中国剩余定理（CRT）

解决问题类型

例题：洛谷 P1495 【模板】中国剩余定理（CRT）（本题需要使用 快速乘，否则超出 unsigned long long 的存储范围）。

给定 n 个两两互质的正整数，构成序列 {mn}。再给定序列 {an}， 有如下同余方程 求 x 的最小正整数解。

结论

令 ，。

然后考虑求出 Mi × pi + mi × qi = 1 的一组可行解 (pi, qi)。

由于 mi 两两互质，所以 Mi ⊥ mi，那么 gcd (Mi, mi) = 1。

根据裴蜀定理，该方程必然存在解，故使用 Exgcd 求解即可。

令 ei = Mi × pi，则 这就是 x 的最小正整数解。

证明

考虑 ei × ai 对 mj 取模的值，可以发现

(1) 式中，由于 ei = Mi × pi，而 Mi 是 mj 的倍数，所以结果为 0​。

(2) 式中，pi 和 qi 满足 Mi × pi + mi × qi = 1，等式两边对 mi 取模，即得 ei mod  mi = 1，再两边同乘 ai 就可以得证。

由此不难发现，将 代入第 i (i ∈ [1, n]) 个同余式中，ej × aj mod  mi = 0 (i ≠ j)，对运算结果无影响，而 ei × ai mod  mi = ai，刚好统计下来。故 CRT 得证。

算法流程

  1. 求出 。

  2. 求出 。

  3. 用 Exgcd 求出 Mi × pi + mi × qi = 1 的 pi。

    注意，此时 pi 可能为负数，可以通过 pi ← pi + mi，qi ← qi − Mi，将 pi 变为非负数。

  4. 通过公式 得到答案。

时间复杂度

时间复杂度为 Θ(n + n + nlog n + n) ≈ O(nlog n)，瓶颈在第三步求解不定方程。

Code

前置：

  • Exgcd 中的 lint exgcd(lint, lint, lint &, lint &);。
  • 快速乘中的 lint mul(lint, lint, lint);。
1
2
3
4
5
6
7
8
9
10
11
12
using lint = long long;
const int N = /*同余方程数量*/。

int n, a[N], m[N];
lint ans, p, q, M = 1, mm[N];

for (int i = 1; i <= n; ++i) M *= m[i];
for (int i = 1; i <= n; ++i) mm[i] = M / m[i];
for (int i = 1; i <= n; ++i) {
  exgcd(mm[i], m[i], p, q);
  ans = (ans + mul(mul(mm[i], p, M), a[i], M) % M + M) % M;
}

扩展中国剩余定理（ExCRT）

解决问题类型

例题：洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）。

给定序列 {mn} 和序列 {an}， 有如下同余方程 求 x 的最小正整数解。

两个方程

设方程为 将两式联立，可得 m1p − m2q = a2 − a1 可以使用扩展欧几里得算法求出 p, q 的一组解 p0, q0。

令 d = (m1, m2)。

那么这个方程的全部解即为 将解代入 (1) 中，可得 令 a′ = m1p0 + a1，m′ = [m1, m2]，则 x = a′ + km′，即 x ≡ a′ (mod  m′) 这样就成功将两个方程合并为一个方程。