既然是数论就做好面对一大堆式子的觉悟了吧
中国剩余定理应该都知道，就是可以用来搞同余方程组，但有个前提：模数得互质
遇到不互质的同余方程怎么办呢？
这就要求我们找到一个通式
扩展中国剩余定理就可以解决这个问题
假设现在有同余方程 \(\left\{\begin{matrix}x\equiv a_1\pmod{p_1} \\x\equiv a_2\pmod{p_2} \\... \\x\equiv a_n\pmod{p_n} \end{matrix}\right.\) 先看前两项可以化为$x=a_1+k_1p_1=a_2+k_2p_2$
移项得：$k_1p_1-k_2p_2=a_2-a_1$
根据贝祖定理，有解得满足：$(p_1,p_2)\vert (a_2-a_1)$
那同除一下？$\frac{p_1k_1}{(p_1,p_2)}-\frac{p_2k_2}{(p_1,p_2)}=\frac{a_2-a_1}{(p_1,p_2)}$
移项，可以化成同余的形式（$k_2$为商）$\frac{p_1}{(p_1,p_2)}k_\equiv \frac{a_2-a_1}{(p_1,p_2)}\pmod {\frac{p_2}{(p_1,p_2)}}$
再同除：$k_1\equiv \frac{\frac{a_2-a_1}{(p_1,p_2)}}{\frac{p_1}{(p_1,p_2)}}\pmod{\frac{p_2}{(p_1,p_2)}}$
除化为逆元：$k_1\equiv \frac{a_2-a_1}{(p_1,p_2)}inv(\frac{p_1}{(p_1,p_2)})\pmod {\frac{p_2}{(p_1,p_2)}}$
$k_1$就出来了：$k_1= \frac{a_2-a_1}{(p_1,p_2)}inv(\frac{p_1}{(p_1,p_2)})+K\frac{p_2}{(p_1,p_2)}$
回带：$x= \frac{a_2-a_1}{(p_1,p_2)}inv(\frac{p_1}{(p_1,p_2)})p_1+K\frac{p_2}{(p_1,p_2)}p_1+a_1$
又是一个同余的形式（$K$为商）：$x\equiv [\frac{a_2-a_1}{(p_1,p_2)}inv(\frac{p_1}{(p_1,p_2)})p_1+a_1]\pmod {\frac{p_2}{(p_1,p_2)}p_1}$
这样就又是一个同余方程的样子，$a_1$和$a_2$，$p_1$和$p_2$分别合并成一个 $A=\frac{a_2-a_1}{(p_1,p_2)}inv(\frac{p_1}{(p_1,p_2)})\%\frac{p_2}{(p_1,p_2)}\times p_1+a_1,P=\frac{p_2}{(p_1,p_2)}\times p_1$
这样两个同余方程就合成了一个
把剩下的一一合并，最后的$A$就是答案简单吧
