中国剩余定理
Imakf
·
·
个人记录
求最小整数解。
\begin{cases}
x_1 \equiv a_1 (\bmod\ p_1) \\
x_2 \equiv a_2 (\bmod\ p_2) \\
... \\
x_n \equiv a_n (\bmod\ p_n)
\end{cases}
其中 p_1,p_2,...,p_n 两两互质。
考虑懒人解法：
对于一组方程 x \equiv a_1 (\bmod\ p_1) ，它的自然数解可以写成： x_1=kp_1+a_1\ (k \in N)
当我们把他放到 n 个方程组内考虑，希望这个 x_1 只在第 1 个方程组内有效，其他的方程组内，他都被 \bmod 成了 0。
如果这样可行，就只用求 \sum x_i。
令 M=\prod p_i,M_i=\dfrac{M}{p_i}
则有 x_i = M_i\times M_i^{-1}\times a_i。
注意有时候 $M$ 巨大，要快速乘。
### exCRT
excrt 就更不屑了。
直接考虑合并两个方程：
$$
\begin{cases}
x \equiv a_1 (\bmod\ p_1) \\
x \equiv a_2 (\bmod\ p_2) \\
\end{cases}
$$
第一个柿子的通解写成 $x_1=kp_1+a_1\ (k \in N)$，把它带入第二个柿子
$kp_1\equiv a_2-a_1 (\bmod\ p_2)
直接 exgcd 求解 k ，无解就方程组无解。
得到特殊解 kp_1+a_1 之后得到合并后的方程：
x\equiv kp_1+a_1 (\bmod\ \mathrm{lcm}(p_1,p_2))
就这么搞 m-1 次即可。