牛客算法周周练2 C完全平方数 题解
完全平方数
https://ac.nowcoder.com/acm/contest/5203/C
比A还签到的签到题。。。
求l-r的完全平方数的个数
我们按套路将询问拆成两个询问:
求0-r的完全平方数的个数和0-l-1的完全平方数的个数
那么，我们需要解的就是求0-x的完全平方数的个数
注意到,l可能为0，所以，可能有个询问是求0-(-1)的完全平方数的个数，这个时候特判即可
那么，我们来看看其他情况怎么做。
假设我们枚举的是完全平方数a(a=b*b)，我们可以先预处理出0-1000000000内所有完全平方数，然后二分判断下即可
但是，我们有更简单的做法——枚举b
我们知道，对于0-x中，每个完全平方数对应的b一定是从0开始的连续一段数(可以反证法证明)，而最大的，明显就是，所以，我们对于每个询问，输出
即可
代码：
#include<bits/stdc++.h>
using namespace std;
inline int calc(int x){
return x<0?0:sqrt(x)+1;
}
int main(){
int n;
scanf("%d",&n);
while(n--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",calc(y)-calc(x-1));
}
return 0;
} 
