中国剩余定理

· · 个人记录

感谢Imagine的讲解

中国剩余定理

\ $$\begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \\ x\equiv a_2\ ({\rm mod}\ m_2) \\ \cdots \\ x \equiv a_n\ ({\rm mod}\ m_n)\end{cases}$$ 求最小的满足方程的$x$。 $\

由于网上对中国剩余定理的基本概念讲述的差不多了，这里就直接进入正题。

\

为了方便后面的描述，我们定义M=\prod\limits_{i=1}^nm_i\ ,\ w_i=\frac{M}{m_i}（这个定义不用于后面的扩展中国剩余定理和其它情况）。

我们的目的是想对于每一个方程找出一个比较特殊的p_i，使得p_i\equiv a_i\ {\rm mod}\ m_i，且p_i\equiv 0\ {\rm mod}\ m_j(j≠i)，因为求出所有的p_i后，\sum\limits_{i=1}^np_i\ {\rm mod}\ M就是我们的答案x。

观察p_i的限制，可以发现p_i应该为除了m_i以外的模数的最小公倍数（因为所有m_i互质，所以也就是w_i）的倍数，所以我们只需找到一个p_i使得p_i=k_iw_i（k_i为任意整数），且p_i\equiv a_i\ {\rm mod}\ m_i，那么这个p_i就是我们需要的。但是p_i\equiv a_i\ {\rm mod}\ m_i这个式子并不特殊，我们需要找一些更方便求解的式子来替换它。思考一下可以发现，其实我们只需要找到在满足p_i=k_iw_i的条件下，使得p_i \equiv 1\ {\rm mod}\ m_i的数，把p_i乘上a_i，就得到我们想要的p_i。

现在的问题就是如何找到满足条件的k_i，观察式子k_iw_i\equiv 1\ {\rm mod}\ m_i，可以看到k_i实际上是w_i在模m_i意义下的逆元，所以：p_i=a_i×w_i×k_i=a_i×w_i×w_i^{-1}

到这里，我们就成功得出了中国剩余定理的公式：

x\equiv \sum_{i=1}^ka_i×w_i×w_i^{-1}({\rm mod}\ M)

扩展中国剩余定理

\

由于一般情况下模数并不是两两互素，那么之前的做法就行不通了，所以我们就需要用到扩展中国剩余定理。

我们将上面的同余方程组更改一下：

\begin{cases}x=p_1m_1+a_1 \\ x=p_2m_2+a_2 \\ \cdots \\x=p_nm_n+a_n\end{cases}

对于这种形式，比较好的办法就是两两合并成一个方程。以合并前两个方程为例：

根据等式可得：m_1p_1+a_1=m_2p_2+a_2

移项：m_1p_1-m_2p_2=a_2-a_1

由于p_2可正可负，为了方便推导，我们变一下号：m_1p_1+m_2p_2=a_2-a_1

根据贝祖定理可以知道，若gcd(m_1,m_2)\nmid a_2-a_1，那么整个同余方程无解。

在有解的情况下则可用扩展欧几里得求出一组x,y使得：m_1x+m_2y=gcd(m_1,m_2)

两边同时乘上\frac{a_2-a_1}{gcd(m_1,m_2)}:m_1\frac{x(a_2-a_1)}{gcd(m_1,m_2)}+m_2\frac{y(a_2-a_1)}{gcd(m_1,m_2)}=a_2-a_1

根据多项式恒等定理：p_1=\frac{x(a_2-a_1)}{gcd(m_1,m_2)},p_2=\frac{y(a_2-a_1)}{gcd(m_1,m_2)}

那么：m_1p_1+a_1=a_2-m_2p_2=x 所以我们目前得到了满足前两个方程的一个x的解， 合并后的同余方程为：x \equiv m_1p_1+a_1\ {\rm mod}\ {\rm lcm}(m_1,m_2)

或者也可以是：

x \equiv a_2-m_2p_2\ {\rm mod}\ {\rm lcm}(m_1,m_2)

若我们要得到满足所有方程的解，那么我们只要把合并后的方程再与其它的方程合并，最后剩下的一个方程就是答案。

应用：【模板】扩展中国剩余定理

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=100010;
int n;
LL x,y,lcm,equ[N][2];
LL multi(LL a,LL b,LL p)
{
    a=(a%p+p)%p;b=(b%p+p)%p;LL ans=0;
    for(;a;a>>=1,b=(b*2)%p)if(a&1)ans=(ans+b)%p;
    return ans;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    LL val=exgcd(b,a%b,x,y);
    LL t=x;x=y;y=t-a/b*y;return val;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     scanf("%lld%lld",&equ[i][1],&equ[i][0]);
    for(int i=1;i<n;i++)
    {
        LL val=exgcd(equ[i][1],equ[i+1][1],x,y);
        lcm=equ[i][1]/val*equ[i+1][1];
        equ[i+1][1]=lcm;
        val=multi(x,(equ[i+1][0]-equ[i][0])/val,lcm);
        equ[i+1][0]=(multi(equ[i][1],val,lcm)+equ[i][0])%lcm;
    }
    printf("%lld\n",(equ[n][0]%equ[n][1]+equ[n][1])%equ[n][1]);
    return 0;
}

注意乘法溢出

其它情况

\begin{cases} w_1x \equiv a_1\ ({mod}\ m_1) \\ w_2x\equiv a_2\ ({mod}\ m_2) \\ \cdots \\ w_kx \equiv a_k\ ({mod}\ m_k)\end{cases}

若未知数x的系数不为1，当w_i与m_i互质时可以用exgcd求出逆元将w_i除到另一边，但是如果不互质又该怎么办？我们尝试能不能将其转换成互质的形式。

若要使得w_i与m_i互质，我们则需要对方程两边同时除上一个{\rm gcd}(w_i,m_i)，但是这样的正确性和更改后的方程又如何？

令Q_i={\rm gcd}(w_i,m_i)，那么w_i=Q_il_i,m_i=Q_ir_i。将方程转化为以下形式：

Q_il_i×x=a_i+Q_ir_i×q_i

其中q_i为任意整数，那么a_i=Q_i(l_i×x+r_i×q_i)，也就是说a_i必为Q_i的倍数，若不满足的话则方程组无解，否则我们可以将方程两边同时除以Q_i得到以下形式：

l_i×x=a_i'+r_i×q_i

可以发现l_ix\equiv a_i'\ {\rm mod}\ r_i\Leftrightarrow w_ix\equiv a_i\ {\rm mod}\ m_i

那么我们可以将原方程替换为l_ix\equiv a_i'\ {\rm mod}\ r_i，因为l_i,r_i互质，所以我们就可以用逆元将l_i除到方程右边，然后就可以用exCRT求解了。

应用：[NOI2018]屠龙勇士