中国剩余定理（CRT）

Published on	7/29/2025
Created on	12/17/2021

中国剩余定理用于求解如下形式的一元线性同余方程组：

\begin{cases} x&\equiv a_1&(\mathrm{mod}\ m_1)\\ x&\equiv a_2&(\mathrm{mod}\ m_2)\\ x&\equiv a_3&(\mathrm{mod}\ m_3)\\ &\vdots\\ x&\equiv a_n&(\mathrm{mod}\ m_n)\\ \end{cases}

普通算法只适用于模数 $m_1,m_2,\dots,m_n$ 两两互质的情况。先上算法：

计算模数 $m_1,m_2,\dots,m_n$ 的积 $M$
对于第 $i$ $i$ 条方程，执行：
- 计算除 $m_i$ 外其他模数之积为 $m_i'$ ，也就是 $m_i'=\frac{M}{m_i}$
- 计算 $m_i'$ 在模 $n_i$ 意义下的逆元 $m_i'^{-1}$ ，即是要找最小正数满足 $m_i'm_i'^{-1}\equiv1\quad(\mathrm{mod}\ m_i)$
- 计算 $c_i=m_i'm_i'^{-1}$ ，对 $M$ 取模，而不是 $m_i$
最小正数答案即为： $\sum^n_{i=1}a_ic_i\quad(\mathrm{mod}\ M)$ 答案的周期为 $M$

证明：对于所有 $m_1',m_2',m_3',\dots,m_n'$ 中的其中一个 $m_i'$ ，其就为剔除了 $m_i$ 的 $M$ ，除其之外其他 $m'$ 均有一因子 $m_i$ 。即：

\forall j\neq i,\ m_j'\equiv 0\quad(\mathrm{mod}\ m_i)

所以，我们算出的答案满足，对于任意一条方程 $x\equiv a_i\quad(\mathrm{mod}\ m_i)$ ：

\begin{aligned} x&\equiv\sum^n_{j=1}a_jc_j&(\mathrm{mod}\ n_i)\\ &\equiv a_1m_1'm_1'^{-1}+\dots+a_ic_i+\dots+a_nm_n'm_n'^{-1} &(\mathrm{mod}\ n_i)\\ &\equiv 0+0+\dots+a_ic_i+\dots+0+0 &(\mathrm{mod}\ n_i)\\ &\equiv a_im_i' \underset{(\mathrm{mod}\ n_i)}{m_i'^{-1}} &(\mathrm{mod}\ n_i)\\ &\equiv a_i&(\mathrm{mod}\ n_i) \end{aligned}

参考代码

题目：P1495 【模板】中国剩余定理(CRT)/曹冲养猪 - 洛谷)

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
//---//
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

typedef unsigned int u;
typedef long long ll;
typedef unsigned long long llu;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)

const ll N = 11;

ll a[N], m[N];

void exgcd(ll a, ll b, ll &x, ll &y) {
  if (b) {
    exgcd(b, a % b, x, y);
    swap(x, y);
    y -= a / b * x;
  } else {
    x = 1;
    y = 0;
  }
}

signed main() {
  ll n, M = 1, x, y, c, ans = 0;
  scanf("%lld", &n);
  REP(i, 1, n) {
    scanf("%lld%lld", &m[i], &a[i]);
    M *= m[i];
  }
  REP(i, 1, n) {
    c = M / m[i];
    exgcd(c, m[i], x, y);
    c *= (x % m[i] + m[i]) % m[i];
    ans = (ans + a[i] * c % M) % M;
  }
  printf("%lld", ans);
}

// https://www.luogu.com.cn/record/61038480