HDU 1573 X問題：擴展中國剩餘定理求解同餘方程組計數

題目大意

給定一組同餘方程：X mod a[i] = b[i]（0 < a[i] ≤ 10），求在 [1, N] 範圍內滿足所有方程的正整數 X 的個數。注意 a[i] 不一定兩兩互質，需用擴展中國剩餘定理（EXCRT）合併方程。

解題思路

1. 使用 EXCRT 將多條同餘方程兩兩合併，得到通解形式 X ≡ r (mod m)，其中 m 為所有模數的最小公倍數。
2. 若合併過程中發現無解（即某步 c % d != 0），直接輸出 0。
3. 得到最小非負解 r 後，滿足條件的 X 為 r, r+m, r+2m, ...。在 [1, N] 內的個數為 (N - r) / m + 1（若 r == 0 需調整為 m）。

關鍵代碼片段

// 擴展歐幾里得：求解 a*x + b*y = gcd(a,b)
void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if (!b) { d = a; x = 1; y = 0; }
    else { ex_gcd(b, a % b, d, y, x); y -= x * (a / b); }
}

// EXCRT 合併方程
LL ex_crt(LL *a, LL *b, LL n) {
    LL m1 = a[0], r1 = b[0];
    for (int i = 1; i < n; ++i) {
        LL m2 = a[i], r2 = b[i];
        LL d, x, y;
        ex_gcd(m1, m2, d, x, y);
        LL c = r2 - r1;
        if (c % d) return -1; // 無解
        LL t = m2 / d;
        x = (c / d * x % t + t) % t; // 最小非負解
        r1 = m1 * x + r1;
        m1 = m1 * t; // lcm
        r1 = (r1 % m1 + m1) % m1;
    }
    return r1; // 返回最小非負解，模數為 m1
}

複雜度

合併 n 條方程，每步 O(log max(a))，總體 O(n log max(a))，極快。