中国剩余定理

定义

给出一个线性同余方程组：\(\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\ \ldots \\x\equiv a_n\pmod{m_n}\end{cases}\)，其中\(m_i\)两两互质，中国剩余定理用于求这样的方程组的解。

求解算法

思路与简单证明

将每一个方程分开讨论：

\[\begin{cases}x_i\equiv a_i\pmod{m_i}\end{cases},\quad 1\leq i\leq n\]

对于每一个方程，\(x_i\)应该满足\(x_i\equiv a_i\pmod{m_i}\)；

考虑其他方程，令\(x=\sum x_i\)，为了满足原来线性方程组的条件，可以简单地认为需要满足\(\sum x_j\equiv 0\pmod{m_i},\quad j\not=i\)；

假设\(x_i\)满足\(\forall m_j(j\not=i),x_i\bmod m_j=0\)。

设\(M=\prod_i m_i\)，

简单地令\(x_i\bmod \frac M{m_i}=0\)。

设\(k=\frac M{m_i},x_i=tk\)，于是\(tk\equiv a_i\pmod{m_i}\)，移项得\(t\equiv a_i\cdot k^{-1}\pmod{m_i}\)。

得出\(x_i=a_i\cdot k^{-1}\cdot k\)，为了得出最小解，\(x=\sum (a_i\cdot k^{-1}\cdot k)\bmod M\)，注意这里\(k^{-1}\)是指\(k\)在膜模\(m_i\)意义下的逆元，不能简单地消去。

扩展

思路与简单证明

当\(m_i\)不满足两两互质时，考虑两两合并：

对于两个方程：

\[x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\]

等式形式：

\[x=a_1k_1+m_1\\ x=a_2k_2+m_2\]

合并起来，移项：

\[a_1k_1+a_2k_2=m_2-m_1\]

用扩展欧几里得解该方程（注意无解情况），得出解\(k_1\)，那么 x 的一个特解就是\(a_1k_1+m_1\)，为了保证\(x\)满足原来两个方程，x 的通解可以表示成\(a_1k_1+m_1+k\cdot lcm(m_1,m-2)\)，于是得出新的同余方程：

\[x\equiv a_1k_1+m_1\pmod{lcm(m_1,m-2)}\]

实现

LL a[MAXN],m[MAXN];
LL CRT()
{
    LL M=m[1],A=a[1],t,d,x,y;
    for(int i=2;i<=n;i++)
    {
        d=exgcd(M,m[i],x,y);
        if((a[i]-A)%d)return -1;
        x=x*(a[i]-A)/d;
        t=m[i]/d;
        x=(x%t+t)%t;
        A=M*x+A;
        M=M*m[i]/d;
        A%=M;
    }
    A=(A%M+M)%M;
    return A;
}