接触编程这些年，要是有人问我哪个算法最“短小但耐琢磨”，我脑子里第一个冒出来的就是欧几里得算法，也就是大家常说的辗转相除法。凡是用到最大公约数的地方——分数化简、数论推导、轮转调度、甚至现代密码学里的密钥生成——背后都有它的影子。很多人觉得它无非就是几行递归，真正上手后才发现，从数学原理到工程实现，再到扩展欧几里得算法，每一个环节都有值得深挖的细节。
这篇文章不打算堆数学符号，我想结合自己的踩坑经验，把求最大公约数这件事从原理、代码、复杂度、边界条件、扩展应用，再到面试实战，完整地讲一遍。无论你是刚学算法的新手，还是正在准备算法面试的开发者，看完应该都能直接上手用它解决实际问题。
1. 欧几里得算法核心：搞清楚它在解什么题
1.1 最大公约数：中学概念背后的工程意义
最大公约数，英文叫 Greatest Common Divisor，通常简写为 GCD，指的是两个或多个整数共有的约数中最大的那一个。举个最简单的例子，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。
这个概念表面上是中学数学内容，但在工程里到处都是它的影子。做分数运算的时候，约分靠的就是分子分母的最大公约数；做音视频编解码时，画面的比例缩放需要按最大公约数归一化；做分布式系统里的哈希槽分配，也经常需要判断两个数之间是否互质。互质，意思就是最大公约数等于 1。所以最大公约数并不只是数学题，它是一切需要“找公共单位”的场景的地基。
我当年刚学编程时，第一反应是用暴力枚举：从较小的数开始往下试，逐个检查能不能同时整除两个数。这样写当然能出结果，但一旦数字大到十万百万级别，性能就很糟糕。暴力枚举的时间复杂度是 O(min(a, b))，而欧几里得算法能把这个问题压缩到接近 O(log(min(a, b)))，中间差着好几个量级。这也是为什么这个诞生了两千多年的算法，到今天依然是教科书级的方案。
1.2 辗转相除的核心思想：把大问题缩小到能一眼看出答案
辗转相除法之所以叫“辗转”，是因为它反复利用“余数”把数字逐步缩小，像翻来覆去地辗转一样，直到余数为 0，这时候剩下那个非零数就是最大公约数。
核心定理只有一句话：对于两个整数 a 和 b，假设 a > b，那么 gcd(a, b) = gcd(b, a mod b)。
这个定理的证明很直观。设 a = qb + r，其中 q 是商，r 是余数，0 ≤ r < b。如果某个数 d 能同时整除 a 和 b，那么 d 一定能整除 a - qb，也就是 r。反过来，如果 d 能同时整除 b 和 r，那么 d 一定能整除 qb + r，也就是 a。所以 (a, b) 的所有公约数和 (b, r) 的所有公约数完全一致，最大公约数自然也一样。
我最早看到这个结论时觉得太妙了：一个看似复杂的求最大公约数问题，被转化成两个更小的数的同样问题。每次取模之后，数字规模都会明显下降，继续递归下去，最多几十步就能把数字压到 0。举个例子，求 gcd(252, 105)：
- 252 除以 105，商 2，余数 42
- 105 除以 42，商 2，余数 21
- 42 除以 21，商 2，余数 0
所以 gcd(252, 105) = 21。三步就出来，肉眼可见地高效。
还有一种叫“更相减损术”的古老方法，出自《九章算术》，思路是 gcd(a, b) = gcd(a-b, b)，当 a > b 时。这个方法在原理上完全正确，但减法次数可能很多，不如取模一步到位。不过在某些嵌入式场景里，如果硬件不支持耗时的除法指令，更相减损术配合位移操作还有用武之地，这个我们后面聊 Stein 算法时会再提到。
2. 三种代码实现：从递归到位运算的演进
2.1 递归写法：最符合数学定义的版本
欧几里得算法的递归实现非常简洁，几乎所有算法教材都会用它作为递归教学的入门例子：
def gcd_recursive(a, b): if b == 0: return a return gcd_recursive(b, a % b)递归版本的核心就是那个数学定理：gcd(a, b) = gcd(b, a % b)。当 b 变成 0 的时候，a 就是最大公约数。
但这里有一个容易忽略的细节：函数调用时参数的顺序。假设调用 gcd_recursive(12, 18)，第一次进入函数，b 不等于 0，于是递归调用 gcd_recursive(18, 12 % 18)。因为 12 % 18 等于 12，所以下一轮会变成 gcd_recursive(18, 12)。你会发现第一次递归后，较大的数自动跑到了第一个参数的位置上，后续每轮都保持“前一个数大于等于后一个数”的顺序，不需要人为比较。
真正写代码时要注意 Python 默认递归深度限制。虽然欧几里得算法的递归深度通常只有几十层，但如果你封装成通用工具，并且不小心把参数写反，或者处理负数时出现问题，可能导致递归层数异常增加。生产环境我更推荐用迭代版本。
2.2 迭代写法：稳定可靠，避免栈溢出
迭代版本就是手动维护 a 和 b 的更新过程，直到 b 为 0：
def gcd_iterative(a, b): while b != 0: a, b = b, a % b return abs(a)这里我多做了一个小动作，最后返回 abs(a)，也就是绝对值。为什么要处理负数？因为最大公约数的原始定义通常限定在正整数范围，但编程时你没法保证使用者不会传一个负数进来。Python 的 % 运算对负数的结果符号跟除数有关，直接拿结果去算虽然也能跑到终止，但返回的可能是负数，或者语义不符合预期。主动取一下绝对值，行为就干净多了。
迭代版本的好处是没有任何递归调用，不存在栈溢出的风险，循环次数跟递归版本完全一样。这也是我在生产代码里最常用的版本。
2.3 位运算加速：Stein 算法在大整数场景下的优势
欧几里得算法依赖模运算，而模运算本质上是除法。对于普通的 32 位或 64 位整数，这完全不是问题。但当数字变成几百位、几千位的大整数时，一次除法取模的成本可能非常高。这时候有一个叫 Stein 算法（也叫二进制 GCD 算法）的变体，只用减法、移位和判断奇偶就能算出最大公约数，避开除法。
核心思路基于三个规则：
- 如果 a 和 b 都是偶数，gcd(a, b) = 2 × gcd(a/2, b/2)
- 如果 a 是偶数、b 是奇数，gcd(a, b) = gcd(a/2, b)
- 如果 a 和 b 都是奇数，gcd(a, b) = gcd((a-b)/2, b)，并保证较大的数减较小的数
一段标准的实现长这样：
def gcd_stein(a, b): if a < 0: a = -a if b < 0: b = -b if a == 0: return b if b == 0: return a shift = 0 while ((a | b) & 1) == 0: a >>= 1 b >>= 1 shift += 1 while (a & 1) == 0: a >>= 1 while b != 0: while (b & 1) == 0: b >>= 1 if a > b: a, b = b, a b -= a return a << shift这段代码比欧几里得算法长不少，但里面每一行都有意义。shift 记录了两个数共同含有的因子 2 的个数，最后要乘回去。第一个 while 循环用来剥离公因子 2，第二个 while 把 a 变成奇数，第三个 while 循环里不断把 b 变成奇数，然后相减。每次循环数字至少减半，所以收敛速度依然是指数级的。
需要说明的是，对于 int 范围内的数字，Stein 算法不一定比取模版本快，因为位运算和减法的优势在小整数上体现不出来。但如果你在做大数运算、密码学里的底层实现，或者目标平台没有高效的除法指令，Stein 算法就很有价值。
3. 时间复杂度与边界情况：老算法为什么依然能打
3.1 拉梅定理：最坏情况也只需要 O(log(min(a, b))) 次运算
很多初学者觉得这个算法快，但快在哪里，说不清楚。这里有一个经典的结论，叫拉梅定理：欧几里得算法所需的除法次数，不会超过较小那个数的十进制位数的 5 倍。换句话说，时间复杂度是 O(log(min(a, b)))。
这个界是怎么来的？关键在于最坏情况。什么时候辗转相除的次数最多？答案是当输入是两个连续的斐波那契数时。比如 gcd(144, 233)，你会发现每一步的余数序列恰好是 89、55、34、21、13、8、5、3、2、1，最后才得到结果 1。因为斐波那契数列增长是指数级的，所以数字位数每增加一点，需要的步数只会线性增加一点点。
这解释了欧几里得算法为什么在工程中如此“耐打”：就算两个数都是 64 位整数，最多也就几十次取模运算，性能完全不用担心。对比暴力枚举的 O(min(a, b))，取模版本的复杂度几乎是作弊级别的存在。
不过要注意一点，复杂度分析里讨论的是“取模运算的次数”，不是算术运算的绝对时间。对大整数来说，每次取模本身的耗时跟数字位数有关，所以整体耗时应该是 O(log(min(a, b))) 次取模，乘以每次大整数除法的代价。这也是为什么在超大整数场景下，人们会转而研究 Stein 算法这样避免除法的变体。
3.2 边界情况：零、负数和溢出陷阱
我在代码审查里见过不少奇怪的 bug，大部分出在边界情况。这里把常见坑整理一下。
第一，gcd(0, n) 应该返回 n。因为任何非零整数都能整除 0，0 和 n 的最大公约数就是 n。很多实现里把 b == 0 当作终止条件，正好覆盖了这个场景，但如果你先判断 a == 0 也要记得返回 b。
第二，两个数都是 0 的情况。gcd(0, 0) 在数学上未定义，因为任何数都能整除 0，没有最大值。实际工程中建议直接返回 0 或者抛异常，取决于你的业务语义。
第三，负数的处理。刚才说过，最稳妥的做法是在进入算法之前统一取绝对值。因为 gcd(-12, 18) 在业务上通常等价于 gcd(12, 18)，返回结果用非负数表达最不容易出问题。
第四，C 和 C++ 里的负数取模。C 家族的 % 运算符结果是截断除法得到的，余数符号跟被除数一致。比如 -6 % 4 在 C 里等于 -2，而不是 Python 里的 2。这意味着如果你在 C 里直接实现欧几里得算法，遇到负数输入时可能得到负的余数，导致后续逻辑出错。所以在 C/C++ 实现中，要么先归一化绝对值，要么手动把余数修正为非负。
第五，溢出问题。某些写法里会用减法代替取模，比如：
while (a != b) { if (a > b) a -= b; else b -= a; }这个写法在 a 和 b 都是正数时完全正确，但如果两个数都是 int 的最大值附近，a += b 或者 b -= a 不会溢出，但循环次数可能非常多。更隐蔽的问题是，有人会把 gcd 结果继续参与乘法运算，比如计算最小公倍数时使用 a / gcd(a, b) * b，如果不先除再乘，a * b 可能直接溢出。这个顺序问题在面试和工程里都极其常见。
3.3 标准库到底够不够用
先说结论：如果你的编程语言标准库里已经有现成的 GCD 函数，生产环境优先用标准库。
Python 从 3.5 开始提供了 math.gcd，从 3.9 开始支持任意多个参数：
import math gcd = math.gcd(12, 18)C++17 里则有 std::gcd，需要包含头文件：
#include <numeric> int d = std::gcd(12, 18);Java 有 BigInteger.gcd，不过它要求参数是 BigInteger 对象。
那为什么还要手写？一方面是为了理解原理，考试和面试需要；另一方面，标准库函数解决的是通用场景，如果我们需要在算法内部做定制化处理，比如同时记录辗转过程的商和余数（这正是扩展欧几里得算法要做的事），就必须自己控制每一步的计算过程。标准库再快，也替代不了你对原理的理解。
4. 扩展欧几里得算法：从求 gcd 到解不定方程
4.1 多求出来的两个系数有什么用
普通欧几里得算法解决的是“最大公约数是多少”，扩展欧几里得算法更进一步，不仅求 gcd，还要找出一对整数 x 和 y，使得：
a × x + b × y = gcd(a, b)
这就是贝祖等式。很多人第一眼看到会觉得奇怪：求出 x 和 y 有什么用？我最初也有这个疑问，直到接触了模逆元才明白它的价值。
模逆元，简单说就是找一个数 x，使得 a × x ≡ 1 (mod m)。这在 RSA 公私钥生成、哈希去重、同余方程求解、组合数计算等领域到处都有应用。而计算模逆元的标准做法，正是扩展欧几里得算法。它比费马小定理适用面更广，因为费马小定理要求模数必须是质数，扩展欧几里得算法则没有这个限制，只要 a 和 m 互质就能算。
这就能看出扩展欧几里得算法的定位了：普通欧几里得算法回答“是什么”，扩展欧几里得算法回答“怎么凑出来”。
4.2 手工推演：从辗转相除到回溯求系数
看代码之前，我建议先手工推一次，建立直觉。以 gcd(240, 46) 为例。
第一步，照常做辗转相除：
240 = 46 × 5 + 10 46 = 10 × 4 + 6 10 = 6 × 1 + 4 6 = 4 × 1 + 2 4 = 2 × 2 + 0所以 gcd(240, 46) = 2。但是怎么把 2 写成 240x + 46y 的形式？
从倒数第二个式子开始往回带：
2 = 6 - 4 × 1 4 = 10 - 6 × 1 6 = 46 - 10 × 4 10 = 240 - 46 × 5逐层代入：
2 = 6 - 4 = 6 - (10 - 6) = 2 × 6 - 10 = 2 × (46 - 10 × 4) - 10 = 2 × 46 - 9 × 10 = 2 × 46 - 9 × (240 - 46 × 5) = 47 × 46 - 9 × 240由此得到 x = -9，y = 47。验证一下：240 × (-9) + 46 × 47 = -2160 + 2162 = 2，完全正确。
手工回溯的过程其实就是递归版的展开过程。如果代码里用递归，递去的时候一路取模，归来的时候一路算系数，逻辑非常顺。
4.3 代码实现：递归版与迭代版
递归版扩展欧几里得算法非常优雅：
def exgcd(a, b): if b == 0: return a, 1, 0 g, x1, y1 = exgcd(b, a % b) x = y1 y = x1 - (a // b) * y1 return g, x, y当 b == 0 时，gcd(a, 0) = a，此时 a × 1 + 0 × 0 = a，所以 x = 1，y = 0。这一层向上返回时，利用下一层的结果更新当前层的 x 和 y。
迭代版稍微啰嗦一点，但避免了递归深度问题，并且更容易观察中间状态：
def exgcd_iter(a, b): x0, y0, x1, y1 = 1, 0, 0, 1 while b != 0: q = a // b a, b = b, a % b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return a, x0, y0利用这个函数可以直接求模逆元。求 a 模 m 的逆元时，先判断 gcd(a, m) 是否等于 1，如果不等则不存在逆元。如果相等，exgcd(a, m) 会返回 x，使得 a × x ≡ 1 (mod m)。注意 x 可能是负数，需要做 (x % m + m) % m 的调整，让它落在 [0, m-1] 范围内。
这里还有个小细节：模逆元的计算一定要保证 a 和 m 互质，否则展开到最后可能得到 gcd 不等于 1，那就不存在逆元。我在处理数论题时经常先调一次 gcd 判断，再调 exgcd，虽然多了一次计算，但逻辑更清晰。
4.4 实操场景：RSA 中的私钥指数计算
扩展欧几里得算法在 RSA 里有一个非常具体的应用：计算私钥指数 d。
RSA 加密中，公钥由 e 和 n 组成，私钥包含 d，要求满足：
e × d ≡ 1 (mod φ(n))
其中 φ(n) 是欧拉函数。已知 e 和 φ(n) 的前提下，求 d 就是在求 e 关于模 φ(n) 的逆元。只要 gcd(e, φ(n)) = 1，就可以用 exgcd 直接算出来。整个过程不需要暴力遍历，只需要一次扩展欧几里得算法，这就是这个古老算法在现代密码学里不可替代的原因。
当然，密码学涉及的细节远不止这一点，但核心的数学工具确实是从“求最大公约数”延伸出来的。这算是一个很好的例子，说明基础算法并不“基础”，它只是隐藏在现代系统底层，平时你看不到它而已。
5. 面试与工程实战：从刷题到生产环境的完整经验
5.1 高频面试题与解题思路
在算法面试里，最大公约数很少单独出成一道题，但经常作为核心步骤嵌在更大的题目里。我总结几类常见的考法。
第一类是“直接考理解”，比如要求实现 gcd 并说明原理，或者比较递归和迭代的区别。这类题目考察对边界条件的处理，以及是否能清晰解释辗转相除的数学基础。
第二类是“分数运算”，比如设计一个支持加减乘除的分数类，内部需要约分。这类题目本质就是反复使用最大公约数：分子分母除以 gcd 得到最简形式，分母相同时用最小公倍数，而最小公倍数可以写成 a / gcd(a, b) * b。
第三类是“数组和字符串”，比如 LeetCode 1071 字符串的最大公因子，题目要求判断一个字符串能否由另一个字符串重复若干次得到，本质是把字符串长度求 gcd，再验证是否存在公共子串。LeetCode 914 卡牌分组也是类似思路，统计每个数字出现次数，然后判断这些次数的最大公约数是否大于等于 2。
第四类是“不定方程”，比如 LeetCode 365 水壶问题，判断能否用两个容量分别为 x 和 y 的水壶量出 z 升水。这类题的核心就是贝祖等式：只要 z 能被 gcd(x, y) 整除，且 z 不超过 x + y，就有解。用扩展欧几里得算法可以进一步构造出操作方案。
遇到这类题目，我建议先写出 gcd 的迭代版本，确认边界条件，再根据题目要求决定是否要用 exgcd。因为面试中最常见的失误不是算法不会，而是边界处理很粗糙，比如忘记处理 0、忘记对负数取绝对值、或者用错误顺序计算最小公倍数导致溢出。
5.2 生产环境中的使用建议
在真实项目里，我的建议非常简单：优先用语言自带的数学库，不要手写。Python 的 math.gcd 在 CPython 内部是用 C 实现的，C++ 的 std::gcd 也经过了充分优化，它们的性能和稳定性远超绝大多数手写版本。手写 gcd 的主要价值只存在于两种情况：一是你在实现语言标准库本身，二是你需要在算法里嵌入额外的逻辑，比如扩展欧几里得。
如果你确实要封装自己的工具函数，我推荐按照这样的顺序处理输入：
- 先把所有参数取绝对值，保证后续逻辑只处理非负整数
- 如果出现 0，立即返回不为 0 的那个参数
- 使用 while 循环而非递归，循环条件为 b != 0
- 返回结果之前再取一次绝对值，防止负余数的影响
另外，如果你在写最小公倍数相关逻辑，务必用 a / gcd(a, b) * b 而不是 a * b / gcd(a, b)，前者能避免中间结果溢出。这个错误我在代码审查里见过太多次，后果是数字稍大一点就得到错误结果，且极难排查。
5.3 踩坑实录与排查技巧
下面这些坑，都是我亲手踩过或帮忙排查过的，整理成速查表：
| 症状 | 可能原因 | 解决办法 |
|---|---|---|
| 输入为 0 时返回 0 | 终止条件写错 | 递归入口优先判断 b == 0，并检查 a == 0 时应返回 b |
| 结果为负数 | 参数含负数且未取绝对值 | 进入算法前统一取绝对值，返回前再次确认非负 |
| 递归导致栈溢出 | 深度异常增大 | 改用迭代版本，或在递归函数入口手动限制深度 |
| 最小公倍数计算结果溢出 | 写成 a * b / gcd(a, b) | 改成 a / gcd(a, b) * b |
| C++ 负数取模出现负余数 | 语言本身的截断除法语义 | 先归一化绝对值，或者手动对结果加模数修正 |
| Stein 算法结果不对 | 忘记将 shift 的 2 的幂左移回去 | 检查最后 return a << shift |
最后一个排查技巧：如果怀疑 gcd 函数有 bug，最笨但最有效的验证方式是用暴力枚举做对拍。对于小范围内的随机数，把手写实现的输出和标准库函数的输出逐一比对，很快就能定位是终止条件、负号处理还是溢出问题。对拍方法在排查其他算法问题时同样好用，我几乎每次都靠它快速锁定问题。
5.4 怎么向别人讲清楚这个算法
最后聊一个很多人忽略的点：如何向面试官或同事讲清楚这个算法。
我发现不少开发者能写出正确的代码，但解释原理时只会说“取模后递归”，别人追问“为什么取模后公约数不变”，就答不上来了。一个比较好的讲解框架是：
- 先说明目标：求 gcd(a, b)
- 引入关键等式：a = qb + r
- 解释公约数集合不变：能整除 a 和 b 的数，必然整除 r；能整除 b 和 r 的数，必然整除 a
- 于是把问题规模缩小到 gcd(b, r)
- 不断缩小，直到 r = 0，此时的 b 就是最大公约数
这套逻辑也能无缝衔接到扩展欧几里得算法。讲清楚这两层，才算真正掌握了这个算法，而不只是记住了代码。
根据我的经验，学这个算法最好的方式不是背模板，而是拿笔在纸上手动推几次。算一遍 240 和 46 的辗转相除，再反向回溯求出贝祖系数，比看十遍代码都管用。等你闭着眼都能推完整个过程，再回来看递归代码，就会觉得每一行都理所当然。这个感觉一旦建立起来，以后遇到任何跟最大公约数相关的变形题目，你都能很快想到思路。
)
