【题解】区间和
1.区间和(sum.cpp)
【描述】
输入一个整数Q，进行Q次询问,每次给定两个整数l和r，每一次输出l～r中所有平方数的和 % 1000000007
【输入】
第一行是一个整数Q
后面的Q行每行有2个数字l和r
【输出】
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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。