本课时有配套视频讲解，购买后即可观看（永久有效）
中国剩余定理
一、课上练习
编程练习
- 中国剩余定理：L49963
二、知识总结
✨ 核心思想
中国剩余定理（CRT）是一种求解一元线性同余方程组的方法。当模数两两互素时，方程组有唯一解。该定理最早见于《孙子算经》中的"物不知数"问题，是中国古代数学的重要成就。
✨ 定理内容
问题描述：求解如下同余方程组：
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)其中 m₁, m₂, ..., mₖ 两两互素。
定理：设 M = m₁ × m₂ × ... × mₖ，Mᵢ = M / mᵢ，tᵢ 是 Mᵢ 模 mᵢ 的逆元（即 Mᵢ × tᵢ ≡ 1 (mod mᵢ)），则方程组的唯一解为：
x ≡ a₁ × M₁ × t₁ + a₂ × M₂ × t₂ + ... + aₖ × Mₖ × tₖ (mod M)
直观理解：每一项 aᵢ × Mᵢ × tᵢ 仅在模 mᵢ 时贡献 aᵢ，在模其他 mⱼ 时贡献 0，从而构造出满足所有条件的解。
✨ 构造性证明
对于第 i 项 aᵢ × Mᵢ × tᵢ：
- 当 j ≠ i 时，Mᵢ 包含 mⱼ 作为因子，所以 aᵢ × Mᵢ × tᵢ ≡ 0 (mod mⱼ)
- 当 j = i 时，Mᵢ × tᵢ ≡ 1 (mod mᵢ)，所以 aᵢ × Mᵢ × tᵢ ≡ aᵢ (mod mᵢ)
因此 x = Σ(aᵢ × Mᵢ × tᵢ) 满足所有同余方程。
唯一性：若 x₁ 和 x₂ 都是解，则 M | (x₁ - x₂)，所以在模 M 下解唯一。
✨ 代码实现
中国剩余定理（标准版）
1#include <iostream>
2using namespace std;
3typedef long long ll;
4
5// 扩展欧几里得算法，求 ax + by = gcd(a,b)
6ll exgcd(ll a, ll b, ll &x, ll &y) {
7 if (b == 0) {
8 x = 1; y = 0;
9 return a;
10 }
11 ll d = exgcd(b, a % b, y, x);
12 y -= (a / b) * x;
13 return d;
14}
15
16// 求 a 模 m 的逆元
17ll mod_inverse(ll a, ll m) {
18 ll x, y;
19 ll d = exgcd(a, m, x, y);
20 // d 应该为 1（因为 a 与 m 互素）
21 return (x % m + m) % m;
22}
23
24// 中国剩余定理
25// a[]: 余数数组, m[]: 模数数组, k: 方程个数
26ll crt(ll a[], ll m[], int k) {
27 ll M = 1; // 所有模数的乘积
28 for (int i = 0; i < k; i++) {
29 M *= m[i];
30 }
31
32 ll ans = 0;
33 for (int i = 0; i < k; i++) {
34 ll Mi = M / m[i]; // 除去当前模数的乘积
35 ll ti = mod_inverse(Mi, m[i]); // Mi 模 m[i] 的逆元
36 ans = (ans + a[i] % M * (Mi % M) % M * (ti % M)) % M;
37 }
38 return (ans % M + M) % M;
39}
40
41int main() {
42 int k;
43 cin >> k;
44 ll a[20], m[20];
45 for (int i = 0; i < k; i++) {
46 cin >> m[i] >> a[i]; // 读入模数和余数
47 }
48 cout << crt(a, m, k) << endl;
49 return 0;
50}扩展中国剩余定理（模数不互素）
1#include <iostream>
2using namespace std;
3typedef long long ll;
4typedef __int128 lll;
5
6ll exgcd(ll a, ll b, ll &x, ll &y) {
7 if (b == 0) {
8 x = 1; y = 0;
9 return a;
10 }
11 ll d = exgcd(b, a % b, y, x);
12 y -= (a / b) * x;
13 return d;
14}
15
16// 扩展中国剩余定理（excrt）
17// 逐步合并方程，不要求模数两两互素
18ll excrt(ll a[], ll m[], int k) {
19 ll A = a[0], M = m[0]; // 当前合并后的余数和模数
20 for (int i = 1; i < k; i++) {
21 // 合并 x ≡ A (mod M) 与 x ≡ a[i] (mod m[i])
22 // 即求 M*t + A ≡ a[i] (mod m[i])
23 // => M*t ≡ a[i] - A (mod m[i])
24 ll c = ((a[i] - A) % m[i] + m[i]) % m[i];
25 ll x, y;
26 ll d = exgcd(M, m[i], x, y);
27
28 if (c % d != 0) {
29 // 无解
30 return -1;
31 }
32
33 ll mod = m[i] / d;
34 // 防溢出使用 __int128
35 x = (lll)x % mod * (c / d) % mod;
36 A = A + (lll)M * x;
37 M = M / d * m[i]; // 新的模数为 lcm(M, m[i])
38 A = (A % M + M) % M;
39 }
40 return A;
41}
42
43int main() {
44 int k;
45 cin >> k;
46 ll a[25], m[25];
47 for (int i = 0; i < k; i++) {
48 cin >> m[i] >> a[i];
49 }
50 cout << excrt(a, m, k) << endl;
51 return 0;
52}✨ 应用示例
经典问题：物不知数
"今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？"
即求解：
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)手算过程：
- M = 3 × 5 × 7 = 105
- M₁ = 105/3 = 35, M₂ = 105/5 = 21, M₃ = 105/7 = 15
- 求逆元：
- 35 × t₁ ≡ 1 (mod 3) → 2 × t₁ ≡ 1 (mod 3) → t₁ = 2
- 21 × t₂ ≡ 1 (mod 5) → 1 × t₂ ≡ 1 (mod 5) → t₂ = 1
- 15 × t₃ ≡ 1 (mod 7) → 1 × t₃ ≡ 1 (mod 7) → t₃ = 1
- x = 2×35×2 + 3×21×1 + 2×15×1 = 140 + 63 + 30 = 233
- x mod 105 = 233 mod 105 = 23
验证：23 mod 3 = 2, 23 mod 5 = 3, 23 mod 7 = 2，全部正确。
✨ 解题步骤详解
- 检查条件：确认模数是否两两互素。若不互素，使用扩展 CRT
- 计算总模数 M：将所有模数相乘
- 计算各 Mᵢ：M 除以对应的 mᵢ
- 求逆元 tᵢ：用扩展欧几里得求 Mᵢ 模 mᵢ 的逆元
- 构造解：累加各项 aᵢ × Mᵢ × tᵢ
- 取模：对 M 取模得到最小正整数解
- 注意溢出：中间乘法可能需要
__int128或分步取模
✨ 常见错误
- 未检查模数是否两两互素就直接使用标准 CRT
- 中间计算乘法溢出
long long范围 - 逆元计算后忘记取模，导致结果为负数
- 扩展 CRT 中合并方程时
c % d != 0的无解判断遗漏 - 求逆元时未处理负数的情况（应
(x % m + m) % m） - 将 Mᵢ 和 mᵢ 混淆
✨ 算法评价
| 算法 | 时间复杂度 | 适用条件 |
|---|---|---|
| 标准 CRT | O(k log M) | 模数两两互素 |
| 扩展 CRT | O(k log M) | 任意模数 |
中国剩余定理在竞赛中应用广泛，常见于：大数分解后合并、NTT 中多模数合并结果、构造特定余数的数等。掌握标准版和扩展版是竞赛选手的基本功。