当猴子开始藏苹果：聊聊最大公约数背后那个"反复切"的思维 - 每日分享

先抛结论：辗转相除法之所以成立，核心不在于"除法"这个动作，而在于一个更深的结构——两个数的公约数集合，和"小数"与"余数"的公约数集合，是完全相同的。理解了这一点，你就不需要背 gcd(a,b) = gcd(b, a%b) 这个公式了，因为它会变成一件自然而然的事。

从"公平分配"说起

分零食这件事大家都熟。12颗糖和8块巧克力，最多能分给几个人，每人拿到的一样多且没有剩余？答案是4。这个4就是12和8的最大公约数。

但真正有意思的问题不是"怎么求"，而是"为什么辗转相除法能求"。

大多数人学GCD的时候，老师直接甩出欧几里得算法，然后让你照着写循环。代码确实短，三行就完事了：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

但如果你只是记住了这个模板，遇到变形题就会卡住。比如下面这道。

一道让很多人绕晕的题：猴子分苹果

n只猴子采了一堆苹果，约定第二天平分。但每只猴子都趁夜里偷偷跑去，把苹果平均分成n份，发现多出m个，就把这m个吃掉，然后藏走一份，剩下的重新合在一起。第二天大家一起分，巧了，还是多出m个。问原来至少有多少苹果？

样例输入 5 1，输出 15621。

这道题表面上看跟GCD没什么关系，但它考察的恰恰是同一种思维：在反复操作中寻找不变量。

先分析一下。假设第k只猴子来的时候看到的是 $x_k$ 个苹果，它的操作是：

吃掉m个：$x_k - m$
这个数能被n整除，分成n份，每份是 $\frac{x_k - m}{n}$
藏走一份，剩下 $(n-1) \cdot \frac{x_k - m}{n}$
所以下一只猴子看到的是 $x_{k+1} = \frac{(n-1)(x_k - m)}{n}$

第二天剩下的苹果数也要满足 $\equiv m \pmod{n}$。

暴力枚举当然可以，但n和m虽然小（n<9），答案可能很大，纯暴力会超时或者写得很丑。更好的思路是倒推：从第二天剩下的最少情况出发，反推回去。因为每次操作都是线性的，倒推公式很干净：

$$x_k = \frac{n \cdot x_{k+1}}{n-1} + m$$

从最后一天倒推n次，每次要求 $n \cdot x_{k+1}$ 能被 $n-1$ 整除。最小的满足条件的起点就是答案。

关键代码思路：

# 从最后一次分完最少剩 m 个开始倒推
x = m  # 第二天分完后剩下的（最少情况）
for _ in range(n):  # 倒推 n 次
    # x 是当前猴子操作后剩下的
    # 操作前：吃掉m个，分成n份藏走一份
    # 所以操作前 = x * n // (n-1) + m，需要整除
    while (x * n) % (n - 1) != 0:
        x += 1  # 调整起点直到整除
    x = x * n // (n - 1) + m

这道题的本质是什么？是在递推关系中寻找满足整除条件的最小解。而GCD解决的是"两个数能被同一个数整除的最大那个"，两者共享同一个数学直觉：整除结构决定了问题的解空间。

回到辗转相除法：为什么它是对的

现在认真回答那个问题：为什么 gcd(a, b) = gcd(b, a % b)？

设 $a = qb + r$，其中 $r = a \bmod b$。

第一步：如果 $d$ 是 $a$ 和 $b$ 的公约数，那么 $d | a$ 且 $d | b$，所以 $d | (a - qb) = r$。也就是说，$d$ 也是 $b$ 和 $r$ 的公约数。

第二步：反过来，如果 $d$ 是 $b$ 和 $r$ 的公约数，那么 $d | b$ 且 $d | r$，所以 $d | (qb + r) = a$。也就是说，$d$ 也是 $a$ 和 $b$ 的公约数。

两步合起来：${a, b}$ 的公约数集合 $= {b, r}$ 的公约数集合。既然集合完全一样，最大的那个当然也一样。

这就是为什么算法成立。不是因为"除法很神奇"，而是因为公约数集合在变换下保持不变。

用木板来类比：12厘米和8厘米的木板，你要切出尽可能长的小段。12切掉一个8剩4，现在问题变成8和4。8切掉两个4剩0，问题结束，答案是4。每次"切"的操作不改变"能同时整除两块木板的长度"这个集合——原来能整除12和8的，现在也能整除8和4；反之亦然。

新手最容易踩的坑

交换顺序写反。a, b = b, a % b 是对的。有人写成 a, b = a % b, b，这就完全错了——余数赋给了a，b没变，下次循环还是同样的计算，直接死循环。

while条件写错。判断的是 b != 0，不是 a != 0。因为终止条件是余数为0，此时b变成了0，a就是答案。

没考虑a < b的情况。其实不需要特判。如果a < b，第一次 a % b = a，然后a和b自动交换，大的就到前面了。算法自己会处理。

负数问题。数学上GCD定义为非负。Python的 math.gcd 会自动取绝对值，但自己写的函数不会。加一行 a, b = abs(a), abs(b) 就行。

一道选择题暴露的认知盲区

有这么一道题：辗转相除法求a和b（a > b）的最大公约数时，下一步应该计算什么？

选项有 a-b、a+b、a%b、a//b。

答案是 a%b。但选错的人不少——有人选a-b，因为记得"更相减损术"也是求GCD的方法；有人选a//b，因为觉得"除法"嘛，当然是算商。

这里暴露的问题是对两种算法没有清晰区分：

更相减损术（中国古代）：gcd(a,b) = gcd(b, a-b)，用减法缩小问题
辗转相除法（欧几里得）：gcd(a,b) = gcd(b, a%b)，用取余缩小问题

两者殊途同归，但效率差别巨大。更相减损术在遇到(1000000, 1)这种情况时要减一百万次，而辗转相除法两步就出结果。

所以记住：辗转相除法用的是取余（%），不是减法，也不是整除（//）。

GCD还能干什么

这东西的用处远超你的想象：

化简分数。36/48，分子分母同时除以gcd(36,48)=12，得到3/4。Python的 fractions.Fraction 内部就是这么做的。

求最小公倍数。lcm(a,b) = a * b // gcd(a,b)。这个公式成立是因为 $a \cdot b = \gcd(a,b) \cdot \text{lcm}(a,b)$，本质上是质因数分解中指数取min和max的关系。

判断互质。gcd(a,b)=1就意味着互质。RSA加密算法中生成密钥的第一步就是找两个大质数，判断互质是基础操作。

扩展欧几里得算法。不仅能求gcd，还能同时求出满足 $ax + by = \gcd(a,b)$ 的整数x和y。这是求解线性同余方程的基础，在竞赛中非常常见。

最后说一句

GCD这个知识点，表面上看只是"求两个数的最大公约数"，但它背后的思维方式——在变换中寻找不变量——才是真正值得带走的东西。猴子分苹果是这样，辗转相除是这样，很多算法问题都是这样。

如果你已经理解了辗转相除法，下一步建议看看扩展欧几里得算法和线性同余方程。那两个东西会把你对GCD的理解拉高一个层次。至于 math.gcd，正式项目里直接用就行，但自己手写一遍的过程不能跳过——因为理解原理和会调库，是两件完全不同的事。

关于作者

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

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

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