题目描述

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

定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x

输入描述: 

第一行一个数n表示查询次数
之后n行每行两个数l,r

输出描述: 

对于每个查询，输出一个数表示答案
示例1

输入 

5
1 3
1 4
2 4
4 4
1 1000000000

输出 

1
2
1
1
31622

备注: 

n <= 100000
0<= l <= r <= 1000000000

题解

本题还是比较好想的，直接求的话肯定不划算，预处理一下所有的完全平方数然后查找就可以。
需要注意一点的就是一定别忘了0！！！

代码 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long
ll a[N];
void init(){
    for(ll i=0;i<N;++i){
        a[i]=i*i;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    init();
    while(n--){
        ll l,r;
        scanf("%lld%lld",&l,&r);
        l=lower_bound(a,a+N,l)-a;
        r=upper_bound(a,a+N,r)-a;
        printf("%lld\n",max(r-l,0LL));
    }
}