8.7 KiB
中国剩余定理(CRT)
问题背景
孙子定理是中国古代求解一次同余式方程组的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。
用现代数学的语言来分析这个问题，中国剩余定理给出了以下的一元线性同余方程组：
\large \left\{\begin{matrix}
x \equiv a_1 (mod \ m_1) \\
x \equiv a_2 (mod \ m_2) \\
... \\
x \equiv a_n (mod \ m_n)
\end{matrix}\right.
- 在中国剩余定理（以下简称
CRT) 中m_1,m_2,...,m_n为两两互质的整数 - 在扩展中国剩余定理（以下简称
EXCRT）中m_1,m_2,...,m_n并不满足互质条件，后者相对于前者更难解决。而两者都要运用一个算法来解决：扩展欧几里得算法。
下面的问题证明牵涉到一个 最基本数学定理 ，如果有a%b=c,则有(a+kb)%b=c(k为非零整数)，换句话说，如果一个除法运算的余数为c，那么被除数与k倍的除数相加（或相减）的和（差）再与除数相除，余数不变。这个是很好证明的。
问题1：计算一个整数 x ，使得它满足除以3余2、除以5余3、除以7余2。
如果能够找到三个整数 x_1,x_2,x_3 ，使得：
x_1 除以3余2、除以5余0、除以7余0；
x_2 除以3余0、除以5余3、除以7余0；
x_3 除以3余0、除以5余0、除以7余2；
那么令 x=x_1+x_2+x_3，利用上面的基本定理，我们知道这时的 x 就满足除以3余2、除以5余3、除以7余2。
分别称找到整数 x_1,x_2,x_3 的问题为问题1-1、问题1-2、问题1-3。可以看出这三个问题本质上是类似的。
下面对问题1-1继续分解，如果能够找到一个整数 y_1 满足 y_1 除以3余1、除以5余0、除以7余0，那么令 x_1=2\times y_1 ，就很容易验证这时的 x_1 就满足除以3余2、除以5余0、除以7余0。
因此定义
问题1-1-1为：寻找整数 y_1 满足 y_1 除以3余1、除以5余0、除以7余0；
问题1-2-1为：寻找整数 y_2 满足 y_2 除以3余0、除以5余1、除以7余0；
问题1-3-1为：寻找整数 y_3 满足 y_3 除以3余0、除以5余0、除以7余1。
这三个问题本质上是相同的。
如果找到了 y_1,y_2,y_3 ，那么就可以取 x=2\times y_1 + 3 \times y_2 + 2 \times y_3。
下面就以问题1-1-1为例：寻找整数 z 使得 z 除以3余1、除以5余0、除以7余0。
于是 z 一定 是5 \times 7=35的倍数，假设z=35k。
那么就有35k \equiv 1 (mod \ 3),而这时的 就是5 \times 7模3的逆元k 。这样，就转化为以前的知识，可以通过扩展欧几里得来求逆元，也就是求得了k \Rightarrow z \Rightarrow y \Rightarrow x \Rightarrow 最终的解。
将这个k记作[35^{-1}]_3,那么z就等于5 \times 7 \times [(5\times 7)^{-1}]_3,恰好就是 5 \times 7 \times 2=70,对应“凡三三数之剩一，则置七十”一句及“三人同行七十稀”一句。
于是类推得到，
问题1-1-2的解答是 3\times 7 \times [(3 \times 7)^{-1}]_5 ，恰好就是 3 \times 7 \times 1=21 ，对应“五五数之剩一，则置二十一”一句及“五树梅花廿一枝”一句；
问题1-1-3的解答是 3 \times 5 \times [(3\times 5)^{-1}]_7 ，恰好就是 3\times 5\times 1=15 ，对应“七七数之剩一，则置十五”一句及“七子团圆月正半”一句。
所以将分解的问题复原，可得：
$$x=2\times (5 \times 7 \times [(5\times 7)^{-1}]_3)+3\times (3\times 7 \times [(3\times 7)^{-1}]_5)+2\times (3\times 5 \times [(3 \times 5)^{-1}]_。
最后 ，注意到，如果 x 满足除以3余2、除以5余3、除以7余2，那么 x+3\times 5 \times 7 也同样满足。
因此要计算满足要求的最小的非负整数，就只需要计算总和除以105的余数即可。——对应“除百零五便得知”一句。
下面要讨论的是：如果有多个满足要求的整数，那么它们之间有什么关系呢？
假设 X,Y 都满足“除以3余a、除以5余b、除以7余c”。
观察 X-Y 会发现， X-Y 满足“除以3余0、除以5余0、除以7余0”。因此 X-Y一定是 3\times 5 \times 7 的倍数。
这也就是说，在“模105同余”的意义下，之前通过分解问题、组合解答的方法所得到的 x 恰恰就是唯一解。
下面把这个问题一般化：假设整数m_1,m_2,m_3,...,m_n两两互素，则对于任意的整数 a_1,a_2,a_3,...,a_n ，方程组
$\large
\left{\begin{matrix}
x \equiv a_1 (mod \ m_1) \
x \equiv a_2 (mod \ m_2) \
... \
x \equiv a_n (mod \ m_n) \
\end{matrix}\right.
$
都存在整数解，且若X,Y都满足该方程组，则必有 \large \displaystyle X \equiv Y \ (mod \ M) ，其中 \large \displaystyle M=\prod _{i=1}^{n}m_i。
具体而言，
\large \displaystyle x \equiv \sum_{i=1}^{n}a_i \times \frac{M}{m_i} \times \begin{bmatrix}
(\frac{M}{m_i})^{-1}
\end{bmatrix}
_{m_i} \ (mod \ M)$$ 。
——这就是我非常看重和喜欢的中国剩余定理(Chinese remainder theorem, CRT)。
例题：
[P3868 [TJOI2009] 猜数字](https://www.luogu.com.cn/problem/P3868)
```c++
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
int n;
LL a[N], m[N];
LL M = 1, ans;
LL x, y;
//龟速乘
LL qmul(LL a, LL k, LL b) {
LL res = 0;
while (k) {
if (k & 1) res = (res + a) % b;
a = (a + a) % b;
k >>= 1;
}
return res;
}
//扩展欧几里得
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++) scanf("%lld", &m[i]), M *= m[i]; // M是累乘积
// a[i]可能为负数，需要预处理
for (int i = 1; i <= n; i++) a[i] = (a[i] % m[i] + m[i]) % m[i];
//中国剩余定理
for (int i = 1; i <= n; i++) {
exgcd(M / m[i], m[i], x, y); //求逆元x
x = (x % m[i] + m[i]) % m[i]; //防负数
ans = (ans + qmul(a[i], M / m[i] * x, M)) % M; //调用龟速乘
}
printf("%lld\n", ans);
return 0;
}
```
[P1495 【模板】中国剩余定理(CRT)/曹冲养猪](https://www.luogu.com.cn/problem/P1495)
```c++
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
//曹冲养猪 洛谷 P1495
//曹冲养猪 AcWing 1298
int n;
LL a[N], m[N];
LL M = 1, x, y, ans;
//龟速乘
LL qmul(LL a, LL k, LL b) {
LL res = 0;
while (k) {
if (k & 1) res = (res + a) % b;
a = (a + a) % b;
k >>= 1;
}
return res;
}
//扩展欧几里得
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
scanf("%d", &n); //建立猪圈的次数
// m[1]=3 第1次建立3个猪圈
// a[1]=1 第1次有1只猪无家可归,也就是余数
// 也就是 x % 3 = 1
for (int i = 1; i <= n; i++) scanf("%lld%lld", &m[i], &a[i]), M *= m[i];
// a[i]可能为负数，需要预处理
// for (int i = 1; i <= n; i++) a[i] = (a[i] % m[i] + m[i]) % m[i];
for (int i = 1; i <= n; i++) {
exgcd(M / m[i], m[i], x, y); //求逆元x
x = (x % m[i] + m[i]) % m[i]; //防负数
ans = (ans + qmul(a[i], M / m[i] * x, M)) % M; //调用龟速乘
}
printf("%lld\n", ans);
return 0;
}
```
参考题解：https://www.acwing.com/solution/content/74377/