说个有意思的现象越是基础的算法越容易在真正动手时翻车。最大公约数和最小公倍数大家中学就学过概念刷题网站上也属于“入门第一课”但真到了面试手写代码、或者竞赛里卡时间的时候能把边界情况一次写对的人并不多。我自己在面试候选人时常常先让写一个gcd(a, b)——这道题能暴露出很多问题递归出口写对没有负数进来怎么办a % b和b % a到底哪个是循环条件更别提往后延伸的最小公倍数溢出问题。所以这篇文章干脆把最大公约数最小公倍数的完整算法模板整理出来从原理到代码从基础到扩展场景一次性说透适合正在准备算法面试的人、竞赛选手还有那些觉得“我会调math.gcd就行”但心里其实没底的朋友。1. 为什么算法模板需要单独写一版从“会调库”到“能默写”很多人第一反应是最大公约数不是一行math.gcd就完了吗确实Python 3.9以后自带math.gcdC从C17开始有std::gcdJava的BigInteger里也有现成的。那为什么还要自己准备一套模板原因有三每一个都在实际场景里真实遇到过。1.1 面试官要的不是结果是你的推导过程我模拟面试的时候见过太多这样的候选人张口就说“我用辗转相除法”代码也写对了但一问“为什么gcd(a, b) gcd(b, a % b)成立”就卡住了。更常见的情况是递归写法出口处理得模棱两可——有人写if b 0: return a有人写if a % b 0: return b这两种在大多数情况下结果一致但遇到a b或者b 0的输入时行为完全不同。算法模板的本质不只是“能跑”而是你要理解每一行存在的理由才能在高压环境下临场变形。1.2 竞赛和Online Judge里没有“调库”这个选项很多竞赛环境尤其是偏向算法素养的老牌OJ不允许或者不鼓励直接调内置函数而且模板题考察的就是你的手写能力。再者有些语言的内置函数有隐藏的性能差异——比如某些版本的Python里math.gcd是纯C实现速度确实快但它无法帮你处理自定义场景比如求整个数组的最大公约数时顺便记录中间结果、或者实现扩展欧几里得求逆元。所以一套干净、无依赖、经得起边界测试的手写模板是算法基本功的压舱石。1.3 一套模板覆盖三族问题最大公约数和最小公倍数从来不是孤立知识点。从它们能延伸出三族高频问题一是分数化简把分子分母同时除以gcd二是判断整除关系gcd(a, b) b则说明b整除a三是扩展欧几里得求解模线性方程——这直接通向模逆元。如果只记住一个“辗转相除”的公式后面这些扩展就都要重新推导。所以我建议你手头常备的不是一个「函数」而是一整套「模板族」围绕gcd这个核心向外展开。我把这套模板的定位总结成三个词可默写、可解释、可变形。可默写指不查资料能在两分钟内写完可解释指每个边界条件都能说出道理可变形指从普通gcd能快速切换到扩展gcd、多参数gcd、以及带模运算的版本。后面几节就围绕这三点展开。2. 辗转相除法的底层逻辑取模为什么能一圈圈缩小问题2.1 从“整除关系”出发看算法的几何意义想象你有两根绳子长度分别是a和ba ≥ b 0想找一根最长绳子使得它能同时正好量完这两根——这就是最大公约数。最朴素的思路是暴力从b往下试但数据一大就废了。辗转相除法的聪明之处在于一个关键观察如果b能整除a那b就是答案如果a除以b余数为r那么任何能同时整除a和b的数也一定能同时整除b和r反过来也一样。所以gcd(a, b) gcd(b, a % b)问题规模从(a, b)缩小到(b, r)而r是严格小于b的非负整数接着再递归缩小。这个过程的几何版本就是古希腊人量线段的方法用短边去量长边余下不足一段的部分再用这段残余去量短边——所以算法也叫欧几里得算法。2.2 数学上的严谨证明为什么等式两边“同一组公约数”证明其实不复杂。设a k*b r其中k a // b0 ≤ r b。先证明左边 ≤ 右边设d是a和b的公约数则d | a且d | b因为r a - k*b所以d | r于是d也是b和r的公约数。再证明右边 ≤ 左边设d是b和r的公约数则d | b且d | r因为a k*b r所以d | a于是d也是a和b的公约数。两边互为子集说明(a, b)和(b, r)的公约数集合完全一致当然最大公约数也相等。这个“公约数集合不变”的视角特别重要它解释了为什么这个算法对负数也有一定的宽容度——只要你保持“公约数集合相同”的性质符号问题是可以在最后处理的后面第5节细说。2.3 递归模板与迭代模板的取舍先上最经典的递归模板def gcd(a: int, b: int) - int: if b 0: return a return gcd(b, a % b)这个写法最简洁也最接近数学定义。但在工程上我喜欢用迭代版def gcd(a: int, b: int) - int: while b ! 0: a, b b, a % b return a迭代版的好处有两个。第一没有函数调用栈Python里递归深度默认限制在1000层左右虽然gcd的递归深度通常到不了1000但在极端数据比如两个相邻的斐波那契数下深度也就是几十层真正不需要担心——可万一你接手的工程改过递归限制或者用了很深的包装迭代版永远更稳。第二迭代版更容易做“中间状态观察”比如我想记录每一步的商和余数来推导扩展欧几里得的系数迭代版天然适合保存历史。这里有一个很多人忽略的细节循环条件里的b ! 0和交换顺序。a, b b, a % b这行左侧的a会被更新为旧的b右侧的a % b用的是旧的a和旧b——Python的元组赋值保证了两个值同步取旧值不会有次序问题。但如果你自己写临时变量就很容易写错成先用新a去模b导致死循环。2.4 复杂度分析为什么它这么快很多人以为取模运算很慢、递归次数很多。实际上算法每次迭代都会让“两个数里较小的那个”至少减小一半——严格说当a b时a % b a / 2恒成立取b和a-b的两种极端情况都能验证。所以迭代次数是O(log(min(a, b)))对64位整数来说最多也就跑几十次循环效率上完全没有压力。这个性质也是“用辗转相除法求gcd”远胜于“逐个试除”的根本原因。3. 最小公倍数不是独立算法而是gcd的“一步变形”3.1 从质因数分解的视角理解两个数的关系最小公倍数lcm的定义不需要再多说。关键是记住一条黄金公式lcm(a, b) * gcd(a, b) a * b推导思路来自质因数分解把a和b都拆成质因数幂的乘积gcd取每个质因数幂的较小指数lcm取较大指数。同一质因数在两个结果里的指数之和恰好等于它在a和b里指数之和——所以乘积相等。那么这个公式的实际价值是什么它告诉我们**lcm不需要单独写算法只要gcd写对了lcm就是一行代码。**这也是为什么几乎所有算法模板里lcm都是基于gcd实现的而不会去单独发明一个“更直接”的算法。3.2 先除后乘那个能救命的小细节直接写a * b // gcd(a, b)看着没问题但a * b可能溢出。比如在Java里两个int相乘直接翻车Python虽然不会溢出无限大整数但在C里这是真实事故高发区。更隐蔽的是即使不溢出a * b的结果也可能远超你最终需要的范围增加不必要的转换成本。所以模板里必须写成def lcm(a: int, b: int) - int: return a // gcd(a, b) * b先除后乘先让a除以gcd把大数缩小到互质状态再乘以b。比如a 1998b 2000gcd 2直接乘是3,996,000如果数字再大一些先除的优势会非常明显——中间结果小了整整两倍。如果你担心整除精度gcd本来就整除a因为gcd(a, b)是a的约数。注意在C中如果a和b都是int而a // gcd(a, b) * b的结果可能超过int范围你要主动把其中一个数转成long long否则本质问题没有解决只是把溢出的时机推迟了。3.3 lcm的常见应用场景分数化简与周期问题工程和竞赛里lcm最常见的用法有三个分数通分两个分母的lcm就是最小公分母这比盲目相乘再约分要优雅得多。循环周期对齐两个事件分别每隔m天和n天发生问下一次同时发生在哪一天——答案就是lcm(m, n)。数论中的阶梯题比如求[1, n]的所有数的最小公倍数或者判断某个数是否能被一组数同时整除核心都是多次调用lcm。这里就引申出一个频繁出现的坑多个数的lcm不是两两lcm的简单套娃得注意顺序和溢出。例如def lcm_many(nums: list) - int: res 1 for num in nums: res res // gcd(res, num) * num return res每一步都先除后乘可以让中间结果尽量小。但即便如此多个数的lcm增长速度极快前30个自然数的lcm是一个巨大的数你在实际使用时要评估数值范围是不是放得下。3.4 配套工具因数分解和质数筛关联如果你频繁需要lcm相关的推导一个质因数筛会是很好的配合工具。比如要算C(200, 100)这类组合数它可能超过普通长度类型但你可以用质因数幂次来做精确运算——这本质上是“把指数拼起来”的lcm思想。你的模板库如果能和质数筛打通后面做很多数论题都会顺很多。4. Stein算法与扩展欧几里得模板树的另外两根枝干4.1 Stein算法不用取模也无惧大数辗转相除法好归好但有个小隐患——它依赖取模运算。在某些嵌入式环境或者特别大的整数比如几千位的BigInteger里取模运算本身可能代价不低。Stein算法也叫二进制GCD算法换了个思路只用移位和减法利用“奇偶性”来缩减问题。算法规则是如果a和b都是偶数gcd(a, b) 2 * gcd(a 1, b 1)如果a是偶数b是奇数gcd(a, b) gcd(a 1, b)如果两者都是奇数gcd(a, b) gcd((a - b) 1, b)经过交换保证a ≥ b基础情形某数为0时返回另一个数代码实现def gcd_stein(a: int, b: int) - int: 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: while b 1 0: b 1 if a b: a, b b, a b (b - a) 1 return a shift实际刷题里普通整数用辗转相除法就够了Stein算法更多是作为概念储备和“大数运算”“位运算技巧”联系在一起。面试时如果聊到高精度或者二进制优化能说出Stein算法的存在和核心分支是一个很好的加分项——但我不建议在模板里把Stein算法当首选除非环境真的不支持取模。4.2 扩展欧几里得从“求最大公约数”到“求整数解”扩展欧几里得算法的目标是找出一组整数x, y使得a * x b * y gcd(a, b)这个等式是线性丢番图方程的基础形态。为什么它会出现在“最大公约数最小公倍数算法”的生态里因为两者共享几乎一模一样的递推骨架辗转相除的每一步都在“换元”。扩展欧几里得就是在回归递归回溯的过程中把每一层的系数拼回来。def exgcd(a: int, b: int): 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这三个返回值分别是gcd、x系数、y系数。验证一下比如exgcd(30, 12)能得到g6, x1, y-2因为30 * 1 12 * (-2) 6。这个模板的价值非常大模逆元要求a在模n下的逆元等价于解a * x ≡ 1 (mod n)即a * x n * y 1当gcd(a, n) 1时x就是逆元。判断线性丢番图方程是否有解a*x b*y c有整数解当且仅当c % gcd(a, b) 0。求同余方程组的统一解中国剩余定理的工程实现里扩展欧几里得是核心步骤。如果面试官只让你写gcd你背的模板止步于此可能还不够他很可能追问一句“能不能同时求出一组系数”所以我把gcd和exgcd放进同一套模板树里它们是孪生算法。4.3 多参数gcd与流式处理竞赛和工程里有时候需要对一个数组求整体gcd。最朴素的写法from functools import reduce def gcd_all(nums) - int: return reduce(gcd, nums)复杂度分析数组长度N每步gcd的复杂度是对数级别所以总体是O(N log M)。注意一个性质整体gcd一定不大于数组里的最小元素而且计算过程中数值会单调不增。当数值已经下降到1时可以提前终止——因为gcd永远不会从1再变大这是个小优化点。同理多参数lcm也可以用reduce但每一步都要重新评估溢出风险。5. 实战中的边界陷阱与模板落地负数、零、溢出和竞赛经验5.1 零的处理约定、陷阱与标准行为数学上gcd(0, n)一般定义为n因为任何非零数都能整除0而0的最大约数就是它“最大的约数”这个约定要和“0不能做除数”区分清楚。在代码层面gcd(0, 0)有的语言定义返回0有的定义未定义。Python的math.gcd(0, 0)返回0。我的模板中递归出口b 0 return a恰好覆盖了gcd(a, 0) agcd(0, 0)就返回0和Python官方行为一致。lcm要更小心任何数乘0的lcm都是0。这符合lcm(a, 0) 0因为0是任何非零数的倍数但“所有数的公共倍数里最小的”这个定义下0其实必然存在所以直接返回0是对的。我的模板里由于gcd(a, 0)alcm(a,0) a // a * 0 0自动正确。但要注意有些题目会把“0”作为非法输入排除所以你在写题解的时候先明确题目约定再去套模板。5.2 负数怎么处理取绝对值还是保留符号数学上最大公约数通常指正整数但很多题目会丢给你负数。两种常见策略入口处取绝对值推荐def gcd(a, b): a, b abs(a), abs(b) while b: a, b b, a % b return a这样行为最可预期也符合“最大公约数为正”的惯例。信任取模运算在C/C里的截断语义 这和语言相关C里-7 % 3 -1Python里-7 % 3 2两种语言对负数的取模结果不同使用辗转相除法时即使过程会“绕路”最终辗转下来还是会收敛到符号不确定的数。所以最稳的方案仍然是入口取绝对值。5.3 溢出与数值范围不只是换long long这么简单如果说负数是一个“小坑”溢出就是“大坑”。尤其在做lcm的时候a * b很容易爆。我已经强调过先除后乘现在补充一点即使先除后乘结果也可能超出目标数据类型你怎么提前判断对于Python没必要但C/Java里可以这样long long lcm(long long a, long long b) { return a / std::gcd(a, b) * b; // 前提是一定要用 long long }如果你真的需要判断是否溢出一个技巧是a / gcd(a, b) LLONG_MAX / b则必然溢出。这类判断在一些“输出两数最小公倍数数据范围到1e18”的题目里数见不鲜。5.4 我在面试和竞赛里用这套模板的实测体会说点经验之谈。面试时写gcd我建议第一版直接上迭代版因为它不需要向面试官解释“递归栈深度”而且好改写成扩展欧几里得。如果面试官追问“能再优化吗”你再引Stein算法如果你一开始就写了个很炫技的Stein算法反而容易被追问到“为什么用移位代替取模不会出错”给自己挖坑。其次最好在写完gcd之后主动说一句“基于这个lcm只需要注意先除后乘”这能展示你考虑溢出问题的工程素养。竞赛实战里我一般会把这套模板收进自己的代码仓库然后在需要用的时候直接粘贴。但请注意粘贴前先看一眼题目对数据范围的定义特别是“0”“负数”“大数”三个边界。我见过有人拿了模板就套结果被一组lcm(0, 5)的数据整懵了——模板没错是读题出了问题。5.5 一个常年被忽略的增强记录最大公约数的同时算线性组合最后补一个进阶玩法有时候你想知道“到底哪一组x, y让a*x b*y gcd(a, b)成立”这就是前文说的exgcd。我的实际建议是在模板库里gcd和exgcd放一起并且注释里写清楚两者的关系“exgcd在递归返回时用的递推式是x y1, y x1 - (a // b) * y1”。这个递推式怎么来的其实很简单在下一层我们有g b * x1 (a % b) * y1而a % b a - (a // b) * b所以g b * x1 (a - (a // b) * b) * y1 a * y1 b * (x1 - (a // b) * y1)。于是上面一层取x y1, y x1 - (a // b) * y1。每次手推一遍这个式子你会彻底根治“背不下来扩展欧几里得代码”的老毛病。这些话我常拿来在带新人的时候讲因为实操里太容易踩了模板不是拿来背的是拿来理解的。理解了那行递推式之后你想忘都忘不掉。