今天在$xsy$上翻题翻到了一道扩展$CRT$的题，就顺便重温了下
中国剩余定理是用于求一个最小的$x$，满足$x\equiv c_i \pmod(m_i)$。
正常的$CRT$有一个微小的要求，就是$\forall i,j (m_i,m_j)=1$。
在某些情况下，这个式子无法被满足，这个时候就要用扩展$CRT$来求解了。
我们先假设我们只有两条方程要被求解，它们分别是：
$\begin{cases} x\equiv c_1 \pmod{m_1}\\x\equiv c_2 \pmod{m_2}\end{cases}$
我们考虑将同余去掉，就变成了：
$\begin{cases} x= c_1+m_1k_1\\x= c_2+m_2k_2\end{cases}$
联立一波，得：
$c_1+m_1k_1=c_2+m_2k_2$
$m_1k_1=(c_2-c_1)+m_2k_2$
若该方程存在解，则有$(m1,m2)|(c_2-c_1)$，否则无解
下面令$d=(m1,m2)$。
我们对等式两边全部除以$d$，得：
原文：https://www.cnblogs.com/xiefengze1/p/10350652.html