拓展中国剩余定理总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15817918.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$ 的最小值。

然而此时并不互质。

我们假设前 $i$ 个式子我们求出当前满足答案的数 $m$，设 $s=\prod_{j=1}^{i=1}a_i$，我们现在要求满足:

$$\Large m+xs\equiv b_i \pmod {a_i}$$

时的最小 $x$。

变换一下:

$$\Large sx+a_iy\equiv b_i-m\pmod {a_i}$$

然后就可以用拓展欧几里得求出 $x$ 了。

无解情况代入验证即可。