中国剩余定理（CRT）小结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15685484.html

求：

$$\Large\begin{cases}S\equiv b_1\pmod {a_1}\\ S\equiv b_2\pmod {a_2}\\ \cdots\\ S\equiv b_i\pmod {a_i}\\ \cdots\\ S\equiv b_n\pmod {a_n}\\ \end{cases}$$

中 $S$ 的最小值。

考虑对于每一个 $b_i$ 暴力翻倍，然后加到答案里。

翻多少倍不会影响其他呢？翻 $\Large\frac{\prod_{j=1}^n a_j}{a_i}$ 倍!

那此时就是求 $b_i$ 翻多少倍满足满足 $\frac{\prod_{j=1}^n a_j}{a_i}\times k\equiv b_i\pmod {a_i}$？

由于本身就是 $b_i$ 翻倍，所以可以写成 $\frac{\prod_{j=1}^n a_j}{a_i}\times k\equiv 1\pmod {a_i}$？

可以看出 $k$ 就是 $\frac{\prod_{j=1}^n a_j}{a_i}$ 在模 $a_i$ 意义下的逆元，可以用exgcd拓展欧几里得来求。