学习笔记 中国剩余定理

发表于 | 分类于 | 阅读次数：

中国剩余定理（CRT）可用于求线性同余方程组的最小整数解。

CRT

中国剩余定理（CRT）给出了下面这组关于 $x$ 的线性方程组当模数两两互质时的最小非负整数解
$$
\begin{cases}x \equiv a_1 & \pmod{m_1} \x \equiv a_2 & \pmod{m_2} \… \x \equiv a_n & \pmod{m_n}\end{cases}
$$
设 $m = \prod _{i = 1} ^n m_i$，$M_i = m / m_i$，$t_i$ 为 $M_i$ 在模 $m_i$ 意义下的逆元，那么整数解为
$$
x = \sum _{i = 1} ^n a_i M_i t_i
$$
证明：对于任意的 $i$，因为 $M_i = m / m_i$ 是除 $m_i$ 之外所有模数的倍数，那么对于任意的 $j \ne i$，$a_i M_i t_i \equiv 0 \ \ (\text{mod}\ m_j)$，因此解成立。

exCRT

那么当模数不一定两两互质时呢？此时要用到扩展中国剩余定理（exCRT）。

考虑数学归纳法。假设我们已经求出了前 $k - 1$ 个方程的一个解 $x$，记 $m = \text{lcm} (m_1, m_2,…,m_{k - 1})$，则 $x + i \cdot m (i \in \mathbb{Z})$ 是前 $k - 1$ 个方程的通解。

考虑第 $k$ 个方程，我们要求出一个整数 $t$，使得 $x + t \cdot m \equiv a_k \pmod{m_k}$。移项得 $t \cdot m \equiv a_k - x \pmod{m_k}$，这是一个线性同余方程，我们可以用扩展欧几里得算法检验并求出它的的解。如果有解，那么 $x’ = x + t \cdot m$ 就是前 $k$ 个方程的共同解。

因此，使用 $n$ 次扩展欧几里得算法就能得到上述方程组在模数不满足两两互质时的解。

Code

题目：洛谷P4777

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
39
40
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

int Gcd(int a, int b) {
	return b ? Gcd(b, a % b) : a;
}

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

inline int Mul(int x, int y, int Mod) {
	int res = 0;
	for (; y; y >>= 1, x = (x + x) % Mod)
		if (y & 1) res = (res + x) % Mod;
	return res;
}

signed main() {
	int n, a, m, fail = 0;
	scanf("%lld%lld%lld", &n, &m, &a);
	int lcm = m, res = a, x, y;
	for (int i = 2; i <= n; ++i) {
		scanf("%lld%lld", &m, &a);
		a = ((a - res) % m + m) % m;
		int g = Gcd(lcm, m);
		if (a % g != 0) fail = 1;
		ExGcd(lcm, m, x, y);
		int tmp = Mul(x, a / g, m);
		res += lcm * tmp;
		lcm = lcm / g * m;
		res = (res % lcm + lcm) % lcm;
	}
	printf("%lld\n", fail ? -1 : res);
	return 0;
}