别傻傻列因数了：为什么 2000 年前的算法，依然是今天 C++ 程序员的必修课 - 每日分享

你有没有注意过，生活中那些看似毫无关联的事，背后其实是同一个数学问题？

上周我邻居家两个孩子分零食，一个拿了 24 块巧克力，一个拿了 36 块饼干，要把它们平均装成小礼包，每个包里巧克力和饼干数量都一样，还要让包数尽可能多。俩孩子掰着手指琢磨了半天，我在旁边脱口而出："12 包，每包 2 块巧克力 3 块饼干。"孩子问我怎么这么快，我说这叫最大公约数。

但真正让我想写这篇文章的，不是这个生活小插曲，而是另一个发现：这道小学算术题，和两千年前欧几里得在《几何原本》里写下的算法，以及你今天写的 C++ 代码，本质上是同一件事。

因数的"暴力美学"与它的天花板

如果要找出 12 和 18 的最大公约数，最直接的办法是列出所有因数：

12 的因数：1, 2, 3, 4, 6, 12
18 的因数：1, 2, 3, 6, 9, 18

共同的：1, 2, 3, 6 → 最大是 6，所以 GCD(12, 18) = 6。

这个方法没有任何难度，就是枚举。但问题是——如果数字稍微大一点呢？求 GCD(252, 180) 你还打算一个个列？252 的因数有 18 个，180 的因数也有 18 个，人肉枚举不仅慢，还容易漏。

这时候就需要一个更聪明的办法。欧几里得在公元前 300 年就想到了：两个数的最大公约数，等于较小数和两数相除余数的最大公约数。翻译成数学语言就是：

gcd(a, b) = gcd(b, a % b)

用 18 和 12 试一下：

18 % 12 = 6
12 % 6  = 0  → 余数为 0，除数 6 就是答案

整个过程只有两步，比列因数快了不知道多少倍。这个公式的美妙之处在于，它把问题规模快速缩小，而且永远不丢信息。

有同学问我，那 gcd(a - b, b) 这种"更相减损术"是不是也一个道理？原理相近，但效率差远了——减法最坏情况下要执行很多次，而取模是跳着缩小的。这也是一道选择题里埋的坑：辗转相除法的核心是取余，不是减法。你如果默认减法也是欧几里得算法，那写出来的程序大数直接卡死。

循环还是递归？这是个问题

理解了 gcd(b, a % b) 这个公式，写代码就水到渠成了。先看循环版，我推荐你平时写这个：

int gcd(int a, int b) {
    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

这段代码有个隐含特性很多人没意识到：它不需要比较 a 和 b 的大小。因为如果 a < b，第一次取模 a % b 就等于 a，交换之后 b 变成 a，自然就规整了。所以输入顺序完全无所谓。

对应地，递归版本更简洁：

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

简洁归简洁，面试或者竞赛里用递归要注意栈深度。如果数字达到百万级（比如求 GCD(1000000, 1)），递归层数可能到百万，栈溢出不是闹着玩的。循环是更稳的选择。

另外这里有个经典错误认识，很多人以为 0 和某数的 GCD 是 0，大错特错：0 能被任何非零数整除，所以 gcd(0, x) = x。循环代码里 b = 0 时直接返回 a，正好覆盖了这个边界情况。

还有负数的问题——C++ 的 % 对负数结果可能为负，会导致死循环。稳妥的做法是开头取绝对值：

a = abs(a); b = abs(b);

光会求 GCD 还不够：分数化简实战

很多人学会求最大公约数就停了，但 GCD 的真正价值在于"一次性除到底"。比如分数化简：

24/36 → 分子分母同时除以 gcd(24, 36) = 12 → 2/3

看似简单，但这里暗藏一个新手最容易踩的坑：如果分母为 0 怎么办？ 不判断直接除，程序直接崩溃。在高精度或者竞赛题里，这种隐蔽的分母为 0 问题特别容易让人丢分。

完整逻辑应该是：

int g = gcd(numerator, denominator);
numerator /= g;
denominator /= g;

注意 gcd 内部已经把负数转正了，这样化简 -4/8 得 -1/2 就没问题，负号始终在分子上。

从 GCD 到 LCM：最小公倍数其实就是个除法

知道了 gcd(a, b)，最小公倍数就是白送的：

lcm(a, b) = a / gcd(a, b) * b

注意我先除后乘，为什么？因为 a * b 可能溢出 int 范围。比如 a = 2000000000, b = 1800000000，乘积超过 2^31，直接爆掉。先除再乘能把中间结果控制在合理范围内。

应用场景？你每隔 12 天去图书馆，同桌每隔 18 天去，下一次你俩同时出现的日子就是 lcm(12, 18) = 36 天后。

例题实战：这道题完美卡在 GCD 的理解盲区

来看一道把"最大公约数"和"最简分数"结合起来的题：给你 N、A、B，求分母不超过 N 且小于 A/B 的最大最简分数。

输入：10 1 3
输出：3 10 （因为 3/10 < 1/3，且分母 ≤ 10 的分数中它最大）

核心思路：枚举分母 d 从 1 到 N，对每个 d，最大且小于 A/B 的分子是 (A * d - 1) / B（整除），但这个分数需要化简——只有当分子分母互质（GCD 为 1）时才是真分数。所以每得到一个候选 (A*d - 1) / B，检查它和 d 是否互素，是则更新答案。

这里的关键点是什么？是枚举方向。很多人会从大到小枚举分子分母然后判断，但那样时间复杂度太高。上面这个做法，把 N 的范围（≤1000）利用干净，每次判断 GCD 是 O(log N)，总复杂度 O(N log N)，跑得飞快。

第二道题更有意思：Hankson 的趣味题，已知 gcd(x, a0) = a1 且 lcm(x, b0) = b1，求满足条件的 x 的个数。这题乍一看毫无头绪，但实际上就是个"因子过滤"问题：x 必须是 b1 的因子（因为 lcm 是 b1），所以你枚举 b1 的所有因子，逐个验证是否满足两个条件即可。枚举因子的方式：for (int i = 1; i * i <= b1; i++)，配合 b1 % i == 0 找出 i 和 b1/i，再分别 check。

这两道题都考同一个道理：GCD 是分数化简、因子判断的核心工具，但题目真正考察的是你能不能把它嵌入到枚举、搜索等更大的框架里。光会写 gcd 函数只是第一步。

还需要注意什么？

回到最朴素的问题。如果你要处理多个数的 GCD，比如一组数据的最大公约数，怎么办？两两求，层层嵌套——gcd(a, gcd(b, gcd(c, d)))。用 std::gcd 也行，不过 C++17 之前需要自己写。

还有更高级的东西，比如扩展欧几里得算法（exgcd），能在求 gcd 的同时找到 ax + by = gcd(a, b) 的一组整数解，是解不定方程、计算模逆元的利器——但那是另一个深度了。先把基础打牢，别跳。

我的建议

学算法最忌讳"会用 API 就止步"。std::gcd 一行搞定，但如果你不知道它背后的辗转相除原理，遇到上面那道 Hankson 题，你连怎么枚举 x 都不知道。知其然，也要知其所以然。

你可以试着做几件事：用辗转相除法手算几次 GCD，感受迭代的收敛速度；把循环改为递归看看栈开销的差异；试试用 GCD 求解"判断某数是否为质数"的变种问题（虽然不常用，能加深因子理解）。最后，当你真的把 GCD 用得滚瓜烂熟，你会发现：两千年前的希腊人，早就替我们想清楚了今天九成以上的问题。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）