NC14733 完全平方数

由于sqrt(10e)=31622，题目也说了1-10e内有31622个完全平方数，所以我们就可以建立一个0-31622的递增数组，然后在数组中二分查找答案。假设有一个0-r的区间，这个区间内的完全平方数最多有sqrt(r)个。所以求l-r区间内的完全平方数时，我们在数组中找到第一个>=sqrt(l)的位置，再找到第一个>sqrt(r)的位置，两个位置相减就是答案

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