【题目来源】

洛谷：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

【核心思想】

1. 问题分析：给定区间[ 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的个数。

2. 算法选择：

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

3. 关键步骤：

   • 读入区间：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

4. 时间/空间复杂度：

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

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

   • 平方根还原法：利用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