题意:
多次查询[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); } }