202606-完全平方数计数(luogu-B4553)

GESP C++二级，2026年6月真题，循环和数学运算，难度⭐，洛谷难度入门。

luogu-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

输入 #1

1
21

输出 #1

4

说明/提示

样例解释 1

在 $1$ 到 $21$ 中，有以下 $4$ 个整数是完全平方数： $1, 4, 9, 16$。

数据范围

$1 \le l \le r \le 2000$。

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：

   • 输入两个正整数 $l,r$，表示一个整数范围
   • 需要计算范围 $[l, r]$ 内有多少个完全平方数

2. 解题关键 — 判断完全平方数：

   • 方法一（逐个判断）：遍历 $l$ 到 $r$ 的每个数 $i$，对 $i$ 开平方后取整，判断平方后是否等于 $i$
   • 方法二（直接计数）：利用数学性质，$[1, n]$ 中的完全平方数个数等于 $\lfloor\sqrt{n}\rfloor$，因此 $[l, r]$ 中的完全平方数个数等于 $\lfloor\sqrt{r}\rfloor - \lfloor\sqrt{l-1}\rfloor$

3. 复杂度分析：

   • 方法一：时间复杂度 $O(r - l + 1)$，遍历范围内每个数
   • 方法二：时间复杂度 $O(1)$，仅需两次开平方运算
   • 空间复杂度：$O(1)$

示例代码

方法一、逐个判断

#include <iostream>
#include <cmath>

int main() {
    // 定义输入的范围边界
    int l, r;
    // 从标准输入读取 l 和 r
    std::cin >> l >> r;
    // 计数器，记录完全平方数的个数
    int count = 0;
    // 遍历范围内的每个数
    for (int i = l; i <= r; i++) {
        // 对 i 开平方并取整
        int s = (int)std::sqrt(i);
        // 如果 s 的平方等于 i，则 i 是完全平方数
        if (s * s == i) {
            count++;
        }
    }
    // 输出完全平方数的个数
    std::cout << count << std::endl;
    return 0;
}

方法二、数学公式直接计算

利用 $[1, n]$ 中完全平方数的个数等于 $\lfloor\sqrt{n}\rfloor$ 这一性质，直接计算 $\lfloor\sqrt{r}\rfloor - \lfloor\sqrt{l-1}\rfloor$ 即可。

#include <iostream>
#include <cmath>

int main() {
    // 定义输入的范围边界
    int l, r;
    // 从标准输入读取 l 和 r
    std::cin >> l >> r;
    // [1, r] 中完全平方数的个数为 floor(sqrt(r))
    // [1, l-1] 中完全平方数的个数为 floor(sqrt(l-1))
    // 两者相减即为 [l, r] 中完全平方数的个数
    int count = (int)std::sqrt(r) - (int)std::sqrt(l - 1);
    // 输出结果
    std::cout << count << std::endl;
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号