中国剩余定理（CRT）

例题：P1495

---

求解问题：

中国剩余定理求解的问题如下：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

有一堆物品，它的数量被 $3$ 除后余 $2$，被 $5$ 除后余 $3$，被 $7$ 除后余 $2$，求有多少个？

前置知识：

• 扩展欧几里德

---

求解过程：

我们可以将这个问题用数学的方式表达：

$$\begin{cases} x\equiv a_1 \pmod {m_1} \\ x\equiv a_2 \pmod {m_2}\\x\equiv a_3 \pmod {m_3}\\\quad\quad\quad\;\;\vdots\end{cases}$$

其中，方程数量为 $k$。

先将这道题简单化。

我们能否将 $x$ 拆分成三份，然后再将三份加起来求解呢？

如果这三份分别称为 $n_1,n_2,n_3$，让其满足

$$\begin{cases} n_1\equiv a_1 \pmod {m_1} \\ n_2\equiv a_2 \pmod {m_2}\\n_3\equiv a_3 \pmod {m_3}\end{cases},\; x=n_1+n_2+n_3$$

---

在此补上一点定义：

• $M=\prod m$，所有 $m$ 的乘积

• $M_i=\frac{\prod m}{m_i}$，即除去 $m_i$，所有 $m$ 的乘积

• $N_i=\frac{1}{M_i} \bmod m_i$，即 $M_i$ 在 $m_i$ 意义下的逆元

考虑让：

$$n_i={a_i \times M_i \times N_i}$$

此时，因为 $N_i$ 是 $M_i$ 在 $m_i$ 意义下的逆元，所以 $N_i \times M_i \equiv 1 \pmod {m_i}$，此时满足 $n_i \equiv {a_i} \pmod {m_i}$

然后对于 $j \neq i$，因为 $n_i$ 中含有 $M_i$，而 $M_i$ 中一定含有 $m_j$，所以 $n_i \equiv 0 \pmod{m_j}$

因此一加就可以发现，$x=n_1+n_2+n_3$ 是符合的。

这样就知道特解了。

那一般我们求的都是最小解，或者说，如果想求所有解的话，只需要加上或减去 $M$ 就可以了

还是那个道理，如果说你要保证 $n_1\equiv a_1 \pmod {m_1}$，那么加/减的东西就要是 $m_1$ 的倍数

如果又要 $n_2\equiv a_2 \pmod {m_2}$，还要 $n_3\equiv a_3 \pmod {m_3}$，那么加/减的东西就要是 $m_1$、$m_2$、$m_3$ 的倍数，lcm 就好了。

当然你已经保证 $m_1$、$m_2$、$m_3$ 互质的话就不用 lcm 了。

推广同理

---

还有，求逆元的方法，可以用扩欧，也可以用快速幂

扩欧就是 $M_i\times N_i + k\cdot m_i=1$，因为 $M_i$ 不含 $m_i$ （除非是你没有互质），所以 $\gcd(M_i,m_i)=1$，要 $N_i$ 即可

搞掂，收工