NC14733 完全平方数（二分）

题意很简单，求[l,r]范围内的完全平方数个数，0<= l <= r <= 1000000000；
因为sqrt(1000000000)=31622，所以我们可以写一个0-31622的递增数组，在这个数组里二分找答案
找一个左边界L使得L²>=l，再找一个右边界使得R²>r，答案就是max(R-L,0)
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =31625;
int a[N];
int main()
{
    for(int i=0;i<N;++i)a[i]=i;
    int n,l,r;
    cin>>n;
    while(n--){
        cin>>l>>r;
        int L=0,R=N;
        L=lower_bound(a,a+N,sqrt(l))-a;
        R=upper_bound(a,a+N,sqrt(r))-a;
        cout<<max(R-L,0)<<endl;
    }
    return 0;
}