拓展中国剩余定理总结

求：

\[\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\) 了。

无解情况代入验证即可。