【题目来源】

洛谷：B4553 [GESP202606 二级] 完全平方数计数 - 洛谷

【题目描述】

小杨同学正在研究完全平方数。

平方： 一个数的平方等于这个数乘以这个数本身。

完全平方数： 指可以恰好表示为某个正整数的平方的数。

例如，$9$ 是完全平方数，因为 $9=3^2=3\times 3$；但 $27$ 不是，因为 $27$ 不能表示为任何正整数的平方。

给定两个正整数 $l$ 和 $r$（保证 $l\le r$），小杨同学想知道 $l$ 到 $r$ 之间的所有正整数中（包含 $l$ 和 $r$），有多少个数是完全平方数。

【输入】

输入两行，第一行为一个正整数 $l$，第二行为一个正整数 $r$。

【输出】

输出一个非负整数，表示 $l$ 到 $r$ 中，有多少个正整数是完全平方数。如果 $l$ 到 $r$ 中没有完全平方数，则输出 $0$。

【输入样例】

1
21

【输出样例】

4

【核心思想】

1. 问题分析：给定区间 $[l,r]$，需要统计其中完全平方数的个数。完全平方数是指可以表示为某个正整数 $k$ 的平方的数，即 $x=k^2$。问题等价于求满足 $l\le k^2\le r$ 的正整数 $k$ 的个数。

2. 算法选择：

   • 直接枚举：遍历区间 $[l,r]$ 中的每个整数，利用平方根函数判断是否为完全平方数
   • 数学判定：对于整数 $x$，若 $\lfloor \sqrt{x}{\rfloor }^2=x$，则 $x$ 为完全平方数

3. 关键步骤：

   • 读入区间：$l$（左端点）、$r$（右端点）
   • 遍历判定：对 $i$ 从 $l$ 到 $r$：
     • 计算 $t=\lfloor \sqrt{i}\rfloor$（对 $i$ 取平方根后向下取整）
     • 若 $t\times t=i$，则 $i$ 为完全平方数，ans++
   • 输出答案：$ans$

4. 时间/空间复杂度：

   • 时间复杂度：$O(r-l+1)$，遍历区间内每个整数并执行常数时间的平方根运算
   • 空间复杂度：$O(1)$，仅使用常数个变量

5. 完全平方数判定的核心思想：

   • 平方根还原法：利用 $\sqrt{x}$ 的整数部分 $t$，通过验证 $t^2$ 是否等于 $x$ 来判定完全平方数，避免了枚举所有可能的因数
   • 浮点精度处理：int(sqrt(x)) 将浮点结果截断为整数，再平方比较，利用了完全平方数的平方根必为整数这一性质
   • 区间计数转化：将"区间内完全平方数个数"转化为"区间内满足 $k^2$ 形式的整数个数"，若区间范围较小可直接枚举，若范围较大可优化为计算 $\lfloor \sqrt{r}\rfloor -\lceil \sqrt{l}\rceil +1$
   • 适用于整数性质判定、区间统计类基础数学问题

【算法标签】

#入门 #模拟

【代码详解】

#include <bits/stdc++.h>
using namespace std;

int l, r, ans;                     // l: 区间左端点; r: 区间右端点; ans: 区间内完全平方数的个数

bool check(int x)                  // 判断 x 是否为完全平方数
{
    if (int(sqrt(x)) * int(sqrt(x)) == x)  // 将 sqrt(x) 取整后平方，若等于 x 则为完全平方数
    {
        return true;               // x 是完全平方数
    }
    return false;                  // x 不是完全平方数
}

int main()
{
    cin >> l >> r;                 // 读入区间左右端点

    for (int i = l; i <= r; i++)  // 遍历区间 [l, r] 中的每个整数
        if (check(i))              // 如果当前数是完全平方数
        {
            ans++;                 // 计数器加一
        }

    cout << ans << endl;           // 输出区间内完全平方数的总数

    return 0;
}

【运行结果】

1
21
4