扩展中国剩余定理 (ExCRT) 学习笔记
预姿势：
扩展中国剩余定理和中国剩余定理半毛钱关系都没有
问题：
求解线性同余方程组：
[ f(n)=egin{cases}
xequiv a_1pmod {m_1}\
xequiv a_2pmod {m_2}\
... ...\
xequiv a_npmod {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)}
]
就可以将
[egin{cases}
xequiv c_1pmod {m_1}\
xequiv c_2pmod {m_2}\
end{cases}]
合并成
[xequiv cpmod 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
");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]