当前位置:首页 > 题解目录 > 正文内容

【题解】区间和

亿万年的星光4年前 (2021-05-01)题解目录22599

1.区间和(sum.cpp)

【描述】

输入一个整数Q,进行Q次询问,每次给定两个整数lr每一次输出lr中所有平方数的和 % 1000000007

【输入】

第一行是一个整数Q

后面的Q行每行有2个数字lr

【输出】

Q行,每行一个整数。

【样例输入输出】

light.in

light.out

2

2   10

3   100

13

384

 

【数据范围】

40%的数据:Q<=1000,l<=r<=1000

80%的数据:Q<=1000,l<=r<=1e6

100%的数据: Q<=1e6,l<=r<=1e6

【题目分析】

  • 用到了一点数论的知识,题目范围比较大的时候考虑使用(a*b)%p =(a%p *b%p)%p

  • “平方数”的意思就是两个一样的数的积。即a*a=b。那么b就是一个平方数


【参考答案1】

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int Q;
    long long int l, r, sum;//输入左边界右边界,防止int 不够
    int ans;
    cin>>Q;
    for(int i=0; i<Q; i++)
    {
        cin>>l>>r;//平方数所在范围
        sum = 0;//每次都得初始化
        long long  temp;
        for (int i = l; i <= r; i++)//判断平方数
        {
   temp = sqrt(i);
   if (temp * temp == i)
    sum += temp * temp;
        }
        ans = sum%1000000007;
        cout<<ans<<endl;


    }
    return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

标签: 模拟数论
分享给朋友:

相关文章

【题解】数字三角问题

【题解】数字三角问题

【题目描述】给字一个由n行数字组成的数字三角形(等腰三角形)。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。【输入描述】数字三角形的行数和数字三角形【输出描述】最大的路...

【题解】特殊的质数肋骨

【题目描述】农民约翰母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组...

【题解】计算天数

【题目描述】以 年-月-日 的形式给定一个日期,计算给定的日期是当年第几天。注意闰年二月有29天。【输入描述】输入格式为 yyyy-mm-dd,其中yyyy 表...

【题解】转换字符串的最少操作次数

【题目描述】给你一个字符串 s ,由 n 个字符组成,每个字符不是 'X' 就是 'O' ...

迷宫

【题目描述】一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个...

【题解】木材加工

【题目描述】 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头(木头有可能有剩余),需要得到的小段的数目是事先给定的,切割时希望得到的小段越长越好。   ...