每次带新人或者整理算法模板最大公约数GCD和最小公倍数LCM这对CP都是绕不开的基础题。说它基础是因为很多看似复杂的场景比如分数约分、通分、周期调度、齿轮配比甚至在某些加密和哈希算法里底层都藏着这两个概念说它绕不开是因为几乎所有编程语言的标准库都有现成实现但真要你现场手写能一次写对的人还真不多。我这次梳理的是最经典的几类求法最大公约数重点讲穷举法、辗转相除法欧几里得算法和更相减损术三种最小公倍数则从公式法和枚举倍数两条路线入手。适合刚学算法的同学打基础也适合准备面试、竞赛或者刷题的老手做模板整理。我会把每种算法的思路、代码、复杂度、适用场景和坑一次说清看完你不仅能写还能知道为什么这么写。1. 先理清楚最大公约数和最小公倍数到底是什么关系1.1 两个概念的本质最大公约数也叫最大公因数、最大公因子英文是 Greatest Common Divisor缩写 GCD有些教材也写成 HCFHighest Common Factor。它指的是一组整数共有的约数中最大的那个。比如 12 和 18约数分别是 1、2、3、4、6、12 和 1、2、3、6、9、18公共约数是 1、2、3、6最大那个就是 6。最小公倍数英文是 Least Common Multiple缩写 LCM指的是同时是这几个数的倍数中最小的那个正数。12 和 18 的倍数集合分别是 12、24、36、48……和 18、36、54……最小公共倍数是 36。这两个概念不是孤立存在的。有一个非常核心的数学关系把它们绑在了一起对任意两个正整数 a 和 b都有gcd(a, b) * lcm(a, b) a * b也就是说知道了最大公约数就能直接算出最小公倍数lcm(a, b) a * b / gcd(a, b)这个公式是整个最小公倍数算法里最核心的基石后面第 3 章的第一种算法就是基于它。1.2 它们到底用在哪儿很多人觉得这些是纯数学玩具其实工程和竞赛里全是它们的身影。最简单的场景是约分和通分。把分数 a/b 化简就是分子分母同时除以 gcd(a, b)把两个分数通分最小公分母就是两个分母的 LCM。这两个操作在实现有理数运算类、计算器程序、金融利率换算的时候会反复出现。再比如周期问题。某个流水线上的设备 A 每 6 秒触发一次设备 B 每 8 秒触发一次问多少秒后两者同时触发答案就是 lcm(6, 8) 24 秒。这类问题在实时系统任务调度、网络报文对齐、信号灯相位设计中非常常见本质就是找两个周期的最小公倍数。还有循环小数转分数、RSA 加解密里的模逆元计算、某些哈希表的扩容策略都会用到最大公约数。扩展欧几里得算法更是直接建立在 gcd 的递推过程上用来求模线性方程的逆元。所以别小看这两道“小算法”它们是很多高级数论内容的入口。2. 求最大公约数的三种算法2.1 穷举法最直观的暴力搜索思路一句话从 min(a, b) 开始往下试第一个能同时整除 a 和 b 的数就是最大公约数。int gcd_bruteforce(int a, int b) { if (a 0 || b 0) return 0; // 严格场景需处理 int n a b ? a : b; for (int i n; i 1; --i) { if (a % i 0 b % i 0) return i; } return 1; // 至少为 1 }为什么从大的往小的试因为要找最大公约数倒序找第一个命中的就是最大的直接返回。正序遍历理论上也行但需要把所有约数都找完才能确定最大浪费时间。穷举法的优点是正确性一目了然几乎不需要思考。缺点也很致命时间复杂度是 O(min(a, b))。如果 a 和 b 都是 10 的 9 次方量级循环一亿次起步在竞赛和性能敏感场景里基本不能用。这个算法唯一推荐的场景是教学演示或者 a、b 非常小比如个位数的时候图省事。实际工程里没人用它。2.2 辗转相除法欧几里得算法最通用的标准答案辗转相除法是古希腊数学家欧几里得在《几何原本》里提出的核心是一个递推关系gcd(a, b) gcd(b, a % b)当 b 变成 0 时gcd(a, 0) a。为什么这个等式成立可以这样理解设 a q * b rq 是商r 是余数那么任何能同时整除 a 和 b 的数也一定能整除 r a - q * b反过来任何能同时整除 b 和 r 的数也一定能整除 a q * b r。所以 a 和 b 的公约数与 b 和 r 的公约数完全相同最大公约数自然相等。用代码写出来无论是递归还是迭代都很简洁// 递归版 int gcd_recursive(int a, int b) { if (b 0) return a; return gcd_recursive(b, a % b); } // 迭代版推荐 int gcd_iterative(int a, int b) { while (b ! 0) { int t b; b a % b; a t; } return a; }我给新人讲这个算法的时候喜欢把 a、b 的取模过程比作“两个数在互相咬合缩小”每次取模b 变成余数a 变成原来的 b数字规模快速下降。最坏情况是 a 和 b 是斐波那契数列的相邻两项比如 144 和 89那需要进行的取模次数约等于数字位数的 1.44 倍整体复杂度是 O(log min(a, b))。这个速度非常快哪怕 a 和 b 是 10 的 18 次方量级的 64 位整数也只需要几十次除法就结束。递归版和迭代版用哪个我日常推荐迭代版因为不会因为递归深度造成理论上的栈压力虽然这里递归深度其实很小。但如果是竞赛里写模板递归版代码量更短也更能体现数学美感。两个都建议背下来。2.3 更相减损术中国古代数学家的智慧更相减损术出自我国古代数学著作《九章算术》它的核心也很简单gcd(a, b) gcd(a - b, b) 当 a b 时 gcd(a, b) gcd(a, b - a) 当 b a 时也就是说两个数相等的时候这个数本身就是最大公约数不相等就把大数减小数然后继续比较。int gcd_subtract(int a, int b) { // 需要先保证 a 和 b 都为正数 while (a ! b) { if (a b) a - b; else b - a; } return a; }这个算法的正确性和辗转相除法是类似的。它把“取模”换成了“多次减法”数学上等价但工程性能差异很大。假设 a 1000000b 1更相减损术要循环约 999999 次才能走到 a b 1而辗转相除法一步取模就得到 gcd(1000000, 1) 1。所以在数值差异很大的情况下更相减损术会退化到 O(max(a, b))。那它是不是就没用了也不完全是。它的改进版叫 Stein 算法Steins algorithm通过识别偶数和移位运算来加速完全不依赖除法在部分仅支持加减和位运算的低端嵌入式平台上比辗转相除法更实用。这个作为延伸了解就好平时编程用辗转相除法足够。2.4 三种算法的对比与选型算法核心思想时间复杂度代码复杂度适用场景穷举法从 min(a,b) 向下枚举O(min(a,b))极低教学、极小数据辗转相除法取模递推O(log min(a,b))低通用首选更相减损术大数减小数最坏 O(max(a,b))低纯加减平台、教学对比我的建议很直接除非题目明确要求你写某种特定方法否则一律用辗转相除法的迭代版本。它性能稳定、代码简洁、不容易出边界问题。3. 求最小公倍数的两种算法3.1 公式法利用 GCD 一步到位这是最重要的一种也是工程里几乎唯一的正解。由前面的关系式直接可以得到lcm(a, b) a / gcd(a, b) * b注意这里的写法。为什么不写成 a * b / gcd(a, b)因为 a * b 可能溢出。比如 a 和 b 都是 int 范围内的数a * b 可能会超过 32 位整数的上限但 a / gcd(a, b) 的结果一定不会超过 a再乘 b 就更安全。这个先除后乘的顺序是无数前辈用线上事故换来的经验。long long lcm_formula(int a, int b) { return (long long)a / gcd(a, b) * b; }我解释一下为什么要强转 long long。C 里 int 和 int 的除法还是 int虽然 a / gcd(a, b) 一定整除但你不希望中间计算溢出。先用 (long long) 把 a 转换成 64 位再进行后续运算这是一个好习惯。如果你用的是 Python因为整数是无限大就不用担心这种问题直接 a // gcd(a, b) * b 即可。def gcd_euclid(a: int, b: int) - int: while b: a, b b, a % b return a def lcm_formula(a: int, b: int) - int: return a // gcd_euclid(a, b) * b这个算法的正确性可以从质因数分解的角度理解。把 a 和 b 做质因数分解gcd 取的是每个质因数指数的最小值交集lcm 取的是最大值并集。a * b 是所有质因数的指数都相加等于最大公约数和最小公倍数的乘积因为两个数交集部分被算了两次。所以除以一个 gcd 就能得到 lcm。时间复杂度就是 gcd 的复杂度也就是 O(log min(a, b))速度极快这也是它成为首选的根本原因。3.2 枚举倍数法不推荐但值得理解第二种方法同样简单粗暴从 max(a, b) 开始往上枚举遇到第一个同时是 a 和 b 倍数的数就是最小公倍数。int lcm_bruteforce(int a, int b) { int m a b ? a : b; while (true) { if (m % a 0 m % b 0) return m; m; } }为什么从 max(a, b) 开始因为最小公倍数不可能比 a 和 b 中较大的那个还小。举个例子lcm(12, 18) 肯定不小于 18所以从 18 开始试第一个同时整除 12 和 18 的是 36这就是答案。这个算法在 a 和 b 互质的时候特别尴尬。比如 999999937 和 999999929 这种大质数它们的最小公倍数差不多是 10 的 18 次方用枚举法就是天文数字级别的循环。所以它只适合非常小的数或者你只是想快速验证公式法结果对不对的时候。3.3 两种算法的选型建议公式法几乎在所有场景都是碾压级的优势时间上是 O(log n)枚举法是 O(a * b)尤其是数字大的时候差距是数量级的。枚举法的唯一“优势”是不需要先求 gcd也就没有 gcd 这个概念适合刚学编程、还没接触过数论概念的初学者。我在实际编程里的一条原则是能用公式法绝不用枚举法。如果是在 LeetCode 这类平台上做题看到“最小公倍数”“返回两个数的最小公倍数”这类字眼第一反应就该是把 lcm a / gcd(a, b) * b 这个公式写出来。4. 实战避坑指南溢出、负数和多参数处理4.1 整数溢出是最大的坑前面提到过lcm 计算里先除后乘而不是先乘后除这是第一优先级。很多人第一次写 lcm顺手就写 return a * b / gcd(a, b)结果在 a 2000000000b 1500000000 这种数据下直接炸掉因为 a * b 远超 int 范围出现负数或者错误结果。再看 gcd 本身虽然 a % b 不会溢出但如果你把 a、b 定义成 int而 a 或 b 正好是 INT_MIN-2147483648绝对值操作 int 也可能会溢出。处理这种极端情况比较保险的做法是直接用 long long 接收输入或者在函数入口做类型提升。记住gcd 本身不太容易溢出但 lcm 计算中先除后乘能救你一条命。4.2 负数和 0 的处理数学上gcd(-12, 18) 一般定义为 6但很多编程语言对负数的取模结果是负的直接套用递归版 gcd 容易出错。最简单的策略是进入 gcd 函数后先把 a、b 取绝对值lcm 只需要在最后处理符号工程上通常也直接对绝对值计算如果要求返回负数再加上符号判断。0 的情况很特殊。数学定义里 gcd(a, 0) |a|因为任何数都能整除 0但 0 的最大约数就是 a 本身。有了这个约定辗转相除法的递归终点就是 b 0返回 a。lcm(a, 0) 呢0 乘任何数都是 0所以 lcm(a, 0) 0这在公式法里也自然成立。但穷举法和更相减损术对 0 很敏感需要额外判断。比如更相减损术如果 a 0while 循环会直接卡死。所以如果你是手写穷举或更相减损必须在一开始就处理 0 和负数。4.3 从两个数扩展到多个数求三个以上数的 gcd 和 lcm也是常见需求。核心思路是“两两合并、迭代下去”gcd(a, b, c) gcd(gcd(a, b), c) lcm(a, b, c) lcm(lcm(a, b), c)C 实现// 求数组的最大公约数 int gcd_array(const vectorint nums) { int res 0; // gcd(0, x) x0 作为初始值很方便 for (int x : nums) { res gcd_iterative(res, x); } return res; } // 求数组的最小公倍数 long long lcm_array(const vectorint nums) { long long res 1; for (int x : nums) { res lcm_formula(res, x); } return res; }这里有个容易踩坑的点lcm 数组初始化不能是 1如果数组里有 0结果会出错。更稳妥的初始策略是先取第一个元素然后从第二个开始逐个算。也有一种写法是初始值设为 1但遇到 0 必须提前返回 0。我自己的习惯是用第一个元素初始化然后循环合并。4.4 模板封装的小建议如果你经常写比赛代码建议把 gcd、lcm 封装成全局函数放到模板里。C 标准库里其实已经有 std::gcd 和 std::lcmC17 引入在 头文件但很多在线评测环境可能版本较老或者你不想包含额外头文件手写模板仍然是稳妥选择。我自己的常用模板是typedef long long ll; ll gcd(ll a, ll b) { while (b) { ll t a % b; a b; b t; } return a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; // 先除后乘防溢出 }补一行 typedef long long ll配合函数参数都用 long long能省掉一半以上的溢出问题。5. 常见问题排查与个人使用心得问题现象可能原因解决方案gcd 结果为负数输入的负数没取绝对值进入函数先取 abslcm 结果为超大负数a*b 中间溢出改成 a / gcd(a,b) * b并提升为 long long更相减损术死循环输入中有 0 或负数入口先处理非正数递归版 gcd 栈溢出理论上递归深度很大改用迭代版或确认数据范围多个数 lcm 结果偏小数组里包含 0初始值 1 处理错误用数组第一个元素初始化或特判 0数据范围超过 int用 int 存储大数所有参与 lcm 计算的数用 long long我实际使用中还有一个体会大部分情况下递归版 gcd 不会爆栈因为递归深度只有 O(log n)就算 n 到 10 的 18 次方深度也就几十层。真正危险的反而是你写 lcm 函数时忘了把 a / gcd(a, b) 的结果转成 long long然后乘上 b 又赋给 int。这种问题在编译时不会有任何告警只有跑到边界数据才会爆。另外分享一个用 gcd、lcm 做题的常见套路。很多“周期性相遇”类题目比如两个赛车手绕圈、两盏灯闪烁、两班车发车问下次同时发生的时间本质上都是求 lcm。还有一些“分成相同小组”“均分物品”的题目本质是求 gcd。看到题目描述里的关键词先把模型转成数学语言再决定用哪个函数这比硬套模板更重要。我对这两个算法的最终建议把迭代版 gcd 和公式法 lcm 背到肌肉记忆穷举法和更相减损术理解原理即可。面试时如果被问到“还有没有别的办法”能把更相减损术和 Stein 算法讲出来会让对方觉得你有广度。平时刷题就把这一页当工具书需要的时候直接查不需要背太多变体但一定要明白每个变体的时间复杂度为什么不同。这些基础算法你越熟练后面学扩展欧几里得、中国剩余定理这类更抽象的数论内容时越轻松因为有前面的“手感”垫着。