比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;
}