POJ 2891 整數的奇怪表達：線性同餘方程組 (EXCRT/中國剩餘定理推廣) 完整解析

題目大意

給定 k 個方程：x ≡ rᵢ (mod mᵢ)。求最小非負整數解 x，無解輸出 -1。
mᵢ 不一定互質，故為線性同餘方程組，需用EXCRT (Extended Chinese Remainder Theorem) 求解。

核心數學：兩方程合併

合併 x ≡ r₁ (mod m₁) 和 x ≡ r₂ (mod m₂)。

設 x = m₁·p + r₁ = m₂·q + r₂ → m₁·p - m₂·q = r₂ - r₁。
這是關於 p, q 的線性不定方程。設 g = gcd(m₁, m₂)。
有解條件：g | (r₂ - r₁)。
若有解，通解為 p = p₀ + (m₂/g)·t，代回得新同餘式：

x ≡ r₁ + m₁·p₀ (mod lcm(m₁, m₂))
// 其中 p₀ 為 m₁·p ≡ r₂-r₁ (mod m₂) 的一個解

EXCRT 算法流程

1. 初始 r = r₁, m = m₁
2. 對每個 i = 2..k：
   • 解 m·p ≡ rᵢ - r (mod mᵢ)
   • 用擴展歐幾里得求 g = exgcd(m, mᵢ, x, y)，得 m·x + mᵢ·y = g
   • 若 (rᵢ - r) % g != 0 → 無解
   • p₀ = x * ((rᵢ - r) / g) % (mᵢ / g) (調整為正)
   • 更新 r = r + m * p₀, m = lcm(m, mᵢ) = m / g * mᵢ
   • r = (r % m + m) % m 保證非負
3. 最終 r 即最小非負解

完整代碼

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

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

// 合併 x ≡ r1 (mod m1) 和 x ≡ r2 (mod m2)
// 返回 {new_r, new_m}，無解返回 {-1, -1}
pair merge(int64 r1, int64 m1, int64 r2, int64 m2) {
    int64 x, y;
    int64 g = exgcd(m1, m2, x, y); // m1*x + m2*y = g
    int64 diff = r2 - r1;
    if (diff % g != 0) return {-1, -1}; // 無解

    int64 m2_g = m2 / g;
    // p0 = x * (diff/g) mod (m2/g)
    int64 p0 = (x * (diff / g)) % m2_g;
    if (p0 < 0) p0 += m2_g;

    int64 new_r = r1 + m1 * p0;
    int64 new_m = m1 / g * m2; // lcm
    new_r %= new_m;
    if (new_r < 0) new_r += new_m;
    return {new_r, new_m};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    while (cin >> k) {
        int64 r, m;
        cin >> m >> r; // 注意輸入順序：m r
        bool ok = true;
        for (int i = 1; i < k; ++i) {
            int64 m2, r2;
            cin >> m2 >> r2;
            if (!ok) continue;
            auto [nr, nm] = merge(r, m, r2, m2);
            if (nr == -1) ok = false;
            else { r = nr; m = nm; }
        }
        cout << (ok ? r : -1) << '\n';
    }
    return 0;
}

關鍵細節

防溢出版合併 (推薦)

pair mergeSafe(int64 r1, int64 m1, int64 r2, int64 m2) {
    int64 x, y;
    int64 g = exgcd(m1, m2, x, y);
    int64 diff = r2 - r1;
    if (diff % g != 0) return {-1, -1};

    int64 m2_g = m2 / g;
    __int128 p0 = (__int128)x * (diff / g) % m2_g;
    if (p0 < 0) p0 += m2_g;

    __int128 new_r = r1 + (__int128)m1 * p0;
    __int128 new_m = (__int128)m1 / g * m2;
    new_r %= new_m;
    if (new_r < 0) new_r += new_m;
    return {(int64)new_r, (int64)new_m};
}

複雜度分析

• 每次合併：O(log max(mᵢ)) (擴展歐幾里得)
• 總計：O(k log M)，極快

相關題目

• HDU 1573 / 1014 / 3033 (EXCRT 經典)
• 「中國剩餘定理」互質版 (CRT)
• 「線性同餘方程」單方程 ax ≡ b (mod m)

總結

EXCRT 是解決不互質模數線性同餘方程組的標準算法。核心步驟：兩兩合併 → 擴展歐幾里得解線性同餘方程 → 更新模數為 lcm。掌握 exgcd、模運算性質、溢出防護，即可解決所有同類問題。本題為 EXCRT 入門經典題 (POJ 2891 / HDU 1573 同題)。

1. 上一篇文章： POJ 1019 Number Sequence：數位分組定位第 k 個數字
2. 下一篇文章： POJ 2828 插孔問題：線段樹離線處理逆序構造最終序列

關於C++

C++ 封裝向量（Vector）容器：自動擴容、迭代器與泛型實現

STL std::vector 是 C++ 最常用的動態陣列

C++ vs C#：建構子中呼叫虛擬函數、對話方塊視圖狀態持久化與 POD 型別深度解析

一、建構子/解構子中呼叫虛擬函數：C++ 與 C# 的根本差

Windows Socket 網路程式設計完整入門與範例碼

Windows Socket 概述 Windows Sock

LeetCode 198：打家劫舍問題完整解析與動態規劃實現

問題描述 你是一名專業強盜，計劃沿著一條街道依次打劫房屋。每