中 · 数论

最小公倍数

你在最大公约数里已经写过 gcd。最小公倍数就是 a / gcd(a,b) * b —— 但顺序很关键，否则乘积会溢出。

一句话答案最小公倍数是 a / gcd(a, b) * b —— 先除后乘：10⁴ 这个量级乘起来还不会溢出，但正是这个习惯让输入变大时依然正确。

题目

输入: 两行，各一个整数：a 然后 b（1 ≤ a, b ≤ 10000）。

输出: 它们的最小公倍数。

样例：

输入输出
4
6		12
3
5		15
12
18		36

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 公式

lcm(a,b) = a * b / gcd(a,b)。但写成 a / gcd(a,b) * b —— 先除让中间值更小，在本题范围内不会溢出 32 位 int。

提示 2 — 相等的数

若 a == b，答案就是 a —— 公式同样成立，无需特判。注意运算顺序：a / gcd * b 是整数运算，先除后乘。

题解（先自己试试！） 
#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a / gcd(a, b) * b << endl;
    return 0;
}

可以进阶了：求两个边界之间有多少个 k 的倍数，或者先用 gcd 约分再用 lcm 通分。下一关：阿姆斯特朗数。

深度解析

为什么这样做对

a * b = gcd(a,b) * lcm(a,b) 这一条恒等式就是全部窍门 —— 有了 gcd，lcm 只差一次除法。不用枚举倍数，也不用猜。

代价

O(log min(a,b)) 时间，和欧几里得 gcd 一样。O(1) 空间。写成 a / gcd * b 能让中间值在本题范围内留在 32 位以内。

常见错法

  • 写成 a * b / gcd(a,b) 是先乘后除，a、b 一大中间值就溢出 int，答案变成负数。
  • gcd 里把 a = b; b = a % b 的顺序写反、又没先存余数，可能死循环或返回 0 —— 先把 a % b 存进临时变量再赋值才稳。

下一步

同一个函数换个用法：分子分母同除 gcd 就能约分。阿姆斯特朗数把「数位 + 幂」的想法反过来用。

记住这两句

  • lcm(a,b) = a / gcd(a,b) * b —— 先除后乘。
  • 欧几里得 gcd 是可复用的工具，多数数论题离它只有一次调用。
🐞 这段是错的 —— 点开,亲手让它挂一次

印的是乘积不是最小公倍数 —— 4 6 输出 24，判题要的是 12

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a * b << endl;   // product, not lcm
    return 0;
}