题解 | #完全平方数#

思路

在l和r里面一个一个数肯定会超时的，
可以采用二分先把第一个大于l的平方数找出来，
然后把第一个大于等于r的平方数找出来（等于的情况可以思考一下l==r的情况）
提前打好表然后就能知道中间有多少平方数啦~

代码

#include<bits/stdc++.h>
using namespace std;
int n,l,r,cnt=0,sml_num,big_num;
int fang[150000];
int main(){
    fang[0]=0;
    for(int i=1;i*i<=1500000000;i++){
        fang[i]=i*i;
        cnt++;
    }
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&l,&r);
        sml_num=lower_bound(fang,fang+cnt,l)-fang;
        big_num=upper_bound(fang,fang+cnt,r)-fang;
        cout<<big_num-sml_num<<endl;
    }
    return 0;
}