NYOJ 517 最小公倍數：BigInteger 遞推預處理 1..100 所有 LCM

問題：多測試用例，每次給定 n (≤100)，輸出 1..n 的最小公倍數。結果極大，需高精度。

遞推公式

LCM(1..n) = LCM( LCM(1..n-1), n )
即 L[n] = L[n-1] * n / gcd(L[n-1], n)。

Java BigInteger 實現

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger[] lcm = new BigInteger[101];
        lcm[1] = BigInteger.ONE;
        for (int i = 2; i <= 100; i++) {
            BigInteger iBI = BigInteger.valueOf(i);
            lcm[i] = lcm[i-1].multiply(iBI).divide(lcm[i-1].gcd(iBI));
        }
        while (cin.hasNext()) {
            int n = cin.nextInt();
            System.out.println(lcm[n]);
        }
    }
}

關鍵點

• 預處理 O(100) 一次性算完，查詢 O(1)；
• BigInteger 內置 gcd、multiply、divide，代碼極簡；
• 結果極大（LCM(1..100) 約 42 位），long 遠遠不夠，必須用高精度。