接触编程这些年要是有人问我哪个算法最“短小但耐琢磨”我脑子里第一个冒出来的就是欧几里得算法也就是大家常说的辗转相除法。凡是用到最大公约数的地方——分数化简、数论推导、轮转调度、甚至现代密码学里的密钥生成——背后都有它的影子。很多人觉得它无非就是几行递归真正上手后才发现从数学原理到工程实现再到扩展欧几里得算法每一个环节都有值得深挖的细节。这篇文章不打算堆数学符号我想结合自己的踩坑经验把求最大公约数这件事从原理、代码、复杂度、边界条件、扩展应用再到面试实战完整地讲一遍。无论你是刚学算法的新手还是正在准备算法面试的开发者看完应该都能直接上手用它解决实际问题。1. 欧几里得算法核心搞清楚它在解什么题1.1 最大公约数中学概念背后的工程意义最大公约数英文叫 Greatest Common Divisor通常简写为 GCD指的是两个或多个整数共有的约数中最大的那一个。举个最简单的例子12 和 18 的约数分别是12 的约数1、2、3、4、6、1218 的约数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余数 42105 除以 42商 2余数 2142 除以 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 为 0def 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。因为任何非零整数都能整除 00 和 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)C17 里则有 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 -9y 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 1y 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) * bC 负数取模出现负余数语言本身的截断除法语义先归一化绝对值或者手动对结果加模数修正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 的辗转相除再反向回溯求出贝祖系数比看十遍代码都管用。等你闭着眼都能推完整个过程再回来看递归代码就会觉得每一行都理所当然。这个感觉一旦建立起来以后遇到任何跟最大公约数相关的变形题目你都能很快想到思路。