中国剩余定理

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

简介 #

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

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

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

$$\left\{\begin{aligned} x \bmod 3 = 2 \\ x \bmod 5 = 3 \\ x \bmod 7 = 2 \\ \end{aligned}\right.$$

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

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

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

问题 #

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

$$\left\{\begin{aligned} x&≡a_1 \ (\bmod \ m_1)\\ x&≡a_2 \ (\bmod \ m_2)\\ &\cdots\\ x&≡a_k \ (\bmod \ m_k) \end{aligned}\right.$$

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

解法 #

设 $M=\prod^k_{i=1}m_i$.

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

设 $M_it_i≡1\pmod{m_i}$，$t_i$ 为 $M_i$ 关于模 $m_i$ 的乘法逆元.

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

$$\begin{aligned} x= \ &a_1M_1t_1 + a_2M_2t_2 + a_3M_3t_3 + \cdots + a_kM_kt_k\\ = \ &\sum^k_{i=1}a_iM_it_i \end{aligned}$$

其正确性显然.

模板 #

#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;
}