中国剩余定理（CRT）CSP-S

💡 核心思想

中国剩余定理（CRT）求解一组同余方程：x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ)。当模数两两互质时，有唯一解 x ≡ Σ aᵢ · Mᵢ · inv(Mᵢ, mᵢ) (mod M)，其中 M = ∏ mᵢ，Mᵢ = M / mᵢ。当模数不互质时，需要逐对合并方程，使用扩展欧几里得判断是否有解。

🎯 直觉理解

想象你在安排一个周期性的活动。你每 3 天去一次健身房，每 5 天去一次图书馆，每 7 天去一次电影院。问多少天后你第一次三项活动同一天进行？这就是 CRT：找一个数同时满足被 3 除余某个数、被 5 除余某个数、被 7 除余某个数。

📝 算法流程

1. 两两互质版本：
2. 计算 M = m₁·m₂·...·mₙ
3. 对每个 i，计算 Mᵢ = M / mᵢ
4. 计算 invᵢ = Mᵢ 在模 mᵢ 下的逆元（exgcd）
5. 答案 x = Σ aᵢ·Mᵢ·invᵢ (mod M)
6. 不互质版本：逐对合并两个方程，用 exgcd 求解

$$x \equiv \sum_{i=1}^{n} a_i \cdot M_i \cdot M_i^{-1} \pmod{M},\quad M = \prod m_i,\ M_i = M / m_i$$

📊 复杂度分析

💻 参考实现（C++）

#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, g = exgcd(b, a % b, x1, y1);
    x = y1; y = x1 - (a / b) * y1;
    return g;
}

ll inv(ll a, ll mod) {
    ll x, y;
    ll g = exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

// 中国剩余定理（模数两两互质）
ll crt(vector& a, vector& m) {
    int n = a.size();
    ll M = 1;
    for (ll mi : m) M *= mi;
    ll res = 0;
    for (int i = 0; i < n; i++) {
        ll Mi = M / m[i];
        res = (res + a[i] * Mi % M * inv(Mi, m[i]) % M) % M;
    }
    return res;
}

// 合并两个同余方程：x ≡ a1 (mod m1), x ≡ a2 (mod m2)
pair merge(ll a1, ll m1, ll a2, ll m2) {
    ll x, y;
    ll g = exgcd(m1, m2, x, y);
    if ((a2 - a1) % g != 0) return {-1, -1}; // 无解
    ll lcm = m1 / g * m2;
    ll t = ((a2 - a1) / g * x % (m2 / g) + (m2 / g)) % (m2 / g);
    ll a = (a1 + m1 * t) % lcm;
    return {a, lcm};
}

int main() {
    vector a = {2, 3, 2};
    vector m = {3, 5, 7};
    cout << crt(a, m) << endl; // 23
    return 0;
}

⚠️ 常见坑点

📚 相关题目