看到这个标题就很有共鸣最大公约数和最小公倍数算是算法入门里最经典的一对“老朋友”了。不管是刚学编程准备信奥还是刷LeetCode热身几乎所有人都会先撞到这几行代码。网上讲这个的文章很多但大多数要么只给一个模板要么直接把证明甩你脸上看完能记住的没几个。这篇我换个思路把最大公约数的三种常见算法和最小公倍数的两种求法放在一起拆开揉碎讲清楚每个算法都交代清楚“为什么能这么算”“边界在哪”“坑在哪”最后再补上实际工程和竞赛里怎么选型的经验。想彻底搞懂这块内容的同学这篇可以直接收藏。1. 先搞清楚一件事最大公约数和最小公倍数的关系到底是什么很多人把这两个概念分开记但实际上它们是一对“孪生兄弟”。对于两个正整数a和b假设它们的最大公约数Greatest Common Divisor简称GCD是d最小公倍数Least Common Multiple简称LCM是m那么存在一个非常漂亮的关系式a × b d × m也就是说两个数的乘积等于它们的最大公约数和最小公倍数的乘积。这个式子不是凑巧而是有严格数学推导的。简单理解把a和b各自分解成质因数的乘积gcd取的是每个质因数的“较小指数”lcm取的是每个质因数的“较大指数”两者指数相加正好等于原始的指数和所以乘起来自然相等。这个关系式的价值在于求最小公倍数完全可以借助最大公约数来实现而最大公约数的算法在历史上有过非常多的研究效率高而且稳定。所以大部分时候只要会算gcdlcm就等于a / gcd(a, b) * b注意这个计算顺序先除后乘可以防止溢出后面会详细说。但这不意味着lcm就没有自己的独立算法了——直接分解质因数也能求而且某些场景下反而更直观。接下来我先把最大公约数的三种经典算法讲透再说最小公倍数的两种求法这样整个知识体系就闭环了。2. 最大公约数算法一更相减损术——最古老也最直观的“减法思维”更相减损术是中国古代数学著作《九章算术》中记载的方法比欧几里得算法还要早。它的核心思想特别朴素两个数的最大公约数等于“较大的数减去较小的数”之后得到的差与“较小的数”之间的最大公约数。用数学语言表达就是当a b时gcd(a, b) gcd(a - b, b)。这个式子成立的理由也不难理解任何能同时整除a和b的整数一定能整除它们的差a - b反过来任何能同时整除b和a - b的整数也一定能整除a因为a (a - b) b。所以公约数的集合完全一样最大公约数自然也一样。基于这个原理算法流程就是不断用大数减小数直到两个数相等这个相等的数就是最大公约数。用C实现如下int gcdBySubtraction(int a, int b) { while (a ! b) { if (a b) a - b; else b - a; } return a; }这个算法有个显而易见的缺点如果两个数差距悬殊比如a10000b1那就得循环减9999次性能极差。但它奠定了“通过不断缩小问题规模来解决原问题”的递归思想这是后面所有算法的基础。我在实际讲解这个算法的时候喜欢用一个“切绳子”的类比假设有两根长度分别为a和b的绳子要找能同时把两根绳子都切成整数段的最大长度。更相减损术的过程就是不停地拿长绳子减短绳子把长绳子替换成剩余的部分直到两根绳子一样长。这个“一样长”的长度就是最大公约数。说个实操心得更相减损术虽然效率一般但它在理解“公约数”本质这件事上无可替代。如果你教新手先让他写这个再让他写欧几里得算法他对取模运算的理解会深很多。这比直接甩给他一个gcd模板要有效得多。3. 最大公约数算法二欧几里得算法辗转相除法——竞赛和工程中的绝对主力欧几里得算法也叫辗转相除法是现在应用最广泛的求最大公约数算法。它的核心原理和更相减损术类似但用取模运算代替减法直接实现“大数换成余数”gcd(a, b) gcd(b, a mod b)其中a b为什么这样可以因为取模的本质就是连续减法——a mod b其实就是a不断减去b直到不够再减为止。所以欧几里得算法可以理解为更相减损术的“批量加速版”一次取模运算相当于做了很多次减法。标准递归实现int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }迭代实现实际工程中推荐避免递归栈开销int gcdIterative(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; }关于时间复杂度欧几里得算法的时间复杂度是O(log min(a, b))这里log的底数大约是黄金比例φ ≈ 1.618。也就是说每次取模问题规模至少缩小一个常数倍循环次数非常少。最坏情况出现在两个数是相邻斐波那契数时比如gcd(144, 89)循环次数达到最大但那也只是十几次而已。我在LeetCode刷题时实测过就算a和b都接近int上限约21亿循环次数也基本不超过45次效率极其稳定。这也是为什么所有语言的标准库几乎都内置了gcd实现C17的std::gcdPython的math.gcd底层基本都用的这个算法。避坑提示递归写法虽然简洁但面试写代码时最好改成迭代。很多递归写法在极端情况下栈深度其实还好因为深度只要几十层但有些公司的在线评测系统栈空间设置得很小万一遇到类似情况就会无谓地栈溢出。迭代版本的性能更优也更能体现你对底层原理的理解。4. 最大公约数算法三Stein算法二进制GCD算法——大整数场景下的“特种兵”Stein算法是欧几里得算法的强力补充它抛弃了取模运算只用减法和位运算右移、左移因此在处理超大整数时优势明显。为什么抛弃取模呢因为超大整数比如几百位的十进制数的除法本身很费时CPU的除法指令周期远高于加减法和移位而在高精度计算中“除以2”可以用右移一位完成代价极低。Stein算法的核心规则基于以下四个观察如果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)。如果a和b都是奇数则gcd(a, b) gcd((a - b) / 2, b)利用更相减损术的原理。递归终止条件是a b此时gcd就是a也是b。C实现int gcdStein(int a, int b) { if (a 0) return b; if (b 0) return a; int shift 0; // 提取公共的因子2 while (((a | b) 1) 0) { a 1; b 1; shift; } // 确保a是奇数 while ((a 1) 0) a 1; while (b ! 0) { while ((b 1) 0) b 1; if (a b) swap(a, b); b - a; } return a shift; }这段代码看起来比欧几里得算法复杂但核心思想就是“不断消去因子2把两个奇数的情况转换成减法再除以2”。每次循环至少把一个数缩半整体时间复杂度仍然是O(log max(a, b))级别。适用场景说明普通int范围内的gcdStein算法相比欧几里得算法并没有明显优势有时甚至稍慢因为逻辑分支更多。但在以下场景中Stein算法才是真正的王者高精度大整数计算大数取模一次的成本极其高昂而“除以2”只需要在高精度数组的首位处理一下成本低得惊人。嵌入式等对除法指令敏感的环境某些低端MCU没有硬件除法指令取模运算通过软件模拟会非常慢Stein算法全程只用减法和移位优势巨大。密码学中的大数运算RSA等算法需要大量gcd计算其中操作数往往有几百上千比特。从工程实践角度看如果你只需要在普通程序里求gcd直接用欧几里得算法没错但如果你在做大数运算库或者对性能敏感的系统级开发Stein算法是你必须掌握的备选方案。5. 最小公倍数求法一利用gcd公式法——最通用、最推荐的方案前面提到过关键公式lcm(a, b) a / gcd(a, b) * b。这个式子用起来很简单但有一个非常容易踩的坑先乘a × b再除以gcd在大数场景下会溢出。举个例子a2^31 - 1int最大值b2^31 - 2两者乘积大约是4.6×10^18远超int的表示范围约2.1×10^9直接乘必然溢出。所以标准写法一定是先除后乘int lcm(int a, int b) { return a / gcd(a, b) * b; }这样做的数学依据a / gcd(a, b)和b互为“互质部分”的关系两者相乘不会超出a和b乘积的理论值但在很多情况下不会溢出。什么情况下还是会溢出呢答案是当a和b本身就是接近极限的大整数时它们的lcm可能超出int范围以int类型存储无论如何都会溢出。这时就需要升级为long long或大整数类型而不能只靠调整运算顺序来规避。C标准库风格的完整实现#include numeric #include algorithm long long lcm_ll(long long a, long long b) { return a / std::gcd(a, b) * b; }实操心得在竞赛中处理多组数据的LCM时我习惯将a和b统一提升为long long再做运算并且全程使用long long保存中间结果。很多同学一开始用int存gcd的结果然后转成long long乘结果还是溢出——因为溢出发生在int乘法阶段已经来不及了。正确做法是从头到尾都用更大的类型。另外这个公式还有一个漂亮的性质求多个数的lcm可以两两迭代计算。比如求lcm(a, b, c)可以先算lcm_ab lcm(a, b)再算lcm(lcm_ab, c)。但要注意计算过程中数值可能增长得很快所以务必使用更大范围的数据类型每算一步都尽量先除后乘。6. 最小公倍数求法二分解质因数法——直观但代价更高的路径第二种求lcm的办法是从定义出发先把每个数分解成质因数的幂次积然后对每个质因数取“所有数中出现的最大指数”再乘起来。举个例子求lcm(12, 18)12 2² × 3¹18 2¹ × 3²对质因数2取最大指数2对质因数3取最大指数2所以 lcm 2² × 3² 36。这种方法的直观性极强特别适合用来向初学者解释“最小公倍数到底最小在哪”每个质因数的指数都不能小于任何一个数中该质因数的指数否则无法整除对应数而“最小”意味着恰好取到这些最大指数一个不多一个不少。算法实现上需要先准备素数表可以用埃氏筛或欧拉筛然后对每个数做质因数分解记录每个质因数的最大出现次数#include vector #include map std::vectorint sieve(int n) { std::vectorbool is_prime(n 1, true); std::vectorint primes; is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); for (int j i * i; j n; j i) { is_prime[j] false; } } } return primes; } long long lcmByFactorization(int a, int b) { std::mapint, int max_exp; // 对a分解质因数 int x a; for (int p 2; p * p x; p) { int cnt 0; while (x % p 0) { x / p; cnt; } if (cnt 0) max_exp[p] cnt; } if (x 1) max_exp[x] 1; // 对b分解质因数并更新最大指数 int y b; for (int p 2; p * p y; p) { int cnt 0; while (y % p 0) { y / p; cnt; } if (cnt max_exp[p]) max_exp[p] cnt; } if (y 1) max_exp[y] std::max(max_exp[y], 1); long long result 1; for (auto [p, e] : max_exp) { while (e--) result * p; } return result; }这种实现明显比gcd公式法复杂时间复杂度也高不少——单次分解质因数最坏情况是O(√n)再加上筛法建表的开销在大数据量下性能远不如欧几里得算法。但它的优势在于可解释性和可扩展性当你需要一次性求多个数的最小公倍数并且要输出分解过程比如数学题解题过程、教学演示这个方法无可替代。另外如果你已经维护了一套质因数分解系统顺带求lcm就是“免费”的不用额外维护新的逻辑。7. 三种GCD算法与两种LCM求法的全面对比与选型建议我把上面几种算法放在一起做一次横向对比这样选型的时候一眼就能看清楚算法核心运算时间复杂度代码复杂度最佳适用场景更相减损术减法最坏O(max(a,b))极简教学演示、理解公约数概念欧几里得算法取模O(log min(a,b))简洁通用场景、竞赛刷题、标准库实现Stein算法减法移位O(log max(a,b))中等超大整数、无除法硬件环境分解质因数法求LCM质因数分解O(√n)较复杂数学解题演示、多数组件化求LCMgcd公式法求LCM除法乘法O(log min(a,b))极简几乎一切工程场景首选方案选型建议默认情况下的最优解非常明确——最大公约数用欧几里得算法最小公倍数用“先除后乘”的gcd公式法。这组合在时间效率、代码可维护性、防溢出安全性上都做到最优。但在以下场景需要重新考虑教学场景优先用更相减损术分解质因数法。虽然性能一般但学生能直观看到“公约数”是如何从“不断相减”中浮现的比直接给代码要有说服力得多。大整数运算场景改用Stein算法。尤其在做高精度库如大数RSA、密码学算法时取模是性能杀手减法和移位才有优势。如果你计算的是浮点数或需要处理不一定为整数的情况gcd和lcm都只适用于整数这些算法全部作废。请先回到问题定义确认数据是整数再做方案选型。对于刚入门的朋友我建议先把欧几里得算法背得滚瓜烂熟然后自己手写一遍迭代版和递归版再分别测试几组大数对比运行时间。等你对取模的循环过程有了手感再去看Stein算法和更相减损术会发现它们之间的演进关系非常自然。8. 常见问题与排查技巧实录这块整理我在教学和刷题过程中经常遇到的典型问题每个都是真实踩过的坑问题1递归版gcd在数据很大时会栈溢出吗不会。欧几里得算法递归深度不超过O(log min(a, b))即使a、b均为max long long深度也只有几十层离栈溢出很远。但如果你的递归函数写得不小心比如每次递归前就复制了巨大的对象比如大整数的vector数组那栈和堆都有风险。所以竞赛中我一般直接写迭代版不给自己留隐患。问题2用lcm(a,b) a * b / gcd(a,b)到底行不行数学上完全正确但工程上不推荐。因为a * b在int范围内极容易溢出而a / gcd(a, b) * b就能在很大范围内安全计算。我见过太多人因为这种写法在LeetCode第1201题这类题目上交了错误答案调试半天才发现是溢出。养成先除后乘的习惯以后这类问题可以几乎绝迹。问题3求0和某个数的gcd、lcm会发生什么gcd(0, n) n这是数学上的约定但lcm(0, n)严格来说是未定义的因为0没有“倍数”概念。实际工程中如果你用a / gcd * b去算gcd为0时直接触发除零错误所以要么提前处理a或b为0的情况要么约定输入为正整数。在刷题时也要先看题目约束条件大多数题目明确说“a和b均为正整数”这时候就不用担心这个问题。问题4更相减损术碰上悬殊数字算得很慢怎么区分“教学价值高”和“实际不可用”我的经验是更相减损术适合在小范围数据或课堂教学中使用一旦数据超过一万量级性能问题就会非常突出。如果在竞赛题里看到需要计算gcd且数据范围很大直接放弃更相减损术上欧几里得不要有心理负担。理解它的原理就够了不意味着必须在所有场景用它。问题5多个数的gcd和lcm有没有什么优化技巧多个数的gcd就是从头到尾两两迭代gcd顺序不影响结果lcm同样两两迭代但注意结果是“越迭代越大”所以如果题目的最终要求是取模输出最好在迭代过程中每步都取模防止中间结果爆炸。比如求n个数lcm对某个mod取模可以每次lcm算完直接 % mod但如果后续还要用这个lcm去求别的数就不能只保存取模后的值而应该用适当的大数类型保存完整结果。这个细节在题目“求n个数的lcm对mod取模”中经常出现需要根据题目要求灵活处理。问题6为什么标准库的std::gcd有时比手写慢标准库实现通常会处理更多边界情况包括负数、类型转换等并且开启了异常检查所以可能比手写简单版本稍慢。但这差别微乎其微工程中完全没有必要因此放弃标准库。不过在处理超高频率调用gcd的算法题目时比如某些数论题中循环几十万次手写一个不带边检的迭代版确实能节省一些常数时间这也是竞赛常用做法。9. 最后分享一点个人使用体会我最早学这些算法的时候总觉得最大公约数和最小公倍数是面试热身题没什么实际用处。后来在写加密算法、实现分数运算类、处理采样频率对齐等实际工程里才发现gcd和lcm出现的频率远比自己想的高。分数约分需要gcd多个蓝牙设备的广播周期对齐需要lcm音视频编码中的时间戳对齐也需要lcm。这些东西其实一直在我们身边只是不专门说“这里用了gcd”而已。另外说个很多教学文章不会提的小技巧在写gcd相关代码时可以顺手封装一个同时返回gcd和lcm的工具函数很多场景两个一起用可以省一次类型转换和一次除法的开销。代码很简单但能体现你对这一块的掌握程度。理解了这些底层原理之后再看算法题你会发现很多数论题目就是在gcd和lcm的组合上套壳。把这一关打扎实后面看扩展欧几里得、裴蜀定理、模逆元这些进阶内容都会顺很多。建议把文中的代码亲手敲一遍再试试用long long跑几组大数边界感受一下什么样的写法会爆什么样的写法稳如老狗。踩过这个坑之后你对这几个算法的理解就彻底落地了。