中国剩余定理

假定存在$m_1..m_k$两两互质，中国剩余定理旨在求解这样的线性同余方程组中的$x$：
$$\begin{gathered} x\equiv a_1(mod{m}_1) \\ x\equiv a_2(mod{m}_2) \\ ... \\ x\equiv a_k(mod{m}_k) \end{gathered}$$
定理给出的求解方式是，设：
$$\begin{gathered} M=\prod _{i=1}^k{m}_i \\ {M}_i=\frac{M}{m_i} \end{gathered}$$
易知$M_i$和$m_i$互质。记$M_i^{-1}$表示$M_i$模$m_i$的逆，则定理给出的一个$x$的解是：
$$x=\sum _{i=1}^k{a}_i\cdot M_i\cdot M_i^{-1}$$

如何求$M_i$关于模$m_i$的乘法逆元

前面学了快速幂求乘法逆元，但是要求模数是一个质数。但前面的线性同余方程组中只限制了不同的$m_i$之间两两互质，并不要求$m_i$是一个质数，所以可以用扩展欧几里得算法来求乘法逆元。

根据乘法逆元的定义：

若整数$b$，$m$互质，并且对于任意的整数$a$，如果满足$b|a$，则存在一个整数$x$，使得$\frac{a}{b}\equiv a\cdot x(modm)$，则称$x$为$b$的模$m$乘法逆元，记为$b^{-1}(modm)$。

两边除以$a$，再把$b$乘到右边，就有：
$$b\cdot x\equiv 1(modm)$$

这正是一个特殊的线性同余方程，可以用扩展欧几里得算法求出$x$。

证明

只要证明中国剩余定理给出的解是满足线性同余方程组的一个合法解即可：
$$x=\sum _{i=1}^k{a}_i\cdot M_i\cdot M_i^{-1}$$
只要对方程组中的每一条方程一个个带入校验即可。对于任意的第$i$条方程，$x$模$m_i$的结果必须是$a_1$。

考虑到解中的第$i$项$a_i\cdot M_i\cdot M_i^{-1}$中$M_i^{-1}$是$M_i$模$m_i$下的逆，因此它们的乘积$M_i\cdot M_i^{-1}$模$m_i$一定余$1$，进而这一项$a_i\cdot M_i\cdot M_i^{-1}$模上$m_i$一定余$a_i$。

考虑到解中的第$j$项（$j\ne i$），由于$M_j$中一定包含了一个因子$m_i$，所以这一项$a_j\cdot M_j\cdot M_j^{-1}$模$m_i$一定余$0$。

因此，所有项的加和模$m_i$一定余$a_i$，证毕。

例题：洛谷P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

模板题，注意中间结果可能会爆long long，所以要用__int128，由于是对$M_i$求逆，按照题目数据范围这个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) = dy -= a / b * x;return d;
}// b和m互质求b模m的逆
LL inv_rp(LL b, LL m) {// bx = 1 (% m)// bx = 1 + my// bx + my' = 1LL 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;
}