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

【题目来源】洛谷B4553 [GESP202606 二级] 完全平方数计数 - 洛谷【题目描述】小杨同学正在研究完全平方数。平方一个数的平方等于这个数乘以这个数本身。完全平方数指可以恰好表示为某个正整数的平方的数。例如9 99是完全平方数因为9 3 2 3 × 3 9 3^2 3 \times 39323×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^2xk2。问题等价于求满足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​⌋2x则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×ti则i ii为完全平方数ans输出答案a n s ansans时间/空间复杂度时间复杂度O ( r − l 1 ) O(r - l 1)O(r−l1)遍历区间内每个整数并执行常数时间的平方根运算空间复杂度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适用于整数性质判定、区间统计类基础数学问题【算法标签】#入门 #模拟【代码详解】#includebits/stdc.husingnamespacestd;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(){cinlr;// 读入区间左右端点for(intil;ir;i)// 遍历区间 [l, r] 中的每个整数if(check(i))// 如果当前数是完全平方数{ans;// 计数器加一}coutansendl;// 输出区间内完全平方数的总数return0;}【运行结果】1 21 4