INFO

若无特殊说明，本章涉及的变量皆为正整数。

简介

中国剩余定理最早发现于《孙子算经》中。

QUOTE

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即求满足下列条件的 $x$：

$$\{\begin{array}{r}xmod3=2\\ xmod5=3\\ xmod7=2\end{array}$$

它的通解公式为 $x=233+105k$。

《孙子算经》中只给出了最小正整数解，也就是 $k=-2$ 时的解：$x=23$。

不过，今天我们只关心中国剩余定理更普遍的应用。

问题

中国剩余定理指关于 $x$ 的同余方程组的解法：

$$\{\begin{array}{rl}x& \equiv a_1(mod{m}_1)\\ x& \equiv a_2(mod{m}_2)\\ & \cdots \\ x& \equiv a_k(mod{m}_k)\end{array}$$

其中 $a_1,a_2,\cdots ,a_k$ 两两互质。

解法

设 $M=\prod _{i=1}^k{m}_i$。

设 $M_i={\displaystyle \frac{M}{m_i}}$，即除 $m_i$ 外，其余所有 $m$ 的乘积。

设 $M_i{t}_i\equiv 1(\mathrm{mod}{m}_i)$，$t_i$ 为 $M_i$ 关于模 $m_i$ 的 乘法逆元。

利用以上数据可以构造一个解：

$$\begin{array}{rl}x=& a_1{M}_1{t}_1+a_2{M}_2{t}_2+a_3{M}_3{t}_3+\cdots +a_k{M}_k{t}_k\\ =& \sum _{i=1}^k{a}_i{M}_i{t}_i\end{array}$$

其正确性显然。

模板

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 16;
LL n, a[N], m[N], M[N], prodM = 1, ansX;

void exGcd(int a, int b, int &x, int &y) {
    if (b == 0) { x = 1, y = 0; return; }
    exGcd(b, a % b, x, y);
    int t = x; x = y, y = t - a / b * y;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i] >> m[i];
        prodM *= m[i];
    }
    for (int i = 1; i <= n; i ++) {
        M[i] = prodM / m[i];
        LL x = 0, y = 0;
        exGcd(M[i], m[i], x, y);
        ansX += a[i] * M[i] * (x + m[i]) % m[i];
    }
    cout << ansX % prodM;
    return 0;
}