企业官网建设流程全解析

“统计某类完全平方数（C语言）”——这个题目我在不同场合见过很多次：期末题里有它，在线判题系统的基础题库里有它，甚至面试里偶尔也会作为一道五分钟手写题出现。它看似简单，真正写起来却容易卡住，因为“某类”三个字就像一个没有填的空，不同题目的空里装的东西完全不一样。有人拿到题先满屏写 for 循环，有人上来就调用 sqrt，还有人被边界条件折磨到怀疑人生。这篇文章想聊透一件事：如何把一个模糊的“某类”，翻译成一坨清晰的、可执行的 C 语言判断逻辑，再搭配上正确的完全平方数枚举方式，让你遇到任何一个具体变体都能快速套用。

1. 先把题目里的“某类”翻译成一个能放进 if 里的判断函数

1.1 完全平方数的定义和实现之间的落差

“完全平方数”的数学定义很干净：一个整数 n，存在整数 k，使得 n = k × k。但到了 C 代码里，这个定义会引出两种截然不同的实现思路。

第一种思路：给定一个整数 x，判断它是不是完全平方数。常见做法是取平方根再四舍五入，回来顺手验证一下。第二种思路：不去逐个判断一个数“是不是平方数”，而是直接枚举 k，让 n 自己长成 k × k。第二种思路在这类统计题里几乎总是更优的，因为题目问的是“统计某一段区间内满足条件的完全平方数有多少个”，而不是“给我一个数，告诉我它是不是平方数”。你在枚举 k 的时候，平方数自然就生成了，连判断“是不是平方数”这一步都不需要做。

很多新手容易掉进第一个坑：老老实实从 a 遍历到 b，每个数都调用一次 sqrt，再做一次平方回验。这样写不是不能跑，而是完全没理解“完全平方数”和“整数乘法”之间的等价关系。既然平方数是有规律生成的，那为什么不顺着根去遍历呢？这是本文第 2 节要展开的核心思想。

1.2 给“某类”建模：一个 match 函数搞定所有条件

“某类”在题目里通常是一个自然语言描述，比如：

• 十进制下每一位数字都是偶数
• 各位数字之和是质数
• 十进制表示是回文数
• 所有数字都不重复
• 数字恰好出现一次且从个位开始递增

这些描述虽然五花八门，但在代码层面的抽象是一致的：它们都是对一个非负整数 x 的十进制位序列提出某种约束。换句话说，你只需要实现一个函数：

int match(long long x);

这个函数接收一个数 x，返回它“属于这一类”还是“不属于这一类”。至于 x 到底是不是完全平方数，由调用方负责。match 只负责回答“这个平方数的十进制形式是否满足附加条件”。

我建议把这个函数看成整道题的接口。题目换一个说法，你只需要改 match 内部，外面的枚举循环一行都不用动。后面第 4 节、第 6 节会围绕这个接口给出多个具体实现。

2. 枚举完全平方数：为什么从“检查区间中的每个数”切换到“生成平方数”更稳

2.1 直接遍历区间的暴力做法有什么问题

假设题目给定区间 [a, b]，要求统计其中满足条件的完全平方数。最直觉的解法是这样：

