數論基礎：求兩數最小公倍數 (LCM) 的 C 語言實現

問題描述

輸入兩個整數 a, b (1 ≤ a, b ≤ 1,000,000)，輸出它們的最小公倍數。樣例：1000000 999999 → 999999000000。

數學原理

最小公倍數與最大公約數 (GCD) 滿足關係：

LCM(a, b) = |a × b| / GCD(a, b)

求 GCD 使用輾轉相除法（歐幾里得算法），時間複雜度 O(log min(a,b))。

C 語言完整代碼

#include <stdio.h>
#include <stdint.h>  // 使用 int64_t 防止溢出

// 輾轉相除法求最大公約數
int64_t gcd(int64_t a, int64_t b) {
    while (b != 0) {
        int64_t r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int64_t a, b;
    // 循環讀取多組測試數據，直到 EOF
    while (scanf("%lld %lld", &a, &b) == 2) {
        if (a <= 0 || b <= 0) {
            printf("輸入必須為正整數\n");
            continue;
        }
        int64_t g = gcd(a, b);
        // 先除後乘，避免中間結果溢出 64 位
        int64_t lcm = (a / g) * b;
        printf("%lld\n", lcm);
    }
    return 0;
}

關鍵點解析

• 數據類型：a, b ≤ 10⁶，乘積 ≤ 10¹²，需 64 位整數（long long 或 int64_t）。
• 防溢出順序：先計算 a / gcd 再乘 b，中間值不超過 10⁶。
• 輸入處理：使用 while (scanf(...) == 2) 支持多行輸入，適配 OJ 多測試用例格式。
• 邊界情況：輸入為 0 時 LCM 定義為 0，但題目限制 ≥1，代碼中做了防禦性判斷。

擴展：多數求 LCM

int64_t lcm_multi(int64_t arr[], int n) {
    int64_t res = arr[0];
    for (int i = 1; i < n; i++) {
        res = (res / gcd(res, arr[i])) * arr[i];
    }
    return res;
}

總結

掌握 LCM = a*b/GCD 公式與歐幾里得算法是解決此類問題的核心。注意數據範圍選擇類型，避免溢出，代碼簡潔高效。