C語言求最小公倍數：輾轉相除法與遞歸實現全解析

數學原理

兩數 a, b 的最小公倍數 (LCM) 與最大公約數 (GCD) 滿足：

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

GCD 使用 輾轉相除法（歐幾里得算法）：

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

標準 LCM 實現

#include <stdio.h>

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

int lcm(int a, int b) {
    return a / gcd(a, b) * b; // 先除後乘防溢出
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", lcm(a, b));
    return 0;
}

遞歸版 GCD/LCM

int gcd_rec(int a, int b) {
    return b ? gcd_rec(b, a % b) : a;
}

int lcm_rec(int a, int b) {
    return a / gcd_rec(a, b) * b;
}

經典應用題解析

題 1：A、B、C 三數，兩兩 LCM 已知，求三數

已知： LCM(A,B)=24, LCM(B,C)=40, LCM(A,C)=30
解： 分解質因數
24 = 2³×3, 40 = 2³×5, 30 = 2×3×5
→ A=3 (3¹), B=8 (2³), C=10 (2×5)
驗證：LCM(3,8)=24, LCM(8,10)=40, LCM(3,10)=30 ✓

題 2：已知 GCD=4, LCM=24，求兩數

設兩數為 4x, 4y (x,y 互質)，則 LCM=4xy=24 → xy=6
互質因子對：(1,6)→(4,24), (2,3)→(8,12)
選項中 8 與 12 符合（GCD=4, LCM=24）。

擴展：多數 LCM

int lcm_array(int a[], int n) {
    int res = a[0];
    for (int i = 1; i < n; i++)
        res = lcm(res, a[i]);
    return res;
}

防溢出技巧

• 使用 long long 或 __int128 (GCC)
• 先除後乘：a / gcd(a,b) * b
• 大數場景採用質因數分解法

總結

LCM 核心在 GCD，輾轉相除法 O(log min(a,b)) 極高效。掌握 a/gcd*b 防溢出寫法、遞歸/迭代雙實現、質因數分解應用，即可應對從基礎到競賽的各類 LCM 問題。