中国剩余定理（CRT）求解一组两两互质模数下的同余方程组，是数论中最重要的定理之一，广泛应用于密码学、大数计算和竞赛编程。
一、问题形式
Mermaid · 渲染中（下方为源码）
graph TD A[x ≡ a_i mod m_i] --> B[m_i 两两互质] B --> C[合并为单同余式] C --> D[中国剩余定理]
求解满足以下条件的最小正整数 x：
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₙ (mod mₙ)
其中 m₁, m₂, ..., mₙ 两两互质。
二、定理内容
设 M = m₁ × m₂ × ... × mₙ，Mᵢ = M / mᵢ，则：
x = Σ aᵢ × Mᵢ × Mᵢ⁻¹ (mod M)
其中 Mᵢ⁻¹ 是 Mᵢ 关于 mᵢ 的模逆元。
解在 mod M 意义下唯一。
三、代码实现
// 中国剩余定理：m[] 两两互质
long crt(long[] a, long[] m, int n) {
long M = 1;
for (int i = 0; i < n; i++) M *= m[i];
long x = 0;
for (int i = 0; i < n; i++) {
long Mi = M / m[i];
long inv = modInverse(Mi, m[i]); // exgcd 求逆元
x = (x + a[i] * Mi % M * inv) % M;
}
return (x % M + M) % M;
}
long modInverse(long a, long mod) {
long[] res = exgcd(a, mod);
return (res[1] % mod + mod) % mod;
}
long[] exgcd(long a, long b) {
if (b == 0) return new long[]{a, 1, 0};
long[] r = exgcd(b, a % b);
return new long[]{r[0], r[2], r[1] - (a / b) * r[2]};
}