HDU 3579 Hello Kiki：同餘方程組求解（中國剩餘定理）

問題描述

Kiki 有 x 個硬幣，用 m 種方法分，每次記錄基數 a_i 和餘數 b_i（即 x ≡ b_i (mod a_i)）。求最小正整數解 x。無解輸出 -1。注意：x > 0。

核心算法：合併同餘方程（擴展中國剩餘定理）

標準 CRT 要求模數兩兩互質。本題模數 a_i 可能不互質，需用擴展 CRT（exCRT）：逐個合併方程。

合併兩個方程

已知：
x ≡ b1 (mod a1)
x ≡ b2 (mod a2)
求合併後的 x ≡ b (mod a)（a = lcm(a1,a2)）。

步驟：

1. 設 x = b1 + a1 * k，代入第二式：a1 * k ≡ b2 - b1 (mod a2)
2. 設 g = gcd(a1, a2)。若 (b2-b1) % g != 0 → 無解。
3. 縮約：a1' = a1/g, a2' = a2/g, c = (b2-b1)/g。解 a1' * k ≡ c (mod a2')。
4. 用擴展歐幾里得求 a1' 模 a2' 的逆元 inv，則 k ≡ c * inv (mod a2')。
5. 最小非負解 k0 = (c * inv % a2' + a2') % a2'。
6. 合併解：x = b1 + a1 * k0，新模數 a = a1 * a2' = lcm(a1,a2)，新餘數 b = x % a（調整至 [0, a-1]）。

代碼實現

#include 
using namespace std;
using ll = long long;

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 合併 x≡b1 (mod a1) 和 x≡b2 (mod a2)
// 返回 {新餘數, 新模數}，無解返回 {0, -1}
pair merge(ll a1, ll b1, ll a2, ll b2) {
    ll x, y;
    ll g = exgcd(a1, a2, x, y);
    ll c = b2 - b1;
    if (c % g != 0) return {0, -1}; // 無解
    
    ll a2g = a2 / g;
    // x 是 a1 模 a2 的係數，調整為 a1/g 模 a2/g 的逆元
    ll inv = (x % a2g + a2g) % a2g;
    ll k = (c / g % a2g) * inv % a2g;
    
    ll new_a = a1 / g * a2; // lcm
    ll new_b = (b1 + a1 * k) % new_a;
    if (new_b < 0) new_b += new_a;
    return {new_b, new_a};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        int m; cin >> m;
        vector a(m), b(m);
        for (int i = 0; i < m; ++i) cin >> a[i];
        for (int i = 0; i < m; ++i) cin >> b[i];
        
        ll cur_a = a[0], cur_b = b[0] % a[0];
        bool ok = true;
        for (int i = 1; i < m; ++i) {
            auto res = merge(cur_a, cur_b, a[i], b[i] % a[i]);
            if (res.second == -1) { ok = false; break; }
            cur_a = res.second;
            cur_b = res.first;
        }
        if (!ok || cur_b == 0) cout << -1 << '\n'; // x>0，餘數 0 表示 x=cur_a 但題目可能要求最小正解
        else cout << cur_b << '\n';
    }
    return 0;
}

關鍵點總結

• exCRT 核心：逐對合併，用擴展歐幾里得求逆元解線性同餘方程。
• 無解判斷：(b2-b1) % gcd(a1,a2) != 0。
• 溢出防範：用 __int128 或模運算性質避免中間乘積溢出（a1 * k 可能超 64 位）。
• x > 0：最終餘數為 0 時，最小正解為 lcm 本身，需根據題意調整。

總結

Hello Kiki 是 exCRT 模板題。掌握合併兩同餘方程的標準流程（gcd 判斷 → 縮約 → 求逆 → 合併），即可解決所有不互質模數的同餘方程組問題。注意長整型溢出與 x>0 的邊界處理。