借助上一节学过的最大公约数，几步就能算出最小公倍数——不需要单独的枚举套路。
两个整数的公倍数，是指能同时被这两个数整除的数；在所有公倍数里最小的那一个（不算 0），就叫做最小公倍数（Least Common Multiple，简称 LCM）。上一节求最大公约数是往"因数"的方向找（越找越小），这一节正好反过来，是往"倍数"的方向找（越找越大）。
把 4 和 6 的倍数各自列一排，看看哪个数最早同时出现在两排里：
12，不是 24。最直接的想法：从两个数里较大的那个开始，按它的倍数一格一格往后跳（bigger, 2×bigger, 3×bigger, ...），每跳到一个新的数，就检查它能不能被较小的那个数整除——能整除的第一个，就是答案。
| 1 | int Lcm(int a, int b) |
| 2 | { |
| 3 | int bigger = max(a, b); |
| 4 | int smaller = min(a, b); |
| 5 | for (int multiple = bigger; ; multiple += bigger) |
| 6 | { |
| 7 | if (multiple % smaller == 0) |
| 8 | { |
| 9 | return multiple; |
| 10 | } |
| 11 | } |
| 12 | } |
用 Lcm(15, 8) 走一遍：从 15 开始，每次加 15，一路检查能不能被 8 整除：
15、30、45、60、75、90、105）除以 8 都有余数，直到第 8 个数 120 才正好整除——Lcm(15, 8) = 120。如果两个数都比较大、最小公倍数又特别大，这种"一格一格跳过去试"的办法会跳很多很多次。不需要重新发明一套枚举办法——上一节学过的最大公约数，刚好能帮上大忙。关键想法是：把 a 和 b 都拆成"两个数共享的部分"（也就是最大公约数）和"各自独有的部分"。最小公倍数，正好就是把这三块——共享的部分、a 独有的部分、b 独有的部分——全部凑在一起，一个都不能少，也不会有重复。
GCD(4,6)=2），蓝色的 2 是 4 甩开共享部分后自己独有的，粉色的 3 是 6 独有的。把三块乘起来，正好凑出又能被 4 整除、又能被 6 整除的最小的数：2×2×3=12。共享的部分只需要算一次（不用左右各算一遍再重复），这正是最小公倍数比"a 直接乘 b"要小的原因。换一种说法："4 独有的部分"其实就是 4 ÷ 共享部分，"6 独有的部分"就是 6 ÷ 共享部分。所以最小公倍数可以直接写成：
| 1 | int Lcm(int a, int b) |
| 2 | { |
| 3 | return a / Gcd(a, b) * b; |
| 4 | } |
a * b / Gcd(a, b)：两种写法数学上结果一样，但计算的中间过程不一样安全。a / Gcd(a,b) 算出来的是"a 独有的部分"，这个数不会比 a 本身大，再乘以 b 风险比较小；而 a * b 是直接把两个原数相乘，哪怕最终答案不大，中间这一步也可能先溢出。比如 a = b = 100000 时，最终的最小公倍数其实只有 100000（很小），但 a * b 会先算出 100亿，早就超过了 int 能装的范围（约 21 亿）——明明答案没问题，却因为算的顺序不对而出错。a / Gcd(a,b) * b 从头到尾都不会经过这么大的中间值，更安全。用 Lcm(63, 40)（这两个数互质，最大公约数是 1）实际数一数两种写法的步骤数：
GCD(63, 40) 只需要 6 步，之后再除一下、乘一下就直接得到答案——两个数互质恰好是枚举法的最坏情况，也正是这种写法和优化写法差距最大的时候。| 写法 | 核心思路 | 说明 |
|---|---|---|
| 枚举法 | 按较大数的倍数往后跳，逐个试除 | 直观但慢，两数互质时最坏，要跳"较小数"那么多次 |
| 借助最大公约数 | Lcm(a,b) = a / Gcd(a,b) * b | 复用上一节的 Gcd，几步就能算出答案，竞赛标准写法 |
<numeric> 头文件也直接提供了 std::lcm(a, b)，效果和这里手写的一致。但同样要注意编译器版本兼容问题，手写这个公式依然是竞赛里的基本功——尤其是"先除再乘"这个细节，很多题目就是因为顺序写反了而在大数据下出错。