HDU 2028 Lowest Common Multiple Plus 多數最小公倍數

問題

多組測試案例，每組給 n 個正整數，求它們的 LCM。結果保證 32 位有符號整數範圍內。

核心公式

LCM(a,b) = a / GCD(a,b) * b —— 先除後乘防溢出。

多數 LCM：LCM(a,b,c) = LCM(LCM(a,b), c) 依次累積。

GCD 實現（輾轉相除法）

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

完整代碼

#include <cstdio>

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

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        long long ans = 1;
        for (int i = 0, x; i < n; ++i) {
            scanf("%d", &x);
            ans = ans / gcd(ans, x) * x; // 先除後乘
        }
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵教訓

• 先計算 a * b 再除 GCD 會溢出（即使最終結果在範圍內）
• 先除後乘：a / gcd(a,b) * b 保證中間結果不超過最終 LCM
• 用 long long 存儲中間結果，輸出 %lld
• 輾轉相除法比遞減枚舉快得多（O(log min(a,b))）

測試樣例

Input:
2 4 6
3 2 5 7
Output:
12
70