python/TangDou/AcWing/NumberTheory/中国剩余定理.md

### 中国剩余定理(CRT)
[原文链接](https://zhuanlan.zhihu.com/p/44591114)

#### 问题背景
孙子定理是中国古代求解一次同余式方程组的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元$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$为**两两互质**的整数
<br>
* 在扩展中国剩余定理（以下简称 $EXCRT$）中$m_1,m_2,...,m_n$并不满足互质条件，后者相对于前者更难解决。而两者都要运用一个算法来解决：**扩展欧几里得算法**。

下面的问题证明牵涉到一个 <font color='red'><b>最基本数学定理</b></font> ，如果有`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$ <font color='red'><b>一定</b></font> 是$5 \times 7=35$的倍数，假设$z=35k$。

那么就有$35k \equiv 1 (mod \ 3)$,而这时的 <font color='red'><b>就是$5 \times 7$模$3$的逆元$k$</b></font> 。这样，就转化为以前的知识，可以通过扩展欧几里得来求逆元，也就是求得了$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}]_7)$$。
 。

 最后 ，注意到，如果 $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/