HDU 1788 Chinese Remainder Theorem Again：最小公倍數減 a

題目大意

求最小正整數 N，使得對給定的 m₁, m₂, ..., mᵢ，均有 `N ≡ mⱼ - a (mod mⱼ)`。即 `N + a` 能被所有 mⱼ 整除。等價於求 `LCM(m₁, ..., mᵢ) - a`。i < 10, a, mⱼ < 100。

解法：直接計算 LCM

• 讀入 i, a，再讀 i 個 m。
• 計算 `lcm = m₁`，依次 `lcm = lcm(lcm, mⱼ)`。注意用 64 位整數 (`long long`)，LCM 可能超 32 位。
• 輸出 `lcm - a`。

代碼

#include 
typedef long long ll;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
    int n, a;
    while (~scanf("%d%d", &n, &a) && (n || a)) {
        ll ans = 1;
        for (int i = 0; i < n; ++i) {
            int m; scanf("%d", &m);
            ans = lcm(ans, m);
        }
        printf("%lld\n", ans - a);
    }
    return 0;
}

關鍵點

• **同餘轉化**：`N ≡ -a (mod m)` ⇔ `N + a ≡ 0 (mod m)` ⇔ `N + a` 是所有 m 的公倍數。
• **最小正整數** 即最小公倍數減 a。
• **長長整數** 防止 LCM 溢出（i<10, m<100，最大 LCM < 100¹⁰ ≈ 10²⁰，需 64 位甚至大整數，但題目數據保證 64 位足夠）。

總結

HDU 1788 披著「中國剩餘定理」外衣，實則是 **LCM 直接計算**。同餘條件特殊（餘數均為模數減同一常數），導致問題極大簡化。閱讀題目時應敏銳發現數學結構，避免套用通用 CRT 模板過度設計。