【算法学习笔记】36：中国剩余定理（Chinese Remainder Theorem）求解线性同余方程组
中国剩余定理
假定存在
m
1
.
.
m
k
m_1..m_k
m1..mk两两互质，中国剩余定理旨在求解这样的线性同余方程组中的
x
x
x：
x
≡
a
1
(
m
o
d
m
1
)
x
≡
a
2
(
m
o
d
m
2
)
.
.
.
x
≡
a
k
(
m
o
d
m
k
)
x \equiv a_1~(mod~m_1) \\ x \equiv a_2~(mod~m_2) \\ ... \\ x \equiv a_k~(mod~m_k)
x≡a1 (mod m1)x≡a2 (mod m2)...x≡ak (mod mk)
定理给出的求解方式是，设：
M
=
∏
i
=
1
k
m
i
M
i
=
M
m
i
M= \prod_{i=1}^{k}m_i \\ M_i = \frac{M}{m_i}
M=i=1∏kmiMi=miM
易知
M
i
M_i
Mi和
m
i
m_i
mi互质。记
M
i
−
1
M_i^{-1}
Mi−1表示
M
i
M_i
Mi模
m
i
m_i
mi的逆，则定理给出的一个
x
x
x的解是：
x
=
∑
i
=
1
k
a
i
⋅
M
i
⋅
M
i
−
1
x = \sum_{i=1}^{k}a_i \cdot M_i \cdot M_i^{-1}
x=i=1∑kai⋅Mi⋅Mi−1
如何求 M i M_i Mi关于模 m i m_i mi的乘法逆元
前面学了快速幂求乘法逆元，但是要求模数是一个质数。但前面的线性同余方程组中只限制了不同的 m i m_i mi之间两两互质，并不要求 m i m_i mi是一个质数，所以可以用扩展欧几里得算法来求乘法逆元。
根据乘法逆元的定义：
若整数 b b b， m m m互质，并且对于任意的整数 a a a，如果满足 b ∣ a b~|~a b ∣ a，则存在一个整数 x x x，使得 a b ≡ a ⋅ x ( m o d m ) \frac{a}{b} \equiv a \cdot x(mod~m) ba≡a⋅x(mod m)，则称 x x x为 b b b的模 m m m乘法逆元，记为 b − 1 ( m o d m ) b^{-1}(mod~m) b−1(mod m)。
两边除以
a
a
a，再把
b
b
b乘到右边，就有：
b
⋅
x
≡
1
(
m
o
d
m
)
b \cdot x \equiv 1~(mod~m)
b⋅x≡1 (mod m)
这正是一个特殊的线性同余方程，可以用扩展欧几里得算法求出 x x x。
证明
只要证明中国剩余定理给出的解是满足线性同余方程组的一个合法解即可：
x
=
∑
i
=
1
k
a
i
⋅
M
i
⋅
M
i
−
1
x = \sum_{i=1}^{k}a_i \cdot M_i \cdot M_i^{-1}
x=i=1∑kai⋅Mi⋅Mi−1
只要对方程组中的每一条方程一个个带入校验即可。对于任意的第
i
i
i条方程，
x
x
x模
m
i
m_i
mi的结果必须是
a
1
a_1
a1。
考虑到解中的第 i i i项 a i ⋅ M i ⋅ M i − 1 a_i \cdot M_i \cdot M_i^{-1} ai⋅Mi⋅Mi−1中 M i − 1 M_i^{-1} Mi−1是 M i M_i Mi模 m i m_i mi下的逆，因此它们的乘积 M i ⋅ M i − 1 M_i \cdot M_i^{-1} Mi⋅Mi−1模 m i m_i mi一定余 1 1 1，进而这一项 a i ⋅ M i ⋅ M i − 1 a_i \cdot M_i \cdot M_i^{-1} ai⋅Mi⋅Mi−1模上 m i m_i mi一定余 a i a_i ai。
考虑到解中的第 j j j项（ j ≠ i j \neq i j=i），由于 M j M_j Mj中一定包含了一个因子 m i m_i mi，所以这一项 a j ⋅ M j ⋅ M j − 1 a_j \cdot M_j \cdot M_j^{-1} aj⋅Mj⋅Mj−1模 m i m_i mi一定余 0 0 0。
因此，所有项的加和模 m i m_i mi一定余 a i a_i ai，证毕。
例题：洛谷P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
模板题，注意中间结果可能会爆long long，所以要用__int128，由于是对
M
i
M_i
Mi求逆，按照题目数据范围这个exgcd求inv_rp的过程也要写成long long的。
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL& x, LL& y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
// by + (a % b)x = d
// by + (a - a/b * b) * x = d
// ax + by - (a/b) * b * x = d
// ax + b(y - (a/b) * x) = d
y -= a / b * x;
return d;
}
// b和m互质求b模m的逆
LL inv_rp(LL b, LL m) {
// bx = 1 (% m)
// bx = 1 + my
// bx + my' = 1
LL x, y;
exgcd(b, m, x, y);
return x;
}
LL crt(vector<int>& a, vector<int>& m) {
LL M = 1;
int n = a.size();
for (int i = 0; i < n; i ++ ) {
M *= m[i];
}
__int128 res = 0;
for (int i = 0; i < n; i ++ ) {
LL Mi = M / m[i];
res = (res + (__int128)a[i] * Mi * inv_rp(Mi, m[i])) % M;
}
return (res + M) % M;
}
int main() {
int n; cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i ++ ) {
cin >> a[i] >> b[i];
}
cout << crt(b, a) << endl;
return 0;
}