题解：洛谷 B4553 [GESP202606 二级] 完全平方数计数
【题目来源】
洛谷：B4553 [GESP202606 二级] 完全平方数计数 - 洛谷
【题目描述】
小杨同学正在研究完全平方数。
平方：一个数的平方等于这个数乘以这个数本身。
完全平方数：指可以恰好表示为某个正整数的平方的数。
例如，9 99是完全平方数，因为9 = 3 2 = 3 × 3 9 = 3^2 = 3 \times 39=32=3×3；但27 2727不是，因为27 2727不能表示为任何正整数的平方。
给定两个正整数l ll和r rr（保证l ≤ r l \le rl≤r），小杨同学想知道l ll到r rr之间的所有正整数中（包含l ll和r rr），有多少个数是完全平方数。
【输入】
输入两行，第一行为一个正整数l ll，第二行为一个正整数r rr。
【输出】
输出一个非负整数，表示l ll到r rr中，有多少个正整数是完全平方数。如果l ll到r rr中没有完全平方数，则输出0 00。
【输入样例】
1 21【输出样例】
4【核心思想】
问题分析：给定区间[ l , r ] [l, r][l,r]，需要统计其中完全平方数的个数。完全平方数是指可以表示为某个正整数k kk的平方的数，即x = k 2 x = k^2x=k2。问题等价于求满足l ≤ k 2 ≤ r l \leq k^2 \leq rl≤k2≤r的正整数k kk的个数。
算法选择：
- 直接枚举：遍历区间[ l , r ] [l, r][l,r]中的每个整数，利用平方根函数判断是否为完全平方数
- 数学判定：对于整数x xx，若⌊ x ⌋ 2 = x \lfloor \sqrt{x} \rfloor^2 = x⌊x⌋2=x，则x xx为完全平方数
关键步骤：
- 读入区间：l ll（左端点）、r rr（右端点）
- 遍历判定：对i ii从l ll到r rr：
- 计算t = ⌊ i ⌋ t = \lfloor \sqrt{i} \rfloort=⌊i⌋（对i ii取平方根后向下取整）
- 若t × t = i t \times t = it×t=i，则i ii为完全平方数，
ans++
- 输出答案：a n s ansans
时间/空间复杂度：
- 时间复杂度：O ( r − l + 1 ) O(r - l + 1)O(r−l+1)，遍历区间内每个整数并执行常数时间的平方根运算
- 空间复杂度：O ( 1 ) O(1)O(1)，仅使用常数个变量
完全平方数判定的核心思想：
- 平方根还原法：利用x \sqrt{x}x的整数部分t tt，通过验证t 2 t^2t2是否等于x xx来判定完全平方数，避免了枚举所有可能的因数
- 浮点精度处理：
int(sqrt(x))将浮点结果截断为整数，再平方比较，利用了完全平方数的平方根必为整数这一性质 - 区间计数转化：将"区间内完全平方数个数"转化为"区间内满足k 2 k^2k2形式的整数个数"，若区间范围较小可直接枚举，若范围较大可优化为计算⌊ r ⌋ − ⌈ l ⌉ + 1 \lfloor \sqrt{r} \rfloor - \lceil \sqrt{l} \rceil + 1⌊r⌋−⌈l⌉+1
- 适用于整数性质判定、区间统计类基础数学问题
【算法标签】
#入门 #模拟
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intl,r,ans;// l: 区间左端点; r: 区间右端点; ans: 区间内完全平方数的个数boolcheck(intx)// 判断 x 是否为完全平方数{if(int(sqrt(x))*int(sqrt(x))==x)// 将 sqrt(x) 取整后平方，若等于 x 则为完全平方数{returntrue;// x 是完全平方数}returnfalse;// x 不是完全平方数}intmain(){cin>>l>>r;// 读入区间左右端点for(inti=l;i<=r;i++)// 遍历区间 [l, r] 中的每个整数if(check(i))// 如果当前数是完全平方数{ans++;// 计数器加一}cout<<ans<<endl;// 输出区间内完全平方数的总数return0;}【运行结果】
1 21 4