如果让我从所有算法里挑两个最容易被低估的我大概率会选 gcd最大公约数和 lcm最小公倍数。这两个概念小学就开始接触算法课上也是开篇知识点但很多人对它们的理解停留在“会写个辗转相除就行”的层面。实际上gcd/lcm 向下承接数论里最底层的整除结构向上延伸到模逆元、同余方程、周期事件对齐、加密算法这些看起来毫不相干的领域。这篇博文我想把多年用这两个算法的完整经验梳理一遍内容包括欧几里得算法为什么快、求 lcm 时必踩的溢出坑、扩展欧几里得的推导与代码以及几类高频变种题的解题思路。刚学算法的同学可以当进阶笔记看有经验的老手也可以顺带查漏补缺。1. 重新认识 gcd 和 lcm它们不只是两个“小学概念”1.1 公约数集合与公倍数集合先看定义背后的结构gcd全称 greatest common divisor指两个整数公共约数当中最大的那个。比如 12 和 18约数分别是 {1,2,3,4,6,12} 和 {1,2,3,6,9,18}公共约数集合是 {1,2,3,6}最大的是 6所以 gcd(12,18)6。lcm全称 least common multiple指两个整数公共倍数当中最小的那个。12 的倍数是 {12,24,36,48,...}18 的倍数是 {18,36,54,...}公共倍数集合是 {36,72,108,...}最小的是 36所以 lcm(12,18)36。单看定义确实不难但有一个容易被忽略的点公约数的最大者和公倍数的最小者本质上反映的是同一个整除结构的两面。任意一个公约数都能整除最大公约数任意一个公倍数都能被最小公倍数整除。这个性质比“找到最大/最小”这个操作本身重要得多后面很多证明和工程判断都依赖它。1.2 乘积恒等式gcd × lcm a × b一座关键桥梁这是 gcd 和 lcm 之间最经典的关系式lcm(a,b) × gcd(a,b) a × b第一次看到这个公式的人通常会问为什么成立不从抽象证明出发用质因数分解看最直观。把 12 分解成 2² × 318 分解成 2 × 3²。gcd 取的是每个质因数指数的较小者2 的指数取 min(2,1)13 的指数取 min(1,2)1所以 gcd2×36。lcm 取的是每个质因数指数的较大者2 的指数取 max(2,1)23 的指数取 max(1,2)2所以 lcm2²×3²36。minmax 恰好等于两个原本指数的和所以乘积回归到原始数字的乘积。这个恒等式最大的工程价值在于求 lcm 根本不需要去枚举倍数只需要先算 gcd再做一次除法一次乘法。现实中几乎所有的 lcm 实现都是走这条路而不是真的去找公倍数。理解了这一点后面第三章讨论的“先除后乘防止溢出”才有了基础。1.3 实际场景从分数化简到周期性事件gcd 和 lcm 在真实业务里最常见的出场方式其实比很多教科书讲的更贴近日常。分数化简是最典型的 gcd 场景。把分子分母同时除以它们的 gcd就能得到最简分数。比如 24/36gcd(24,36)12分子分母同除 12得到 2/3。这个操作在做有理数存储、单位换算、比例计算时到处都用。也有不少工程团队在存储分数时会强制约分本质上就是在用 gcd 保证数值表示的唯一性。lcm 的经典场景是通分和周期对齐。通分时找两个分母的 lcm 作公分母周期事件对齐时比如设备 A 每 12 小时巡检一次设备 B 每 18 小时巡检一次同时出发后下一次同时巡检的时间就是 lcm(12,18)36 小时。齿轮啮合、灯光闪烁规律、任务调度里的最小同步周期背后全是同一个模型。列完这些会发现gcd/lcm 是典型的“问题本身简单、迁移到真实场景后价值极大”的算法。2. 辗转相除法为什么它高效以及复杂度下界里的斐波那契2.1 算法核心gcd(a,b) gcd(b, a mod b) 的正确性直觉求 gcd 最古老也最实用的算法是欧几里得算法核心就一个递推式gcd(a,b) gcd(b, a mod b)先说人话版本的直觉。把“a 能否被 d 整除”换成更本质的话如果 d 同时整除 a 和 b那么 d 一定整除 a 减去若干个 b 之后剩下的余数因为余数可以写成 a - qb。反过来如果 d 同时整除 b 和余数 r那 d 一定整除 a因为 a qb r。所以“a 和 b 的公约数集合”和“b 和 r 的公约数集合”是同一个集合最大公约数自然也相同。举个例子完整走一遍。求 gcd(48,18)48 2×18 12所以 gcd(48,18) gcd(18,12)18 1×12 6所以 gcd(18,12) gcd(12,6)12 2×6 0所以 gcd(12,6) gcd(6,0)。当 b0 时gcd(a,0)a答案就是 6。很多人忽略这个证明的一个好处它证明了算法过程中每一步的答案都保持不变而不是“越算越接近答案”。所以即使中间某一步的商比较大也没关系最后一步余数为 0 时的被除数就是想要的结果。2.2 复杂度不是靠运气斐波那契数列就是最坏情况欧几里得算法的时间复杂度是 O(log min(a,b))这个结论经常被直接引用但背后的原理值得展开说。有一个简单的观察对于任意 a ≥ b 0都有 a mod b ≤ a/2。分成两种情况看。如果 b ≤ a/2那余数一定小于 b自然不超过 a/2如果 b a/2那么 a mod b a - b a - a/2 a/2。所以每做一步除法被除数至少缩水一半。这样估算的话迭代次数大概是 O(log a)。这个证明足够直观但不精确。更严格的结论是最坏情况发生在两个数恰好是相邻斐波那契数时。比如求 gcd(55,34)553421342113这串递归会把所有斐波那契数列相邻项“消费”一遍。斐波那契数 F(n) 的规模大约以黄金比例 φ≈1.618 的速度增长所以 n≈log_φ(min(a,b))。也就是说递归深度是自然对数量级不管输入多大都不会栈溢出。这个性质让递归实现变得非常安全。对比一下更相减损术就更有意思了。更相减损术的思想是 gcd(a,b)gcd(a-b,b)反复用减法代替除法。这个算法在两边数量级接近时效率还行但如果一个数远大于另一个比如 gcd(1000000,1)就要减 999999 次直接退化到 O(max(a,b))。欧几里得算法能一次除法跳过大量减法这就是模运算的意义。2.3 递归、迭代与 Stein 算法实际工程怎么选欧几里得算法的实现有很多层选择。递归版本最简洁int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }这个写法在递归深度只有 O(log n) 时没有任何问题。不过实际工程里我更习惯写成迭代形式省去函数调用开销也避免某些编译器在低优化等级下把尾递归优化漏掉int gcd(int a, int b) { while (b ! 0) { int r a % b; a b; b r; } return a; }还有一种 Stein 算法也叫二进制 gcd完全回避除法只用移位和减法两数都为偶数时提取公因子 2一奇一偶时把偶数不断右移两个都是奇数时做减法再右移。这套做法在上个世纪没有硬件除法指令的时代意义巨大现在在普通整数上反而因为多次位运算不一定比一次除法快。不过在处理超长整型数字时它仍有价值因为大整数的除法远比移位昂贵。我个人的建议是日常整数用欧几里得算法就够了真到了大数场景优先考 std::gcd 或者成熟大数库没有必要自己在性能边缘反复横跳。3. 求 lcm 时最容易踩的坑运算顺序、多数合并与周期语义3.1 先除后乘还是先乘后除相差的不只是一个溢出既然有了恒等式 lcm(a,b) a × b / gcd(a,b)实现时最常见的坑就来了。最直觉的写法是先算 a × b 再除 gcd但这一步在 a、b 都比较大时可能导致中间乘法溢出即便最终结果并不超范围。举个例子。设 a46340b46340gcd46340lcm46340。如果先乘 a×b46340×463402147395600这个值已经非常接近 32 位有符号整数的上限约 21.47 亿。再比如用 C int 去计算两个较大的互质数a×b 很容易突破 2^31-1。正确的做法是先除后乘long long lcm(int a, int b) { return 1LL * a / gcd(a, b) * b; }逻辑上先除以 gcd 再乘 b 和先乘再除结果一样因为 gcd 必然整除 a。但中间值从可能溢出的 a×b 变成了 a/gcd(a,b)这是一个明显小得多的数。这条规则值得当成默认习惯凡是涉及 lcm 的代码一律先除后乘。如果两个输入本身就是 long long 级别的大数先除后乘也可能放不下最终结果那就必须上大整数类型Python 直接支持C 就换 BigInteger 或第三方大整数库。3.2 多个数的 lcm逐项合并不难难在结果增长太快求三个或更多数的 lcm方法是逐个合并lcm(a,b,c)lcm(lcm(a,b),c)。这个顺序没问题因为 lcm 满足结合律。但有个工程上的隐患——lcm 的数值增长速度远快于 gcd。算一下 1 到 20 的 lcm 是多少结果是 232792560已经接近 2.3 亿。继续算到 1 到 30结果是 2329089562800约 2.3 万亿直接超过 32 位整数。所以处理多数的 lcm 时如果数据范围较大第一步就应该评估最终量级要么用 64 位整数要么直接上大数。还有一个很隐蔽的问题某些工程代码为了提高“精度”会把每一步 lcm 转成浮点数参与计算比如写成 double 后做除法乘法。这会导致超出 2^53 的整数丢失精度结果看起来“差不多”实际已经错了。我排查过多次这类问题结论很统一——lcm 是精确整数运算任何浮点中间表示都是不必要的冒险。3.3 周期语义别把“最小公倍数”和“下次同时发生”搞混lcm 在周期场景里的意义是“两个周期事件再次同步所需的时间”但实际应用时有个容易混淆的地方。假设事件 A 每 6 天发生一次事件 B 每 10 天发生一次同时发生后第 30 天会再次同时发生因为 lcm(6,10)30。这没错。但如果问题是“30 天内两个事件会在同一天发生的天数有多少”答案不是“1 天”这需要的是计数而不是单纯的 lcm。再比如系统里有多个任务周期最短的同步周期是 lcm但同步时刻之间还可能有局部的重合或嵌套周期单靠 lcm 不足以描述完整时间线。所以我在实际业务里会提醒自己lcm 回答的是“下一次对齐的时间”而不是“对齐的次数”。先把问题转化清楚再决定是调 lcm 还是写一个时间扫描逻辑。很多人在这步栽跟头不是 lcm 不会算而是问题没有拆到正确的粒度。4. 扩展欧几里得从“求最大公约数”到“求一组整数解”4.1 贝祖定理gcd 本质上是线性组合的最小正整数欧几里得算法解决的是“gcd 等于多少”扩展欧几里得算法简称 exgcd解决的是另一个问题给定 a、b找到整数 x、y 使得ax by gcd(a,b)这组解的存在性由贝祖定理保证a 和 b 的 gcd 恰好是 a、b 的全体整数线性组合 {axby | x,y∈Z} 中的最小正整数。比如 gcd(18,12)6而 18×(1)12×(-1)6说明 x1,y-1 就是一组解。当然这组解不是唯一的任意加一个向量都能产生新的解后面讨论同余方程时会用到完整的解系。贝祖定理的价值在于把 gcd 从“约数集合”的静态视角带到了“可构造的线性组合”的动态视角。很多问题的关键不是 gcd 是多少而是怎样用 a 和 b 拼出这个 gcd。最典型的就是解二元一次不定方程 axbyc右侧必须是 gcd 的整数倍才有解exgcd 可以给出特解再扩展得到通解。4.2 exgcd 的递归实现神秘参数交换背后是代数恒等式理解 exgcd 最快的路径是把递归过程从头推一遍。考虑递归调用 exgcd(b, a % b) 返回的解 x1、y1满足b×x1 (a mod b)×y1 gcd(b, a mod b)因为 a mod b a - [a/b]×b代入并整理要得到原方程 axbygcd(a,b)就能反推出目标解 x、y 和递归解 x1、y1 的关系。很多教科书直接给结论令 xy1yx1 - [a/b]×y1这里参数交换看起来像魔法追一遍代数变换就清楚了。标准实现长这样int exgcd(int a, int b, int x, int y) { if (b 0) { x 1; y 0; return a; } int d exgcd(b, a % b, y, x); y - (a / b) * x; return d; }递归到底后 x1,y0 对应方程 a×1b×0a回归时逐层修正。算一个具体的例子求 30x12y6 的解。302×126先递归求 exgcd(12,6)而 122×60所以 exgcd(12,6) 返回 x1,y0 表示 12×16×012。返回上一层时修正30×012×112再修正一次得到 30×112×(-2)6所以 x1,y-2。手动推两遍就能完全吃透这个递归结构。4.3 模逆元gcd 在ax ≡ 1 (mod m)场景里的真面目exgcd 最频繁的实战应用之一就是求模逆元。当我们要解线性同余方程 ax ≡ c (mod m)处理方式取决于 gcd(a,m) 与 c 的关系如果 gcd(a,m) 不整除 c方程无解如果整除方程等价于 (a/g)x ≡ c/g (mod m/g)这时 a/g 与 m/g 互质存在模逆元可以用 exgcd 求出逆元再乘以右侧。模逆元本身可以这样定义满足 ax ≡ 1 (mod m) 的整数 x称为 a 在模 m 意义下的逆元。存在条件就是 gcd(a,m)1。用 exgcd 解 axmy1取 x 并对结果取模就能得到逆元。举个简单例子5x ≡ 3 (mod 8)。gcd(5,8)1exgcd 可得 5×58×(-3)1所以 5 的逆元是 5x ≡ 3×515 ≡ 7 (mod 8)。除了竞赛题模逆元在现代加密算法里是核心原语之一。分数的模运算、同余方程组、某些哈希和随机数生成器都会用到它。这也回答了一个很多人问过的问题学 exgcd 到底有什么用答案是它把“求最大公约数”这个基础运算变成了“解方程”的工具覆盖面比表面看起来大得多。5. 手写实现时的边界检查以及几类非常经典的变种题5.1 0、负数、大数、浮点数这几个边界别想当然gcd/lcm 看似简单边界条件却常常让人翻车我把最典型的整理成一张表边界场景数学约定/工程惯例备注gcd(a, 0)结果为 a循环终止条件依赖它gcd(0, 0)约定为 0数学上未定义程序里要显式处理负数参与计算gcd 结果通常取非负值C 的老版 __gcd 对负数行为不一大整数使用 64 位或大数类型32 位 int 在 lcm 场景非常容易爆浮点数不要直接对浮点数做 % 运算需要自己定义 gcd 的浮点语义或换思路一个常见问题是负数的 gcd。数学定义里约数可以是负数但我们通常约定 gcd 取正。实现时可以先对输入取绝对值再计算。Python 的 math.gcd 已经处理了负数逻辑C 的 std::gcd 在 C17 里也明确返回非负值但老编译器里广泛使用的 __gcd 行为并不统一跨平台时要注意。5.2 经典变种一已知 gcd 和 lcm求原数这类题非常经典给定 gcd(x,y)glcm(x,y)l求满足条件的 x、y 对。核心推导是设 xg×pyg×q因为 gcd 已经把公共因子提出去了所以 p 和 q 必然互质。又因为 lcm(x,y)g×p×ql所以 p×ql/g。问题变成找互质数对 (p,q)使得 p×q 等于 l/g。这个转化是整道题的关键。剩下就是枚举 l/g 的因子检查两个因子是否互质。如果 l/g 不是整数直接无解如果 gl也无解。这类题能考的角度很多比如 x、y 有顺序的时候要乘 2或者需要输出所有合法解而不是只数个数。5.3 经典变种二区间 gcd 与 gcd 分块另一个高频考法是数组上的 gcd 查询。给定一个数组多次询问某个区间 [l,r] 上所有数的 gcd。gcd 满足结合律所以可以用线段树维护每次查询 O(log n)也可以用稀疏表做 O(1) 查询代价是预处理 O(n log n)。这里有一个有趣的单调性质固定左端点随着右端点右移区间 gcd 只会变小而且最多变化 O(log V) 次。因为每次变化至少让结果除以 2。所以很多题会问“有多少个子数组的 gcd 等于某个值”暴力枚举右端点配合二分或双指针就能压到 O(n log V)。这类题看着花哨底层考的其实就是欧几里得算法的步数上界理解复杂度的来源之后解法是水到渠成的。5.4 经典变种三同余方程和“取模相关”的复合题还有一类题目把 gcd 和取模运算组合起来。比如给定 a、b、m问有多少个 x 使得 gcd(ax, b) 的某个性质成立或者求 gcd(ax, bx) 的最大值。这类题的常规突破口是发现 gcd(ax, bx) gcd(bx, a-b)。因为两边同加 x 后差保持不变而 gcd 的变化只取决于其中一个数与差的关系。于是问题常常转化为枚举 a-b 的因子再去检验条件。这类题看起来和 lcm 没直接关系但处理思路完全建立在“gcd 的代数性质”上。如果对辗转相除法的证明只停留在“会背代码”的程度遇到这种变形会非常痛苦。所以我在带新人时反复强调不要光记代码把 gcd(a,b)gcd(b,a mod b) 的推导吃透变种题才能立得住。5.5 实测笔记标准库的坑和不同语言行为的差异最后分享一些实测层面的观察。C17 引入了 std::gcd 和 std::lcm位于 头文件C14 时代大家还在用编译器自带的 __gcd但它既不属于标准库负数行为也没被明确规定。Python 3.9 之前没有 math.lcm但 math.gcd 一直有如果要在老版本里求 lcm需要自己用 a // gcd(a,b) * b 封装。Java 的 BigInteger 自带了 gcd但普通 long 并没有标准库 gcd 方法需要手写。性能方面标准库实现通常经过了充分优化工程代码里我的建议是直接调标准库不要在业务代码里重复造轮子。只有学习、竞赛或者特殊平台限制没有标准库可用时再手写欧几里得算法。手写时注意把返回类型设计成至少 64 位很多“莫名其妙变成负数”的 bug 根源就是 int 溢出。我在实际项目里遇到最频繁的问题其实就是负数和大数这两件事。如果你也需要处理超出 int 范围的数据我的建议是尽早换大整数类型或者直接用 Python别在 int 边缘反复横跳如果你在维护一个老项目看到手写的 gcd 函数最好先确认它的入参类型和负数处理方式再决定要不要继续用。gcd/lcm 的代码量很小但它在代码里扮演的角色往往比看起来重要得多值得多花几分钟把这些边界想清楚。