Least Common Multiple
给你两个正整数 a 和 b。返回它们的最小公倍数：能被 a 和 b 整除且没有余数的最小正整数。
函数
- ainteger
- 第一个正整数
- binteger
- 第二个正整数
- 返回值integer
- 同时是 a 和 b 的倍数的最小正整数
约束条件
1 ≤ a ≤ 1061 ≤ b ≤ 106- 答案可以用有符号 32 位整数表示：
lcm(a, b) ≤ 231-1。乘积a × b可能不行。
示例
- 输入
- a = 4b = 6
- 输出
- 12
- 解释
6的倍数从 6、12、18 开始；4的倍数从 4、8、12 开始。这两个列表中的第一个相同数字是12。
- 输入
- a = 7b = 3
- 输出
- 21
- 解释
7和3除了1以外没有共同因数，所以它们的最小公倍数就是它们的乘积21。
- 输入
- a = 15b = 45
- 输出
- 45
- 解释
15可以整除45，所以45已经是两者的公倍数，并且不存在比45更小的倍数。
进阶
你能只用减法和折半，不进行任何除法或取余，求出最大公约数吗？
提示
逐个打开提示，每个都会多透露一点。
答案是较大数字的倍数。你需要尝试中间的每个数字，还是只尝试较大数字的倍数？
最大公约数和最小公倍数之间存在这样的关系：
gcd(a, b) × lcm(a, b) = a × b。欧几里得算法只需几十步就能求出最大公约数。先计算最大公约数，然后返回
a / gcd × b。先做除法：即使结果能放进 32 位整数，乘积a × b也可能溢出。
题解
最小公倍数和最大公约数由一个事实联系在一起：gcd(a, b) × lcm(a, b) = a × b。所以，快速求解的方法是 a × b / gcd(a, b)。乘积可能达到 10^12，即使结果能放进 32 位整数，乘积也可能溢出，所以要先除以最大公约数，再相乘。
从较大的数字开始计数
结果正确，但无法在最大的测试中运行完毕
思路
答案至少是较大的那个数。将 m 设为 max(a, b)，然后不断加 1，直到两个数都能整除它；你按从小到大的顺序尝试候选数，因此第一个符合条件的数就是最小的。对于 4 和 6，你会尝试 6 到 11，然后在 12 处停止。循环总会结束，因为 a × b 是一个公倍数。
尝试次数大约与答案的大小相当。对于质数 46337 和 46327，答案是 2146654199，需要尝试超过 20 亿次。
算法
- 将
m设为a和b中较大的值。 - 当
m % a或m % b不为0时，将m加 1。 - 返回
m。
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return m按较大数字的倍数逐步递增
思路
答案必须是较大数字 big 的倍数，所以按 big、2 × big、3 × big 依次尝试，直到找到第一个能被较小数字整除的数。对于 4 和 6，你会先尝试 6，再尝试 12。
由于 small × big 始终是公倍数，循环最多运行 min(a, b) 次，在这里最多为一百万次。对于这些限制来说，这已经足够快，但运行次数仍会随着输入增大；如果数字最大达到 10^18，这种做法就不行了。
算法
- 令
big表示较大的数，small表示较小的数。 - 设置
m = big。 - 当
m % small不为0时，将big加到m上。 - 返回
m。
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return m先除以最大公约数，再相乘
思路
将两个数分别分解为质因数。对于每个质数，最大公约数取它的两个幂次中较小的一个，最小公倍数取较大的一个，因此它们合起来恰好各使用一次 a 和 b 的所有因子：gcd × lcm = a × b。对于 4 = 2² 和 6 = 2 × 3，最大公约数是 2，最小公倍数是 2² × 3 = 12。
欧几里得算法可以在 O(log(min(a, b))) 步内求出最大公约数。然后按 a / gcd × b 的顺序计算：最大公约数可以整除 a，所以不会造成精度损失，而且中间结果不会超过答案。对于 a = b = 10^6，a × b / gcd 会超出 32 位整数的范围，此时乘积为 10^12，而答案只有 10^6。
算法
- 将
a和b复制到x和y中。 - 当
y不为0时，将(x, y)替换为(y, x % y)。现在x就是最大公约数。 - 用
a除以x。 - 将结果乘以
b并返回。
def lcm(a, b):
x, y = a, b
while y != 0:
x, y = y, x % y
# x is gcd(a, b). Divide before multiplying.
return a // x * b
易错点和边界情况
- 先计算
a × b。在 Java、C、C++、C# 和 Rust 中，两个接近10^6的数相乘会超出 32 位整数的范围，导致结果错误或为负数（Rust 调试构建会触发 panic），即使最小公倍数仍能用整数表示。 - 用浮点数做除法。结果可能变成
2.146654199E9，或者丢失末尾的数字；所有运算都要使用整数。 - 直接对
a和b本身运行欧几里得算法的循环。循环结束后，它们会分别存有最大公约数和0，所以要对副本进行操作。 - 认为答案是
a × b。只有两个数没有公因数时，这才成立：lcm(4, 6)是12，不是24。
常见问题3
两个数的最小公倍数公式是什么？
lcm(a, b) = a × b / gcd(a, b)，计算时使用 a / gcd(a, b) × b，这样中间值就不会超过答案。对于 4 和 6，最大公约数是 2，而 4 / 2 × 6 = 12。
计算最小公倍数的时间复杂度是多少？
使用 gcd 公式时，时间复杂度为 O(log(min(a, b)))，这是欧几里得算法的开销，空间复杂度为 O(1)。按较大数的倍数逐步查找，时间复杂度为 O(min(a, b))；每次递增 1 计数，时间复杂度为 O(lcm(a, b))。
如何求两个以上数字的最小公倍数？
逐步处理列表：lcm(a, b, c) = lcm(lcm(a, b), c)。对于 [4, 6, 10]，lcm(4, 6) = 12，而 lcm(12, 10) = 60。累计值会迅速增大，因此列表较长时要使用 64 位整数。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def lcm(a, b):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
a = 4 b = 6
预期输出
12