ACM 入門經典：最大公約數與最小公倍數 - 歐幾里得算法 C 實現

題目

輸入兩個正整數 a, b，輸出其最小公倍數 (LCM) 與最大公約數 (GCD)。

核心算法：歐幾里得算法

gcd(a, b) = gcd(b, a % b)，直到 b == 0 時 a 即為 GCD。時間複雜度 O(log min(a,b))。

int gcd(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

最小公倍數公式

lcm(a, b) = a / gcd(a, b) * b。先除後乘避免溢位（若用 long long 更安全）。

完整 AC 代碼

#include 
#include 

int main() {
    long long a, b;
    if (scanf("%lld %lld", &a, &b) != 2) return 0;
    if (a <= 0 || b <= 0) return 0;

    long long x = a, y = b;
    while (y) {
        long long r = x % y;
        x = y;
        y = r;
    }
    long long g = x;
    long long l = a / g * b; // 先除後乘防溢位
    printf("%lld %lld\n", l, g);
    return 0;
}

測試

$ echo "6 8" | ./a.out
24 2
$ echo "1000000000 999999999" | ./a.out
999999999000000000 1

延伸：Stein 算法 (Binary GCD)

僅用位運算、減法、移位，適合無除法指令的處理器：

int gcd_stein(int u, int v) {
    if (!u) return v; if (!v) return u;
    int shift = __builtin_ctz(u | v);
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if (u > v) { int t = u; u = v; v = t; }
        v -= u;
    } while (v);
    return u << shift;
}

總結

GCD/LCM 是數論基礎，歐幾里得算法簡潔高效。競賽中注意：

1. 用 long long 防溢位。
2. LCM 計算先除後乘。
3. 輸入可能含 0，題目通常限定正整數，但防禦性檢查無妨。