中国剩余定理：

一次同余方程组：

一次同余方程组是指形如 $x \equiv a_i \mod m_i \quad (i = 1, 2, …, k)$ 的同余方程构成的组

\left\{\begin{matrix} x \equiv a_1 \mod m_1 \\ x \equiv a_2 \mod m_2 \\ x \equiv a_3 \mod m_3 \\ ... \\ x \equiv a_k \mod m_k \end{matrix}\right.

中国剩余定理的主要用途是解一次同余方程组，其中 $m_1, m_2, ..., m_k$ 互质

中国剩余定理：

令 $M = m_1 \cdot m_2 \cdot ... \cdot m_k$ （即所有 $m$ 的 lcm ）
$t_i$ 为同余方程 $\frac{M}{m_i} \cdot t_i \equiv 1 \mod m_i$ 的最小正整数解

则存在解 $x = \sum a_i \cdot \frac{M}{m_i} \cdot t_i$

通解为 $x + i \cdot M$

最小非负整数解为 $(x \% M + M) \% M$

（我承认这段是抄的 orz ）

原文看起来更方便：https://blog.csdn.net/niiick/article/details/80229217

$\frac{M}{m_i} \cdot t_i \equiv 1 \mod m_i$ 可转化为 $\frac{M}{m_i} \cdot t_i + m_i \cdot y = 1$ ，然后用 exgcd 求 $t_i$

其中 $gcd(\frac{M}{m_i}, m_i) = 1$ 意味着方程组一定有解

证明：

对于第 $k$ 个方程

①当 $i \neq k$ 时，有 $m_k|\frac{M}{m_i}$ ，即 $a_i \cdot \frac{M}{m_i} \cdot t_i \equiv 0 \mod m_k$

②当 $i = k$ 时，有 $\frac{M}{m_k} \cdot t_k \equiv 1 \mod m_k$ ，即 $a_k \cdot \frac{M}{m_k} \cdot t_k \equiv a_k \mod m_k$

故 $\sum a_i \cdot \frac{M}{m_i} \cdot t_i \equiv a_k \mod m_k$

代码：

（其中 LL 是 long long ，qcm 是快速乘）

LL crt(){
    LL bwl=0;
    for(int i=1;i<=k;++i){
        LL x,y;
        exgcd(M/m[i],m[i],x,y);
        if(x<0)  x=x%m[i]+m[i];
        bwl=(bwl+qcm(qcm(a[i],M/m[i]),x))%M;
    }
    return (bwl+M)%M;
}

孙子算经：

《孙子算经》：今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问物几何？

《算法统宗》：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。

其中 $70 = 7 \times 5 \times 2, 70 \% 3 = 1, 21 = 3 \times 7 \times 1, 21 \% 5 = 1, 15 = 3 \times 5 \times 1, 15 \% 7 = 1$

用 $70 \times 2 + 21 \times 3 + 15 \times 2 = 233$ 除 $3 \times 5 \times 7 = 105$ ，得到的余数 $23$ 即为答案

$70 = 3 \times 5 \times 2, 21 = 3 \times 7 \times 1, 15 = 3 \times 5 \times 1$ 三式中的最后一个乘数 $2, 1, 1$ 即为上文提到的 $d_i$

数字还挺吉利的 233

扩展中国剩余定理：

一次同余方程组：

扩展中国剩余定理的主要用途是解一次同余方程组，其中 $m_1, m_2, ..., m_k$ 不一定互质

2.扩展中国剩余定理：

令前 $k - 1$ 个方程组成的同余方程组的一个解为 $x$

且 $M$ 为前 $k - 1$ 个模数的 lcm

则前 $k - 1$ 个方程的方程组的通解为 $x + i \cdot M$

现在将第 $k$ 个方程加入

只需求一个正整数 $t$ ，使得

$x + t \cdot M \equiv a_k \mod m_k$

可以转化为 $M \cdot t + m_k \cdot y = a_k - x$

然后用 exgcd 求出 $t$

若此方程无解，则整个同余方程组无解

否则 $x + t \cdot M$ 为前 $k$ 个方程的方程组的一个解

（这段也是我抄的，原文和上边一样 orz ）

代码：

（其中 LL 是 long long ，qcm 是快速乘，三个参数分别为两个乘数和模数）

LL excrt(){
    LL M=m[1],ans=a[1];
    for(int i=2;i<=k;++i){
        LL x,y;
        LL d=gcd(M,m[i]);
        LL c=(a[i]-ans%m[i]+m[i])%m[i];
        if(c%d)  return -1;
        exgcd(M,m[i],x,y);
        x=qcm(x,c/d,m[i]/d);
        ans+=qcm(x,M,M*m[i]);
        M*=m[i]/d;
        ans=(ans%M+M)%M;
    }
    return ans;
}

细节：

1.有些题数字卡得严，必须要用快速乘

2.快速乘时注意第二个乘数必须为正，要用通解处理

3.每次快速乘的模数不一定一样，需要好好考虑

例题：

洛谷3868 猜数字

洛谷4777 扩展中国剩余定理