HDU 1573 X問題：中國剩餘定理（模線性方程組）模板詳解

題目大意

求滿足同餘方程組 X ≡ bᵢ (mod aᵢ) （i=0..M-1）且 1 ≤ X ≤ N 的正整數 X 的個數。N ≤ 1e9，M ≤ 10，aᵢ ≤ 10。

核心算法：合併同餘方程

將兩個方程 X ≡ a₀ (mod m₀) 和 X ≡ a (mod m) 合併為一個方程 X ≡ a₀' (mod m₀')。
利用擴展歐幾里得算法求解 m₀·x + m·y = gcd(m₀, m)。
若 (a - a₀) % gcd ≠ 0 則無解。
否則通解為 X = a₀ + m₀·t，代入第二個方程解得 t，從而得到新模數 m₀' = lcm(m₀, m) 和新餘數 a₀'。

遞歸合併所有方程

從 X ≡ 0 (mod 1) 開始，依次合併每個 X ≡ bᵢ (mod aᵢ)。最終得到 X ≡ a₀ (mod m₀)。
在 [1, N] 內滿足條件的整數個數為：⌊(N - a₀) / m₀⌋ + 1（若 a₀ = 0 需調整為 m₀）。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

// 合併 X ≡ a0 (mod m0) 和 X ≡ a (mod m)
// 返回是否有解，有解則更新 m0, a0
bool merge(ll& m0, ll& a0, ll m, ll a) {
    ll x, y;
    ll g = exgcd(m0, m, x, y);
    if ((a - a0) % g) return false;
    x = (a - a0) / g * x;
    ll mod = m / g;
    x = (x % mod + mod) % mod;
    a0 = a0 + m0 * x;
    m0 = m0 / g * m; // lcm
    a0 = (a0 % m0 + m0) % m0;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        ll N; int M; cin >> N >> M;
        vector a(M), b(M);
        for (int i=0;i> a[i];
        for (int i=0;i> b[i];
        ll m0 = 1, a0 = 0;
        bool ok = true;
        for (int i=0;i N) cout << 0 << '\n';
        else cout << (N - a0) / m0 + 1 << '\n';
    }
    return 0;
}

關鍵點

• 模數不一定互質，需用廣義中國剩餘定理（合併法）。
• 中間結果可能超過 64 位？題目 aᵢ ≤ 10，M ≤ 10，lcm ≤ 2520，long long 足夠。
• 餘數 0 的處理：X ≡ 0 (mod m) 等價於 X ≡ m (mod m)，但在計數公式中需注意 a₀=0 時第一個正整數解為 m₀。