扩展中国剩余定理 (ExCRT) 学习笔记
预姿势：
扩展中国剩余定理和中国剩余定理半毛钱关系都没有
问题：
求解线性同余方程组：
\[ f(n)=\begin{cases}
x\equiv a_1\pmod {m_1}\\
x\equiv a_2\pmod {m_2}\\
... ...\\
x\equiv a_n\pmod {m_n}\\
\end{cases}\]
的解\(x\)。
\(m\)两两之间不一定互质！
解法：
ExCRT的基本思想是将方程两两合并，合并规则如下：
定义
\[inv(a,b)
\]
表示\(a\)在模\(b\)意义下的逆元。
\[(a,b)
\]
表示\(gcd(a,,b)\)，即\(a\)和\(b\)的最大公约数。
则：
\[c=(inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})*\frac{(c_2-c_1)}{(m_1,m_2)})\%\frac{m_2}{(m_1,m_2)}*m_1+c_1
\]
\[m=\frac{m_1m_2}{(m_1,m_2)}
\]
就可以将
\[\begin{cases}
x\equiv c_1\pmod {m_1}\\
x\equiv c_2\pmod {m_2}\\
\end{cases}\]
合并成
\[x\equiv c\pmod m
\]
的形式。
然后就好了。。。
证明\推导过程：
看这里
反正我也不会推，背过公式就好了（理直气壮）
Code
inline void excrt(ll k1,ll k2)
{
ll m1=m[k1],m2=m[k2],c1=c[k1],c2=c[k2],g=gcd(m1,m2);
if((c2-c1)%g) {printf("-1\n");flag=1;return;}
ll cc=(inv(m1/g,m2/g)*(c2-c1)/g)%(m2/g)*m1+c1;
ll mm=m1*m2/gcd(m1,m2);
m[k2]=mm; c[k2]=cc; c[k2]=(c[k2]%mm+mm)%mm;
}
//然后最后答案就是c[n]
