HDU 1019 Least Common Multiple：求 n 個數的最小公倍數

題目簡介

給定 t 組測試資料，每組包含 n 個整數，求這 n 個數的最小公倍數 (LCM)。

解題思路

利用公式 lcm(a, b, c) = lcm(a, lcm(b, c)) 迭代計算。為了防止整數溢出，採用「先除後乘」技巧：lcm(a, b) = a / gcd(a, b) * b。

代碼實現

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int t, n, a;
    cin >> t;
    while (t--) {
        cin >> n;
        cin >> a;
        long long ans = a;
        for (int i = 1; i < n; i++) {
            cin >> a;
            ans = ans / gcd(ans, a) * a;
        }
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

時間複雜度 O(n log max(a))，空間複雜度 O(1)。