NC14733 完全平方数(二分)
完全平方数
https://ac.nowcoder.com/acm/problem/14733
题意很简单,求[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; }