最大公约数与最小公倍数

💡 打个比方

12 和 18 一起玩积木。它们都能整除的数叫"公约数"：1、2、3、6。其中最大的是 6，这就是最大公约数（GCD）——两个数共同的最大玩具。

再看公交：12 路车每隔 12 分钟一班，18 路车每隔 18 分钟一班，它们"同时发车"的时刻是 36、72、108……最早一次就是 36，这就是最小公倍数（LCM）。

🖼️ 大图看明白

📏 求 GCD 和 LCM，只要 3 步

1. 第 1 步：从 min(a, b) 开始往下试，找第一个能同时整除 a 和 b 的数。
2. 第 2 步：第一个找到的就是最大公约数（因为从大到小试）。
3. 第 3 步：LCM = a ÷ GCD × b（先除后乘）。

💻 C++ 怎么写

// 从大到小找第一个能同时整除 a 和 b 的数
int gcd(int a, int b) {
    for (int i = min(a, b); i >= 1; i--) {
        if (a % i == 0 && b % i == 0)
            return i;   // 从大到小试，第一个就是最大的
    }
    return 1;
}

int main() {
    int a, b;
    cin >> a >> b;
    int g = gcd(a, b);
    cout << "GCD = " << g << "\n";
    cout << "LCM = " << a / g * b << "\n";  // 先除后乘，防溢出
    return 0;
}

✋ 你来试试