扩展中国剩余定理讲解

1.运用领域

　　扩展中国剩余定理是解决向下面列出的一元线性同余方程组的一种数论知识，可以求出下面方程组中最下的正整数$x$。但是扩展中国剩余定理和中国剩余定理有什么区别呢？中国剩余定理对于$mod$是有限制的，他对于$mod$要求为两两互质，然而扩展中国剩余定理对于$mod$没有要求。

　　$egin{cases} xequiv x_1 （mod_1）\ xequiv x_2 （mod_2）\ vdots vdots & \xequiv x_3 （mod_3）end{cases} $

2.前置知识

　　学习扩展中国剩余定理之前需要学习扩展$gcd$，以及一些简单的数学小知识。

3.讲解

　　注：博主部分证明的学习资源来自JZYshuraK的博客。

　　首先我们看上方列出的方程组，我们选择最上方的两个方程，看能不能合成。

　　我们将上面的通与方程进行变形可以得到下面的一个方程组。

　　　　$egin{cases} x=x_1+k_1 imes mod_1 \ x=x_2 +k_2 imes mod_2 end{cases}$

　　我们可以根据上面的方程组得到一个式子$x_1+k_1 imes mod_1=x_2+k_2 imes mod_2$，我们将这个式子进行移项可以得到$k_1 imes mod_1+(-k_2) imes mod_2=x_2-x_1$，这个式子很像$ax+by=c$的形式，所以很容易想到用扩展$gcd$，我们用扩展$gcd$可以求出来$k_1$的通项，但是前提是$gcd(mod_1，mod_2)| (x_2-x_1)$，如果上面的前提不满足，则这个同余方程组无法满足。

　　我们设$K_1，K_2$为$K_1 imes mod_1+(-K_2) imes mod_2=gcd(mod_1，mod_2)$的两个特解。我们将式子两边都乘以$frac{(x_2-x_1)}{gcd(mod_1，mod_2)}$，就能知道上述式子$k_1=K_1 imesfrac{(x_2-x_1)}{gcd(mod_1，mod_2)}$，$k_2=K_2 imesfrac{(x_2-x_1)}{gcd(mod_1，mod_2)}$。我们将$k_1，k_2$回带到原来的式子，能得到一个方程组（下方）。

　　　　$egin{cases} x=x_1+K_1 imesfrac{(x_2-x_1)}{gcd(mod_1，mod_2)} imes mod_1 \ x=x_2 +K_2 imesfrac{(x_2-x_1)}{gcd(mod_1，mod_2)} imes mod_2 end{cases}$

　　显然满足这个方程组的$K_1，K_2$不只一组，并且每一组$K_1，K_2$都对应一个$x$，所以我们能知道每两个解$Delta$就是$frac{(x_2-x_1)}{gcd(mod_1，mod_2)} imes mod_1$和$frac{(x_2-x_1)}{gcd(mod_1，mod_2)} imes mod_2$的倍数，所以$Delta$一定是$frac{mod_1 imes mod_2}{gcd(mod_1，mod_2)}$的倍数，即$Delta$是$lcm(mod_1，mod_2)$的倍数。我们就能知道$x=k_1 imes mod_1+x_1+t imes lcm(mod_1，mod_2)$。这样我们就将上面两个同余方程合成为$x equiv k_1 imes mod_1+x_1 （lcm(mod_1，mod_2)）$。

　　我们可以用$O（log）$，运用$Exgcd$合并两个同余方程，一共做$n$次，就能将所有的同余方程合并在一起了。最后我们得到的同余方程就是所有的$x$的通式。

　　代码（模板），下面以有$n$个同余方程为例。

#define ll long long
ll Exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) {x=1,y=0;return a;}
    ll gcd=Exgcd(b,a%b,x,y),tmp=x;
    x=y,y=tmp-a/b*y;
    return gcd;
}
ll Ex_crt()
{
    ll lcm=mod[1],last_x=x[1];
    for(int i=2;i<=n;i++)
    {
		ll lcm_a=((x[i]-last_x)%mod[i]+mod[i])%mod[i],x,y,k=lcm;
		ll gcd=Exgcd(lcm,mod[i],x,y);
		x=(x*lcm_a/gcd%(mod[i]/gcd)+(mod[i]/gcd))%(mod[i]/gcd);
		lcm=lcm*mod[i]/gcd,last_x=(last_x+k*x)%lcm;
    }
    return (last_x%lcm+lcm)%lcm;
}

　　如果有不懂的地方或者有所写有不对的地方，可以发评论，我会进行解答或改正。