中国剩余定理，Chinese Remainder Theorem，又称CRT，我们接下来就讲一下这个算法的原理。
要说原理，就得从古代说起。
（你到底是在讲编程课还是在讲历史课）
（真的是在将编程课）
在古代，有一个问题，叫做“物不知数问题”，原文是这样的：
- 有物不知其数
- 三三数之剩二
- 五五数之剩三
- 七七数之剩二
- 问物几何？
这个问题翻译过来就是问以下方程的所有正整数解：
$ \begin{cases} x \equiv 2 \pmod{3} \ x \equiv 3 \pmod{5} \ x \equiv 2 \pmod{7} \end{cases} $
这个问题在后来有一个解了，解出来这个问题的人，编了一首诗，叫做“孙子歌诀”，原文：
- 三人同行七十稀
- 五树梅花廿一支
- 七子团圆正半月
- 除百零五便得知
这个解翻译过来就是说，若设 $r_3$ 为方程中 $x$ 模 $3$ 的余数，$r_5$、$r_7$ 同理，那么所有解 $x$ 一定满足：
$x \equiv r_3 \times 70+r_5 \times 21+r_7 \times 15 \pmod{105}$
其中 $105$ 的实际来源是上面三个方程的模数的 $\text{lcm}$，即 $\text{lcm}(3,5,7)=3 \times 5 \times 7=105$。
关于 $70$、$21$、$15$ 的来源下面再说，我们先证明一下这个解是正确的。
由于 $105$ 是三个模数的 $\text{lcm}$，所以说如果 $x$ 是满足条件的，$x-105$、$x+105$ 都是满足条件的（此处暂时忽略“正整数解”的限制），显然。
所以我们就只用证明解 $x=\color{orangered} r_3 \times 70 \color{default}+\color{orange} r_5 \times 21 \color{default}+\color{royalblue} r_7 \times 15$ 合法即可。
我们把这个解带入到第一个方程式 $x \equiv r_3 \pmod{3}$ 里：
我们把方程式换种写法，变成 $x \bmod 3=r_3$。
那么，我们再把 $x$ 的解带入进去，变成 $(\color{orangered} r_3 \times 70 \color{default}+\color{orange} r_5 \times 21 \color{default}+\color{royalblue} r_7 \times 15 \color{default}) \bmod 3=r_3$。
可以发现，其实黄色项（中间）和蓝色项（最后）是可以被 $3$ 整除的，所以可以直接删掉，只保留橙色项（最前），变成 $\color{orangered} r_3 \times 70 \color{default} \bmod 3=r_3$
由于 $70 \bmod 3=1$，所以上述方程一定成立，显然。
带入到其他方程式也是差不多的证法，此处略。
有了上面那个具体的例子，我们就可以来解决抽象的例子了：
$ \begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ x \equiv a_3 \pmod{m_3} \ \dots \ x \equiv a_k \pmod{m_k} \end{cases} $
（说一下，CRT只能解决那些 $m_i$ 和 $m_j$ 两两互质的上述类型同余方程）
有了上面的启发，我们可以设 $x$ 的解为 $(a_1 \times c_1+a_2 \times c_2+a_3 \times c_3+\dots+a_k \times c_k) \bmod (\prod m_i)$。
接下来我们考虑构造 $c$ 数组。
有了上述证明的启发，我们可以列出一个 $c$ 数组要满足的条件列表：
$ \begin{cases} c_1 \bmod m_1=1 & c_1 \bmod m_2=0 & c_1 \bmod m_3=0 & \dots & c_1 \bmod m_k=0 \ c_2 \bmod m_1=0 & c_2 \bmod m_2=1 & c_2 \bmod m_3=0 & \dots & c_2 \bmod m_k=0 \ c_3 \bmod m_1=0 & c_3 \bmod m_2=0 & c_3 \bmod m_3=1 & \dots & c_3 \bmod m_k=0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ c_k \bmod m_1=0 & c_k \bmod m_2=0 & c_k \bmod m_3=0 & \dots & c_k \bmod m_k=1 \end{cases} $
我们先考虑构造 $c_1$（以 $c_1$ 为例）。
我们先满足第一行的第二到最后一列的所有条件，即 $c_1=\prod\limits_{i=2}^n m_i$，且 $c_1$ 在满足第一行第一列中的条件时，只能变成初始值的倍数。
我们设 $c_1$ 最后要变成初始值的 $d_1$ 倍，那么（$d_1$）就需要满足 $c_1 \times d_1 \bmod m_1=1$，由于 $m_i$、$m_j$ 两两互质，所以 $c_1$、$m_1$ 也是互质的，进而就可以构造 $d_1$ 为 $c_1$ 在模 $m_1$ 意义下的逆元即可。
注意到 $m_i$ 不一定都是质数，所以求逆元需要用exgcd（推荐）或者欧拉定理（不推荐）。
总结一下，如果我们设 $M=\prod m_i$，$M_i=M \div m_i$，$t_i$ 为 $M_i$ 在模 $m_i$ 意义下的逆元，那么最小正整数解就是 $(\sum a_iM_it_i) \bmod M$，通解 $x$ 满足 $x \equiv \sum a_iM_it_i \pmod{M}$。
注意到上面说“要保证 $m_i$ 和 $m_j$ 两两互质”，但如果不满足呢？就需要用到exCRT。
exCRT的原理与CRT完全相反，CRT是通过预处理数组一下子求出解，exCRT则是一个一个合并同余方程。
我们设当前要合并：
$ \begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \end{cases} $
那么考虑一下合并之后这个方程组会变成啥样。
遇到取模就要想到拆开，我们设 $k_1$ 和 $k_2$，然后把上面两个方程变成：
$ \begin{cases} x=k_1m_1+a_1 \ x=k_2m_2+a_2 \end{cases} $
所以还可以得到等式：
$k_1m_1+a_1=k_2m_2+a_2$
移项：
$k_1m_1-k_2m_2=a_2-a_1$
设 $k_2’=-k_2$，那么就变成了：
$k_1m_1+k_2’m_2=a_2-a_1$
这个方程可以用exgcd判断是否有解并求出一组解 $(k_1,k_2)$，所以就合并为了：
$x \equiv k_1m_1+a_1 \pmod{M}$
（其中 $M=\text{lcm}(m_1,m_2)$）
用上述合并方法，可以直接把多个方程合并为一个，就可以求出解了。