中国剩余定理

中国剩余定理（CRT）解决的是这样一种同余方程组：

\[\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ x \equiv a_3 \pmod{m_3} \\ ... \\ x \equiv a_n \pmod{m_n} \\ \end{cases}\]

其中对 \(\forall i \neq j\) 均有 \(m_i \bot m_j\)，即它们两两互质

算法的流程是：

  • 令 \(M\) = \(\prod_{i = 1}^n m_i\)
  • 对于每个 \(i\)，令 \(M_i = \frac{M}{M_i}\)
  • 对于每个 \(i\)，令 \(t_i \equiv M_i^{-1} \pmod{m_i}\)
  • 则原同余方程组的通解是
\[x = \sum_{i = 1}^n a_i t_i M_i + kM (k \in \mathbf{Z})\]
证明

我们给出证明，对于每一个 \(i\)，则对于任意的 \(j\) ：

  • 当 \(i = j\) 时，\(x = a_i t_i M_i \equiv a_i \pmod{m_i}\)
  • 当 \(i \neq j\) 时，因为 \(m_i = \prod_{j \neq i}\) 是 \(m_j\) 的倍数，因此 \(a_i t_i M_i \equiv 0 \pmod{m_j}\)
  • 因此
\[\sum_{i = 1}^n a_i t_i M_i \equiv a_i \pmod{m_i}\]

洛谷的模板题涉及大数乘法，要开 __int128 才能过:

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int MAXN = 14;
i128 a[MAXN], m[MAXN], sm = 1, ans, n, t[MAXN];
void exgcd(i128 a, i128 b, i128 &x, i128 &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}
i128 getinv(i128 a, i128 p)
{
    i128 x, y;
    exgcd(a, p, x, y);
    return (x + p) % p;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll x;
    cin >> x, n = x;
    for (int i = 1; i <= n; i++)
        cin >> x, m[i] = x, cin >> x, a[i] = x, sm *= m[i];
    for (int i = 1; i <= n; i++)
    {
        t[i] = getinv(sm / m[i] % sm, m[i]);
        ans = (ans + a[i] * t[i] * sm / m[i]) % sm;
    }
    x = ans;
    cout << x;
    return 0;
}