辗转相除法

💡 打个比方

求 48 和 18 的最大公约数，就像两个数玩追逐游戏：大数除以小数，把"余下的部分"继续拿去追。

48 ÷ 18 余 12 → 18 ÷ 12 余 6 → 12 ÷ 6 余 0。余数越来越小，最后除数为 0 的那一刻，除数 6 就是最大公约数。

换个角度看：用同一种正方形瓷砖去铺 48×18 的地砖，不留缝、不切割，能用的最大瓷砖边长，恰好也是 6。

🖼️ 大图看明白

📏 辗转相除，只要 3 步

1. 第 1 步：大数除以小数，取余数。比如 48 % 18 = 12。
2. 第 2 步：角色互换。小数（18）变成新的被除数，余数（12）变成新的除数：18 % 12 = 6。重复第 1 步。
3. 第 3 步：余数为 0 就停。谁当除数、余数为 0，谁就是最大公约数。12 % 6 = 0，所以 GCD = 6。

💻 C++ 怎么写

// 辗转相除法：递归版
int gcd(int a, int b) {
    if (b == 0) return a;      // 余数为 0，a 就是答案
    return gcd(b, a % b);      // 角色互换，继续追
}

int main() {
    int a = 48, b = 18;
    cout << gcd(a, b) << "\n";          // 6
    // 最小公倍数 = a ÷ GCD × b（先除后乘防溢出）
    cout << a / gcd(a, b) * b << "\n";  // 144
    return 0;
}

✋ 你来试试