完全平方数题解

题目描述：
多次查询[l,r]范围内的完全平方数个数
定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x

输入：
先输入一个整数N,接下来N行，每行输入一个范围；

输出：
一个整数，范围中的完全平方数的个数；

思路：
我们需要的是l，r之间能够开方并且开方结果为整数的数，那么我们就可以反其道而行之，把l,r分别开方，求之间的整数的个数即可；虽然：我们可以使用stl中的upper_bound以及lower_bound直接进行运算，但是为了锻炼自己的代码能力所以还是自己手打一下这两个函数吧；
因为按照题目来的，所以我写的lower与upper与stl中的有所差异。

lower：

int lower(int l,int r,int number){
    int mid=(l+r)>>1;
    while(l<=r){
        mid =(l+r)>>1;//mid要随l，r的变化而更新；
    if(mid>=number)    r=mid-1;//因为找的是最左边的该数值，所以即使等于也要左移，直到最左边为止。
    else {
        l=mid+1;
    }    
    }
    return l；    
} 

upper
类似于lower就不做过多解释了；

int upper(int l,int r,int number){
//    cout<<number<<endl;
    int mid =(l+r)>>1;
    while(l<=r){
        mid =(l+r)>>1;
        if(mid>number)r=mid-1;
        else{
        l=mid+1;
        } 
    } 
    return l;
}

最后就是AC代码了

#include<iostream>
#include<cmath>
using namespace std;
const int type=36125;

int lower(int l,int r,int number){
    int mid=(l+r)>>1;
    while(l<=r){
        mid =(l+r)>>1;
    if(mid>=number)    r=mid-1;
    else {
        l=mid+1;
    }    
    }
    return l;    
} 
int upper(int l,int r,int number){
    int mid =(l+r)>>1;
    while(l<=r){
        mid =(l+r)>>1;
        if(mid>number)r=mid-1;
        else{
        l=mid+1;
        } 
    } 
    return l;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int x,y;
        cin>>x>>y;
        int L,R;
        if(x-(int)sqrt(x)*(int)sqrt(x)>0){
        L=upper(0,type,sqrt(x));     
        }else{
        L=lower(0,type,sqrt(x));
        }

 R=upper(0,type,sqrt(y)); 

    int ans = max (R-L,0);

    cout<<ans<<endl;
    }
    return 0;
}

笱蒻一枚，有错请指教