1. 从一道看似简单的算法题说起先说一个我在面试中经常问的题目请写出两个函数一个求最大公约数GCD一个求最小公倍数LCM。听起来是小学生内容但真的让候选人在白板上手写能一次写对的人不到一半。有人只会暴力循环有人记得欧几里得算法却说不清为什么递归边界是b 0还有人写最小公倍数时直接a * b / gcd(a, b)完全没意识到整数溢出的风险。这类题目之所以经典是因为它考察的不是背没背过模板而是三个底层能力数学恒等式的理解能力、算法复杂度的分析能力、边界条件的处理能力。最大公约数有至少三种典型解法最小公倍数有两条完全不同的实现路径它们的背后对应着枚举思想、减治思想、公式推导思想这些恰恰是更复杂算法比如扩展欧几里得、同余方程、RSA 中的模逆元计算的地基。这篇文章我不打算只罗列代码而是把每一种算法的原理、推导过程、时间复杂度、适用场景、以及我实际写代码时踩过的坑全部讲透。看完之后你不仅能应付面试还能明白为什么递归终止条件是b 0这种别人总结好的结论是怎么来的。2. 最大公约数暴力枚举、欧几里得与更相减损术2.1 暴力枚举法最直白但最容易被忽略的解法先看最没有技术含量的写法从min(a, b)开始逐个往下试找到第一个能同时整除a和b的数它就是最大公约数。int gcdByEnum(int a, int b) { int g min(a, b); while (g 0) { if (a % g 0 b % g 0) { return g; } g--; } return 1; }复杂度是 O(min(a, b))最坏情况下比如gcd(1, 100000)从 1 开始往上找其实很快但如果求gcd(99991, 99989)这种两个大质数就要循环将近十万次才能得到 1。虽然这算法性能很差但我强烈建议你不要小看它。在我的日常工作里它有两个不可替代的作用。第一当基准测试用暴力枚举的结果去验证欧几里得等优化算法的正确性尤其在写新代码或做代码审查时拿暴力实现当标准答案跑随机数据比对比人眼检查靠谱得多。第二面试展示思维层次面试官问算法题最忌讳的是上来就写最优解因为你跳过了思考过程。你先给出暴力解再说这个复杂度是 O(min(a,b))在大数据量下不可行我可以继续优化这充分展示了你分析问题、逐步优化的工程思维。另外暴力枚举还有一个副作用它天然处理了a或b为 1 的情况。任何一个数和 1 的最大公约数都是 1min(a, b)也是 1第一次循环就返回 1逻辑上没有任何特殊分支需要处理。2.2 欧几里得算法两千年不变的经典欧几里得算法就是我们常说的辗转相除法核心公式是gcd(a, b) gcd(b, a % b)写成代码非常短// 递归版 int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } // 迭代版推荐 int gcdIter(int a, int b) { while (b ! 0) { int r a % b; a b; b r; } return a; }但要真正理解它得先搞清楚一个关键问题为什么取模之后公约数集合不变设a b * q r其中r a % b。如果存在一个数d能同时整除a和b那么d也一定能整除r a - b * q因为a和b * q都能被d整除。反过来如果d能同时整除b和r那么d也一定能整除a b * q r。这就证明了(a, b)和(b, r)的公约数集合完全相同所以它们的最大公约数也必然相等。这样不断把问题规模缩小(a, b) - (b, a % b)余数r严格小于b最终余数变成 0此时gcd(x, 0) x递归结束。这里的边界理解很关键——很多人死记b 0但不理解为什么。从数学定义来说gcd(x, 0) |x|因为任何数都能整除 0而能整除x的最大数就是x本身。时间复杂度上欧几里得算法的收敛速度是指数级的最坏情况是斐波那契数列相邻两项比如gcd(144, 89)的取模序列长度等于斐波那契数增长到 n 的索引数总体复杂度为 O(log min(a, b))。用具体数字感受一下求gcd(1000000, 1)暴力枚举要循环一百万次辗转相除法只做两次取模就得到结果1000000 % 1 0直接返回 1。差距就是这么大。我个人的偏好是生产代码里用迭代版面试时先写递归版并主动解释递归深度。欧几里得的递归深度大约是对数级别所以不容易栈溢出但在一些嵌入式编译器上递归调用仍有栈开销迭代版更稳妥。这一点在第五章会展开说。2.3 更相减损术减法思维与 Stein 算法的渊源更相减损术的历史比欧几里得算法还早中国古代数学著作《九章算术》里就有记载。它的核心公式是当 a b 时gcd(a, b) gcd(a - b, b)直觉上很容易理解a和b的共同因子一定也是a - b的因子反过来也一样。证明思路和欧几里得算法几乎完全一致只是把取模换成了减法。int gcdBySubtraction(int a, int b) { while (a ! b) { if (a b) a - b; else b - a; } return a; }这代码有一个隐藏 bug 风险循环终止条件是a b。当a、b都是正数时这个条件是能正确结束的但如果输入为 0 或负数就麻烦了。所以使用前必须做绝对值处理a abs(a); b abs(b);并且要单独处理a 0 || b 0的情况否则a 0时会进入死循环。更相减损术的复杂度退化问题非常严重。最坏情况是gcd(1, 100000)100000 - 1减了九万九千九百九十九次每次只把大数减少 1整体复杂度 O(max(a, b))。虽然平均来说比暴力枚举略好但本质上不是一个稳定性好的算法。不过更相减损术有一个重要价值它是 Stein 算法的思想源头。Stein 算法在 1967 年提出专门针对大整数场景核心优化是用移位代替取模如果a、b都是偶数gcd(a, b) 2 * gcd(a/2, b/2)如果a是偶数、b是奇数gcd(a, b) gcd(a/2, b)如果两者都是奇数再用更相减损术这样就把对大整数的除法运算全部换成了右移和减法运算。在处理几百位的大整数时比如加密算法里的超大数取模的开销极高Stein 算法的优势非常明显。所以更相减损术不是没用而是要配合其他优化手段使用单纯裸写它在现代工程中几乎没有价值。三种最大公约数算法的对比算法核心操作时间复杂度稳定性适用场景暴力枚举取模O(min(a,b))最稳定正确性显然测试基准、小数据欧几里得算法取模O(log min(a,b))高效稳定绝大多数日常场景更相减损术减法O(max(a,b))退化严重Stein 算法的基础3. 最小公倍数的两种算法公式推导与直接枚举3.1 公式法用最大公约数一步到位最小公倍数和最大公约数之间有一个非常优美的恒等式a × b gcd(a, b) × lcm(a, b)所以求最小公倍数最常用的方法是lcm(a, b) a / gcd(a, b) × b为什么这个等式成立用质因数分解来看最直观。假设a p1^e1 * p2^e2 * ...b p1^f1 * p2^f2 * ...最大公约数取每个质因子的较小指数最小公倍数取较大指数。那么gcd * lcm中每个质因子的指数就是min(e, f) max(e, f) e f恰好等于a × b中每个质因子的指数之和。所以恒等式成立。代码实现很短int lcm(int a, int b) { return a / gcd(a, b) * b; }注意这里我特意写了a / gcd(a, b) * b而不是a * b / gcd(a, b)。这是我在实际开发中踩过的坑如果先算a * b再除以gcd中间结果可能溢出。比如a 100000, b 99999两者互质a * b 9999900000已经超出 32 位整数的上限2147483647了直接溢出变成负数。但如果先做除法a / gcd(a, b) 100000 / 1 100000再乘以99999结果虽然还是超过 32 位范围但至少在除法这一步不会溢出。更稳妥的方案是直接全部用long longlong long lcm(long long a, long long b) { return a / gcd(a, b) * b; }现实中很多代码在 32 位整数范围内跑得好好的一旦数据规模升级就出诡异问题原因往往就是这种先乘后除的写法埋下的雷。3.2 直接枚举法适合小数据量场景的朴素思路第二种求最小公倍数的方法是枚举。最朴素的思路是从 1 开始逐个往上找第一个能同时被a和b整除的数就是公倍数。但更高效的枚举方式是从max(a, b)开始每次累加max(a, b)这样可以保证枚举到的每个数都是较大数的倍数只需要检查是否能被较小数整除即可int lcmByEnum(int a, int b) { int step max(a, b); int l step; while (l % a ! 0 || l % b ! 0) { l step; } return l; }你可能会问为什么不每次加 1 检查因为那样会做大量无效判断。从max(a, b)开始每次加max(a, b)枚举的次数最多是min(a, b)次整体复杂度 O(min(a, b))。举个例子求lcm(7, 13)从 13 开始加13 不行26 不行39 不行……到 91 才行一共枚举 7 次恰好等于较小的那个数 7。而如果每次加 1要枚举 91 次。差距一目了然。那枚举法是不是就完全没用呢也不是。在某些场景下它有独特价值当a、b都很小几十以内枚举法写起来最直观逻辑最简单不容易出错。当你已经算出了最大公约数但不想用除法比如在某种受限环境下除法成本很高枚举法可以作为替代。小学奥数教学场景里枚举法能帮助学生理解公倍数的含义建立数感。但如果a、b都很大且互质枚举法会退化到 O(min(a, b))比如求lcm(99991, 99989)要从99991一直加到99991 * 99989这个数字接近 100 亿程序基本跑不完。所以工程上公式法几乎总是优于枚举法枚举法更多是教学和辅助验证的价值。两种最小公倍数算法的对比算法依赖时间复杂度代码复杂度使用场景公式法gcdO(log min(a,b))极低几乎所有工程场景枚举法循环O(min(a,b)) 最坏低小数据、教学演示、无除法环境4. 从两个数到多个数算法推广与实战选型4.1 多个数求最大公约数的迭代实现实际开发中我们经常遇到的不只是两个数而是一堆数同时求最大公约数比如分数约分时需要计算分子、分母、公因数的最大公约数。好消息是最大公约数运算满足结合律gcd(a, b, c) gcd(gcd(a, b), c)也就是说先用任意两个数算出公约数再拿这个结果和第三个数算依次迭代下去即可int gcdArray(const vectorint nums) { if (nums.empty()) return 0; int g nums[0]; for (int i 1; i nums.size(); i) { g gcd(g, nums[i]); } return g; }这个实现的复杂度是 O(n log M)其中 n 是数组长度M 是最大数值。g在迭代过程中严格不增而且一旦g变成 1就可以提前跳出循环——因为任何数和 1 的最大公约数都是 1后面的所有计算都是无用功。这是一个非常实用的性能优化int gcdArray(const vectorint nums) { if (nums.empty()) return 0; int g nums[0]; for (int i 1; i nums.size() g ! 1; i) { g gcd(g, nums[i]); } return g; }这个优化在随机数据上尤其明显。数组里只要有两个互质的数后续所有元素都不需要再计算了直接返回 1。4.2 多个数求最小公倍数的顺序计算最小公倍数对多个数同样满足结合律lcm(a, b, c) lcm(lcm(a, b), c)对应的迭代实现long long lcmArray(const vectorint nums) { if (nums.empty()) return 0; long long l nums[0]; for (int i 1; i nums.size(); i) { l lcm(l, nums[i]); } return l; }我在这里要特别强调一个很多人容易犯的错误三个数求最小公倍数不能写成a * b * c / gcd(a, b) / gcd(b, c)。这个公式只在特定条件下成立比如求lcm(2, 3, 5)按错误公式算2 * 3 * 5 / 1 / 1 30恰好等于正确答案 30。但换一组数就不行了比如lcm(4, 6, 9)错误公式算出来是4 * 6 * 9 / 2 / 3 36而正确答案是 36。咦这个例子凑巧也对。我再换一组lcm(4, 6, 10)错误公式4 * 6 * 10 / 2 / 2 60正确答案是 60。好像还是对的实际上这个错误公式之所以看起来经常对是因为它本质上是把每个质因子的指数重复算了。真正暴露问题的情况是三个数中有两个数共享了最大公约数中未包含的因子时。我构造一个反例lcm(8, 12, 18)。真确答案8 的质因数分解是 2^312 是 2^2 × 318 是 2 × 3^2所以 lcm 是 2^3 × 3^2 72。用错误公式8 * 12 * 18 / gcd(8, 12) / gcd(12, 18) 1728 / 4 / 6 72。结果还是对的好吧让我仔细想一下。这个错误公式其实在某些形式下可以用更一般化的公式纠偏但通常正确的做法就是两两迭代。直接演示一个必错场景lcm(6, 10, 15)。正确答案62×3102×5153×5lcm2×3×530。用错误公式6 * 10 * 15 / gcd(6,10) / gcd(10,15) 900 / 2 / 5 9090 ≠ 30这就出错了。所以结论很明确对于多个数求最小公倍数老老实实两两迭代不要试图用一个复杂的组合公式一把梭。两两迭代不仅思路清晰而且每一步都能保证中间结果是真实的最小公倍数不会出现局部正确全局错误的隐藏 bug。4.3 大整数场景下的溢出防护与选型建议写算法题或业务代码时一个隐藏的坑是中间结果的溢出。前面提到的a / gcd(a, b) * b已经规避了第一步的溢出风险但累乘过程中依然可能溢出。比如lcmArray({1000000007, 1000000009, 999999937})这三个数两两互质按两两迭代算出来的中间结果会迅速膨胀到天文数字即使是long long也扛不住。这种情况下就必须上高精度库或大数类型。我整理了一个实战选型建议表数据规模推荐方案理由32 位 int 范围内int gcd gcdIter; lcm a / gcd * b简单高效注意用 long long 存放 lcm 结果64 位 long long 范围内long long gcd 先除后乘规避乘法溢出lcm 可能超界需自行判断大整数几百位Stein 算法 BigInteger 库避免大数取模的巨大开销浮点数不适用gcd/lcm 定义在整数环上浮点数请用别的方法还有一点容易被忽略数据规模不是唯一标准计算频率也很重要。如果在一个嵌入式环境里每秒要调用几十万次 gcd函数调用本身的开销都不可忽视这时候建议用迭代版、内联函数、避免递归栈开销。我自己在做性能敏感模块时甚至会把欧几里得算法手工展开成循环并加inline关键字。5. 面试与工程中的加分细节边界、溢出与表达5.1 边界条件0、负数、1 的处理标准很多代码能跑通正常用例却在边界条件上翻车。最大公约数和最小公倍数的边界条件有几个业界通用的约定关于 0数学上gcd(0, 0)没有定义但很多语言和库中约定返回 0。gcd(a, 0) |a|这是普遍接受的定义所以欧几里得算法的递归边界b 0返回a天然与这个定义一致。而lcm(a, 0)呢从公式a / gcd(a, 0) * 0 a / |a| * 0 ±0 0出发几乎所有实现里 lcm 遇到 0 都返回 0。这个结果是否符合直觉另说但至少和公式推导是一致的。关于负数最大公约数通常定义为正数。所以函数的正确做法是先取绝对值再计算int gcd(int a, int b) { a abs(a); b abs(b); while (b ! 0) { int r a % b; a b; b r; } return a; }很多面试候选人栽在这个点上他们写的代码在输入负数时返回负数从数学定义讲这是错误的。关于 1任何数和 1 的最大公约数都是 1任何数和 1 的最小公倍数是这个数本身。如果你的 gcd 实现是欧几里得算法这些情况能自动正确处理但如果用更相减损术就必须要小心a b的终止条件与 0/1 的组合所以更相减损术的实践中必须先做绝对值和零值检查。5.2 递归改迭代的必要性欧几里得算法的递归版只有一行非常优雅。但工程上我更推荐迭代版原因有两个。第一递归深度虽然是对数级别但在特殊输入下依然可能出问题。比如求gcd(1, 2147483647)递归只进行两层就结束了完全没问题。真正要注意的是在某些实现了循环优化的高级语言中递归调用栈需要保存大量上下文如 JS 的调用栈深度有限制。虽然欧几里得很安全但惯性地写递归是一种坏习惯一旦扩展到其他递归算法就容易被坑。第二迭代版对编译器更友好。虽然现代编译器对尾递归有一定优化能力但远不如直接写循环来得确定。C 标准并不强制编译器优化尾递归所以在某些嵌入式或交叉编译环境下递归版会产生比预期更多的栈开销。我一般这么劝身边的朋友递归版用于表达思路迭代版用于生产代码两者都要会写能在面试中边说思路边切换更好。5.3 从这道题延伸出的思考方式这道题最大的价值不在于记住三个算法而在于它背后暴露出的思考范式。我自己带新人的时候经常用这道题训练他们三个习惯第一先问数据范围再写代码。候选人如果一开始就动手写暴力枚举我往往会追问一句如果a和b都是 10 亿呢会思考数据范围的人会主动选择欧几里得算法并在代码注释里写明复杂度。这个习惯在工作里尤其重要——写业务代码时没人告诉你数据有多大你必须自己判断。第二主动分析复杂度。能写出 gcd 的人很多但能说出欧几里得算法最坏情况是斐波那契数列相邻两项的人很少。这个细节能体现你不仅会用还深入理解过。第三关注数学恒等式背后的推导。a × b gcd(a, b) × lcm(a, b)不是靠背的而应该从质因数分解的角度自己推一遍。这种推导能力会在很多意想不到的地方派上用场——比如你以后遇到逆向求未知数的问题、同余方程的问题、甚至图像处理中的像素对齐问题都会用到类似的因式分解和整数性质分析。最后分享一个小技巧。我在做算法题或写库函数时习惯把暴力枚举版和优化版同时写在测试代码里然后用随机数做对拍验证。比如写了个欧几里得算法就生成十万组随机数分别用gcdByEnum和gcd算一遍断言结果一致。这个方法能在几秒钟内帮你发现 99% 的实现错误比任何代码审查都有效。做 gcd、lcm 这类看似简单的函数时不要觉得没必要写测试——越简单的函数越容易被忽略一旦出错影响面反而更大。
)
