完全平方数

完全平方数

链接：https://ac.nowcoder.com/acm/problem/14733

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

输入描述：

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

输出描述：

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

数据范围

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

solution

根据数据范围可以知道这道题不能暴力做，容易tle掉
可以通过找寻一个O(1)查找此范围在哪两个平方数范围内

#include<bits/stdc++.h>
using namespace std;
int l,r,n;
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>l>>r;
        int x=sqrt(l),y=sqrt(r);
        if(x*x<l)
            x++;
        cout<<y-x+1<<endl;
    }
}