完全平方数

*题目描述 *

多次查询[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;
}