题意:

多次查询[l,r]范围内的完全平方数个数

定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x
0<=l,r<=1e9


题解:

预处理出范围内所有完全平方数(小于1e5个),然后分别二分l,r所在的位置做差就可以


代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}

LL l,r,n;
vector<LL>v;
int main(){
    scanf("%lld",&n);

    for(LL i=0;i<=100000;i++){
        v.pb(i*i);
    }

    while(n--){
        scanf("%lld%lld",&l,&r);
        l=lower_bound(v.begin(),v.end(),l)-v.begin();
        r=upper_bound(v.begin(),v.end(),r)-v.begin();
        printf("%lld\n",r-l);
    }
}