完全平方数题解

这是一题求完全平方数个数的题目。

关注到这题有多组数据，我们可以想到将所有完全平方数预处理，储存起来，询问时一一查询，此时该算法时间复杂度为 $O(n\sqrt{r})$ ，显然该时间复杂度过大，会导致超时。

可以发现，在区间 $[0,r]$ 中有且只有 $\sqrt{r} + 1$ 个完全平方数，亦可知区间 $[0,l - 1]$ 中有且只有 $\sqrt{l - 1} + 1$ 个完全平方数，那么我们就可以得到区间 $[l, r]$ 中有 $\sqrt{r}- \sqrt{l - 1}$ 个完全平方数，此时时间复杂度为 $O(n)$ ，满足我们的要求。当然，由于 $l$ 有可能为 $0$ ，而此时 $l - 1$ 为负值，因此我们要特别判断这种情况，此时的区间内有 $\sqrt{r} + 1$ 个完全平方数。

#include <math.h>
#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
    int n;
    scanf("%d" , &n);
    while (n--)
    {
        int l , r;
        scanf("%d%d" , &l , &r);
        if (l != 0)
            printf("%d\n" , (int)sqrt(r) - (int)sqrt(l - 1));
        else
            printf("%d\n" , (int)sqrt(r) + 1);
    }
}