问题：

给定2n整数$a_1,a_2...a_n, b_1,b_2...b_n$，求一个最小整数$x$满足$x\equiv a_i(mod\ b_i)$

思路：

先研究两个同余方程：

$\left\{ \begin{aligned} x \equiv a_1(mod\ b_1)\\ x \equiv a_2(mod\ b_2) \end{aligned} \right.$

1： 我们对他进行一下变形(其中$k_1,k_2$均为整数)：

$\left\{ \begin{aligned} x =b_1 * k_1 + a_1\\ x = b_2 * k_2 + a_2 \end{aligned} \right.$

2：联立消去x并且移项：

(1)$b_1*k_1 + a_1 = b_2*k_2 + a_2$
(2)$b_1*k_1 - b_2*k_2 = a_2 - a_1$

3：对于上式我们可以用扩展欧几里得求出它的一组解(这里$k_1,k_2$相当于$x,y$)。解出$k_1 = K_0$后我们立马可以得到$x = b_1*K + a_1$

4： 对于$x$可以写出它的通解,并且整理：

(1)$x = b_1*(K_0 + k *\frac{b_2}{gcd(b_1,b_2)}) + a_1$
(2)$x = b_1*K_0 + a_1 + k *lcm(b_1,b_2)$

5：设$A_0 = b_1*K_0 +a_1,B_0 =lcm(b_1,b_2)$得：

$x = k*B_0+A_0$

到了这里就可以发现和1的式子形式完全相同，所以就可以地推下去求解x了，对于这个方程组是否有解就看在求的过程中$gcd(b_i,b_{i + 1})|a_{i + 1} - ai$是否成立了