for (long long i = a; i <= b; i++) { long long t = (long long)sqrt((double)i); if (t * t == i || (t + 1) * (t + 1) == i) { // 判断是否满足“某类” } }

这样能从 a 一直扫到 b，一个不漏。但问题在于：区间长度有多少个元素，你就要做多少次循环、开多少次平方。当 b 达到 10^9 甚至 10^12 时，这个循环次数是很可观的时间开销。即使每次 sqrt 都很快，几千万、几亿次迭代也会让程序明显变慢。

更关键的是，你在这个循环里干了大量无用功：区间里绝大多数数都不是完全平方数，但你仍然要为它们做一次除法、一次平方验证。我们明明知道完全平方数的分布密度低得多，却还要一个萝卜一个坑地去翻整块地，这显然不够聪明。

2.2 从根出发：left 与 right 怎么算

正确的切入点是：先看 a 的平方根和 b 的平方根，把根的范围确定下来。

设一个符合条件的根 k 需要满足：

a <= k * k <= b

那么 k 也有一个明确的取值范围。左边界 left 是最小的整数 k，满足 k × k >= a；右边界 right 是最大的整数 k，满足 k × k <= b。

用公式写出来就是：

left = ceil(sqrt(a)) right = floor(sqrt(b))

但在 C 语言里，我不会直接用 ceil 和 floor 去处理浮点结果，因为浮点数的舍入存在一个小概率翻车的问题。更稳的写法是先用 sqrt 得到一个大概值，然后通过几百行代码也解决不了的整数比较来微调：

long long left = (long long)sqrt((double)a); while (left * left < a) { left++; }

这段代码的意思是：先让 left 落在 sqrt(a) 附近的整数上，如果它偏小，就一路加，直到 left × left 不再小于 a。由于 sqrt 的误差通常不会超过 1，这个 while 循环最多跑一两次，开销可以忽略。

右边界同理：

long long right = (long long)sqrt((double)b); while (right * right > b) { right--; }

其实还有一种更纯正、完全不依赖浮点的方式：手写一个整数二分开根。但在实际竞赛和作业中，sqrt 加个修正循环已经足够可靠，很少需要真的上二分。如果你非要追求极端稳健，二分开根也是一个备选方案，大约二十行代码就能写出来。

2.3 复杂度对比：一个天一个地

直接遍历 [a, b] 的复杂度是 O(b − a + 1)，也就是区间长度。而枚举 k 的复杂度是 O(√b)，因为 k 只需要从 sqrt(a) 走到 sqrt(b)，一共不过 √b 个候选根。

举个例子：b = 10^9 时，直接遍历要做十亿次循环，而根最多只需要从 1 枚举到 31623，连四万次都不到。两者的差距是数量级的。这一点在处理大区间时尤其关键。

我见过不少人写这类题，第一版是暴力扫描能过小数据，结果一到大范围直接超时。其实只要改一下枚举对象，从“枚举平方数本身”改成“枚举平方根”，性能问题就彻底消失了。

3. 数字拆解：把长整型变成十进制位的那套“扒皮”过程

3.1 最标准的拆数字循环

要判断一个数的十进制位是否满足条件，第一步一定是把这个数的每一位拆出来。C 语言里最朴素也最可靠的做法，就是反复用 10 取余、除以 10：

int digit[20]; int cnt = 0; if (x == 0) { digit[0] = 0; cnt = 1; } while (x > 0) { digit[cnt++] = (int)(x % 10); x /= 10; }

这里我把 digit 数组的长度设成 20，是因为题目常见的范围最多到 10^18，而 10^18 在十进制下只有 19 位，预留 20 位绝对够用。

要注意的一点是：这个循环拆出来的数字顺序是低位在前、高位在后。比如 x = 484，循环结束后 digit 数组从下标 0 到 2 依次是 4、8、4，恰好和原数从左到右一样，因为它是回文。但如果是 x = 64，拆出来就是 4、6，而原数从左到右是 6、4。如果你后续要判断“严格递增”这种跟顺序有关的条件，一定要先把数组里的顺序和原数的顺序对齐好，或者直接用索引匹配，不要闭着眼睛认为数组顺序就是自然读法。

3.2 三类典型条件对应的代码形态

“某类”条件虽然千变万化，但落到数字位这个层面，可以分成三类：

第一类：逐位属性型。要求每位的数字本身满足某个条件。比如“每位都是偶数”，那就检查每个 digit[i] % 2 == 0；比如“每位都不是 0”，那就检查 digit[i] != 0。

第二类：整体属性型。要求所有数字位加总之后的结果满足某个条件。比如“各位数字之和是质数”，那就先累加：

int sum = 0; for (int i = 0; i < cnt; i++) { sum += digit[i]; } // 再判断 sum 是否是质数

第三类：序列关系型。要求数字位之间呈现某种序列关系，比如回文、严格递增、没有重复数字等。这类条件最依赖数组的存在，因为你必须能同时访问任意两个位置的数字去做比较。

3.3 把 match 写成一个纯函数的好处

我建议把 match 设计成一个不访问任何全局状态、只用参数 x 做判断的纯函数。原因是它可以被反复调用，也方便拿到不同的题目里复用。写成纯函数还有个额外好处：你能单独用一个小的 main 函数测试它：

int main(void) { printf("%d\n", match(64)); return 0; }

先单独验证 match(64) 是不是你想要的结果，再去套完整的大循环，排查起来轻松很多。很多人喜欢把所有逻辑都塞进 main 里，一旦结果不对，改起来非常痛苦，不如一开始就做好函数拆分。

4. 一份可以直接跑起来的 C 代码：统计“每一位都是偶数的完全平方数”

4.1 完整源码

为了把前面的思路串起来，我用一个具体条件做完整演示：给定区间 [a, b]，统计十进制下每一位都是偶数的完全平方数的个数，并输出这些数本身。

#include <stdio.h> #include <math.h> #include <stdbool.h> static bool match(long long x) { int digit[20]; int cnt = 0; if (x == 0) { digit[0] = 0; cnt = 1; } while (x > 0) { digit[cnt++] = (int)(x % 10); x /= 10; } for (int i = 0; i < cnt; i++) { if (digit[i] % 2 != 0) { return false; } } return true; } int main(void) { long long a, b; if (scanf("%lld %lld", &a, &b) != 2) { return 0; } long long left = (long long)sqrt((double)a); while (left * left < a) { left++; } long long right = (long long)sqrt((double)b); while (right * right > b) { right--; } int count = 0; for (long long k = left; k <= right; k++) { long long n = k * k; if (match(n)) { count++; printf("%lld\n", n); } } printf("count: %d\n", count); return 0; }

如果你只想得到个数，不想打印每一个平方数，直接把循环里的 printf 去掉即可。

这里有几个值得注意的细节：

• match 里先处理 x == 0 的情况。如果不处理，while 循环会发现 x 本来等于 0，直接跳过，cnt 保持 0，后面那段检查也会因为循环次数为 0 而意外返回 true。其实 0 的每一位都是 0，确实是偶数，所以直接让它返回 true 也没问题，但如果不显式处理，逻辑上会有隐患。
• main 里枚举的是 k 而不是 n。k 的取值区间完全由 a 和 b 推导而来，这样得到的 n = k × k 必然落在 [a, b] 内。
• count 用 int 类型就够用。即使区间大到 10^18，完全平方数的个数也只有 10^9 量级，但也有人习惯用 long long，这个不强制。

4.2 运行示例与条件替换策略

假设输入：

1 1000

满足“每一位都是偶数”的完全平方数只有 4、64、400、484 四个，程序输出就是：

4 64 400 484 count: 4

这个结果看起来很合理。64 是 8 的平方，数字 6 和 4 都是偶数；400 是 20 的平方，数字 4、0、0 也都是偶数；484 是 22 的平方，三个数字全是偶数。

如果你想换成别的条件，只需要修改 match 函数内部的判断逻辑，外面循环完全不用动。这就是前面提到的“接口思维”。比如把条件改成“各位数字之和是 7 的倍数”，就在 match 里先算 sum，再判断 sum % 7 == 0；改成“数字中不含 5”，就把 if (digit[i] == 5) return false 写上。

5. 提交前最容易出错的地方：浮点精度、数据范围与输入格式

5.1 sqrt 的精度问题与修正方式

很多教材不会细讲 sqrt 的精度隐患，但实际提交时它经常让人欲哭无泪。

C 语言的 sqrt 接收 double，返回 double。double 能表示的整数在很大范围内是精确的，但 sqrt(25) 理论上应该是整数 5，经过浮点运算后可能变成 4.999999999999 或者 5.000000000001。如果把结果强转成 long long，C 语言是截断而不是四舍五入，于是 4.999999999 会变成 4。

这正好解释了为什么上面代码里要写：

long long left = (long long)sqrt((double)a); while (left * left < a) { left++; }

这一小段修正的逻辑是：一开始得到的 left 如果偏小，就把它往上拨，直到满足 left × left >= a。由于 sqrt 的误差几乎不可能超过 1，这个循环最多执行一两次，性能完全不是问题。右边界同理，如果 right 偏大，就往下拨，直到满足 right × right <= b。

千万不要直接这么写：

long long left = ceil(sqrt((double)a)); long long right = floor(sqrt((double)b));

虽然语义上没错，但万一 sqrt 的结果是 4.999999999，ceil 也会得到 5，看起来也行；可问题在于 sqrt 也可能返回 5.000000001，这时候 floor 会返回 5，看起来也对。问题更多出在边界数很大、数值相差很近的时候，比如 a = 999999999999999999，这种误差累积起来就不好说了。为了保险，我始终建议用“先取近似，再整数修正”的写法。

5.2 中间变量千万别用 int

这类题最隐蔽的坑是：k 看起来不大，但 k × k 会超 int。

假如 b = 10^9，k 最大约 31623，k × k = 10^9，还在 int 范围内。但一旦 b = 10^12，k 最大是 10^6，k × k = 10^12，远超 int 上界 2147483647。这时候如果写成 int n = k * k，数据溢出，结果变成负数或者被截断，match 函数拿到错误的 x，输出的结果自然全错。

所以我在代码里一律把 a、b、left、right、n、k 都声明成 long long。有些人会想：题目里明明说 a、b 不超过 10^9，我直接用 int 不行吗？理论上可以，但我建议统一用 long long，因为这样写不损失任何性能，又能避免以后把代码改大范围时踩坑。程序员的习惯应该是在写类型之前先想一下，而不是看到题面写 int 就跟着写 int。

5.3 多组输入、a>b、a==b 这些输入细节

在线判题系统对输入格式的套路通常有三种：单组输入、多组输入以 EOF 结束、多组输入以 0 0 结束。上面的源码只处理了单组输入，如果你想让它能循环读多组，可以改成：

while (scanf("%lld %lld", &a, &b) == 2) { // 处理这一组数据 }

如果是“输入 0 0 表示结束”，则需要加一句：

if (a == 0 && b == 0) { break; }

还要注意，题目如果说 a、b 是正整数，那 a 至少从 1 开始，不需要考虑 0。但是如果题目允许 a = 0，那 0 本身是 0 的平方，完全平方数，match 里也要允许它通过。我在 match 里专门处理了 x == 0 的分支，就是为了让框架支持 a = 0 的情况。

a == b 的情况也不难，left 和 right 会收敛到同一个值，如果真的存在一个平方数恰好落在这个单点区间里，就会被统计到。如果区间内压根没有平方数，又或者 left 比 right 还大，for 循环的初始化值大于条件值，循环体一次都不执行，count 自然为 0，逻辑是安全的。

6. “某类”换一种说法，代码要改哪里：常见变体集锦

6.1 变体：回文平方数

一个经典的变体是“统计区间内回文完全平方数”。回文数是指正着读和倒着读都一样，比如 121、484、676、10201。

判断回文，只需要在拆出 digit 数组之后，从两头往中间比较：

static bool match(long long x) { int digit[20]; int cnt = 0; if (x == 0) { digit[0] = 0; cnt = 1; } while (x > 0) { digit[cnt++] = (int)(x % 10); x /= 10; } int i = 0, j = cnt - 1; while (i < j) { if (digit[i] != digit[j]) { return false; } i++; j--; } return true; }

要注意 x = 0 也被我的代码判成回文，因为 0 只有一位，正反都一样。如果你的题目从 1 开始统计，这不会影响结果。

6.2 变体：各位数字之和是质数

这类条件需要两步：先把各位数字加起来，再判断和是否为质数。

static bool is_prime(int x) { if (x < 2) { return false; } for (int i = 2; i * i <= x; i++) { if (x % i == 0) { return false; } } return true; } static bool match(long long x) { int sum = 0; while (x > 0) { sum += (int)(x % 10); x /= 10; } return is_prime(sum); }

很多同学会担心 is_prime 的效率，觉得每次都要试除到 sqrt(x)。其实完全不用怕，因为一个 long long 顶多 19 位十进制，各位数字之和最大也就是 9 × 19 = 171。判断 171 是不是质数，只需要试除到 13，比判断一个 10^12 级别的数快太多了。这也是数字和类条件的天然优势。

6.3 变体：数字不重复

要求完全平方数的十进制表示中，每个数字最多出现一次，这个条件也很常见。

static bool match(long long x) { int seen[10] = {0}; while (x > 0) { int d = (int)(x % 10); if (seen[d]) { return false; } seen[d] = 1; x /= 10; } return true; }

这里用了一个长度为 10 的数组记录 0 到 9 每个数字是否已经出现过。只要某个数字第二次出现，立刻返回 false。这个技巧本质上是“哈希表”的最简形态，很多数字类条件都能用它变出来，比如“至少包含一次数字 7”“偶数字出现次数不超过两次”等等。

6.4 把 match 当成唯一需要维护的接口

你会发现，从头到尾的核心主线只有一条：外层的根枚举是固定的，变化的永远只是 match 里的判断逻辑。

我把这种解法的好处总结给刚入门的读者：如果你想掌握这类题，先不要背代码，而是先理解两层结构。第一层是根枚举，负责低成本地把所有完全平方数列出来；第二层是条件判断，负责从这些平方数里选出“某类”。将来遇到任何一道“统计某类完全平方数”的新题，你脑子里就两个问题：区间怎么拆成根的范围？这个条件怎么翻译成 match 里的逻辑？想清楚这两点，代码基本就是照着框架填。

我在实际刷题过程中也吃过不少亏。最开始我总喜欢把判断逻辑直接写在 main 的大循环里，结果稍微改一个条件就要重写整个循环，还容易写漏边界。后来我把 match 抽成独立函数，几乎所有变体都只需要改函数体，主循环一次都不用动。代码清晰度上去了，调试成本也低了一大截。

这些细节，比单纯背下一段模板要有用得多。下次再看到“统计某类完全平方数”，你会觉得它其实一点也不神秘。