最小公倍数

两个齿轮齿数不同，第一次回到“同一个起始位”所转过的总齿数就是 lcm；同样，多个红绿灯第一次同时变绿的时间也是 lcm。

1. 质因数分解：lcm(a, b) = p₁^max(α₁,β₁) · p₂^max(α₂,β₂) · …。
2. 短除法：与求 gcd 同步进行，把左侧除数与最后剩下的两个互质数全部相乘，得到 lcm。
3. 恒等式：lcm(a, b) = a × b ÷ gcd(a, b)，先求 gcd 再求 lcm 通常更省力。

• “最小公倍数”不是“最小的倍数”——任何数最小的倍数是它本身，公倍数才是关键。
• 三数 lcm 可两两递推：lcm(a, b, c) = lcm(lcm(a, b), c)。