题解 | #完全平方数#
完全平方数
https://ac.nowcoder.com/acm/problem/14733
完全平方数
*题目描述 *
多次查询[l,r]范围内的完全平方数个数
定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x
输入描述:
第一行一个数n表示查询次数
之后n行每行两个数l,r
输出描述:
对于每个查询，输出一个数表示答案
思路：
用一个数组存下标为i的完全平方数，再用upper_bound找下标，通过下标相减计算这区间的完全平方数个数，（这里用的upper_bound全找的大于，后面特判一下左边界是不是完全平方数即可）
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=1e5+5;
ll l,r,a[M];
void solve(){
cin>>l>>r;
ll i=upper_bound(a,a+31623,l)-a;
ll j=upper_bound(a,a+31623,r)-a;
ll ans=j-i;
if(l==a[i-1])ans++;
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;cin>>t;
for(int i=1;i<=1e9/i;i++)a[i]=i*i;
while(t--)solve();
return 0;
}