【数论】CRT 与 ExCRT

中国剩余定理及扩展中国剩余定理

欢迎各位持续向我私信好的 CRT 及 ExCRT 的题目/qq

中国剩余定理(Chinese Remainder Theorem, CRT)和扩展中国剩余定理(Extension of Chinese Remainder Theorem, ExCRT)学习笔记。

一. 求解目标

对于任意两个 m_i,m_j 满足 \gcd(m_i,m_j)=1，存在同余方程组：

\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\x\equiv a_3\pmod{m_3}\\\cdots\cdots\\x\equiv a_n\pmod{m_n}\\\end{cases}

我们希望能够求出它的最小非负整数解 x_0。

二.求解方法

我们定义几个变量的值。首先存在 \alpha=\prod\limits_{i=1}^{n}m_i，也就是令 \alpha 表示所有模数的乘积，接下来如果要表示不包含某一个方程模数 m_i 的乘积，可以表示为 \dfrac{\alpha}{m_i} 记作 \alpha_i，对于 \alpha_i 存在于 \bmod m_i 意义下的的逆元，我们可以把它记作 inv_i，这时候一定存在 \alpha_i\times inv_i\equiv 1\pmod m_i。

此时我们计算序列 c 满足 c_i=\alpha_i\times inv_i，之所以 c_i 不为 1 是因为我们在实数域中进行讨论，并没有在 \bmod m_i 意义下进行讨论，因此他并不等于 1。特别的，此时存在方程组的唯一合法解 x_0 使得：

x_0=\sum\limits_{i=1}^{n}a_ic_i\pmod\alpha

对于模板题「曹冲养猪」我们可以用如下代码进行求解：

#include<bits/stdc++.h>
#define int long long
int n,a[99],m[99],al[99],mul=1,ans;
int Exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }int d=Exgcd(b,a%b,x,y),t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&m[i],&a[i]);
        mul=mul*m[i];
    }for(int i=1;i<=n;i++){
        al[i]=mul/m[i];
        int x=0,y=0;
        Exgcd(al[i],m[i],x,y);
        if(x<0)x+=m[i];
        ans+=a[i]*al[i]*x;
    }printf("%lld\n",ans%mul);
    return 0;
}

正确性证明

为什么这组解是正确的？我们不妨令 i=1,2,3,\cdots,n 进行讨论。当且仅当 i\neq j 的时候，存在 \alpha_j\equiv 0\pmod{m_i}，也就是说除了 \alpha_i 以外所有的 \alpha_j 都包含 m_i 这个因数，这是显然的。而我们确定 c_i 的定义之后，同时可以确定的是 c_i\equiv\alpha_i\times(inv_i\bmod m_i)\equiv 1\pmod{m_i}，我想这从逆元的角度理解应该是可以接受的，因此代入有：

\begin{aligned}x\equiv&\sum\limits_{j=1}^{n}a_jc_j&\pmod{m_i}\\\equiv& a_ic_i&\pmod{m_i}\\\equiv&a_i\times\alpha_i\times(inv_i\bmod m_i)&\pmod {m_i}\\\equiv& a_i&\pmod{m_i}\end{aligned}

因此，我们可以确认对于每一个 i\in\{1,2,3,\cdots,n\} 都存在 x\equiv a_i\pmod{m_i}，由此我们进一步推出结论，每一组 \{a_i\} 都对应唯一的一组解，换言之我们可以确定数列 a 与其特定解 x_0 存在双射关系（即一一映射）。

扩展形式

我们考虑一种情况，如果模数并非两两互质，又应该怎么解决这个问题？实际上，如果我们寄希望于对 CRT 的内容进行修改于扩展，绝对会遭致当头棒喝——CRT 的核心在于求取逆元构造解，而在不互质的情况下这个逆元甚至可能不存在，因此我们只能完全抛弃先前的思想，更进一步地讨论新的方法。

考虑一件事情：我们解寻常方程组的方式是进行合并方程，从而实现化简的需求。在正常的研究当中，我们希望能够从两个方程组之间的合并方法进行归纳，然后我们就可以进一步推广到所有方程。这其中有两个难点，首先在于两个特殊例子的合并法则能否推广至全体（且为什么），另一个在于这样的变化是否是等价的——合并结果是否包含原来的所有解？是否不会多出新的解？这是需要证明的。

那么我们从简单的模式开始。

存在同余方程 \begin{cases}x=r_1\pmod{m_1}\\x=r_2\pmod{m_2}\end{cases}，我们跳脱出同余形式将其写作 x=k_1m_1+r_1=k_2m_2+r_2。

确认此时对于右边两个式子的未知数有且仅有 k_1,k_2，如果我们移项之后就可以得到 k_1m_1-k_2m_2=r_2-r_1，也就是说这是一个不定方程，通过裴蜀定理可以判定是否有解，而剩下的工作可以交给 Exgcd 进行求解，这显然是简单的。我们用 d=\gcd(m_1,m_2) 将两边同时约化之后，记 p=\frac{m}{\gcd(m_1,m_2)} 然后求出来一组特解 \lambda_1p_1+\lambda_2p_2=1，表示出 k 就可以得到：

\begin{cases}k_1=\dfrac{r_2-r_1}{d}\lambda_1\\k_2=-\dfrac{r_2-r_1}{d}\lambda_2\end{cases}

我们任取一个 k 代回原式之中就可以得到 x=\dfrac{r_2-r_1}{d}\lambda_1m_1+r_1，这是一个可以被求出来的 x，但他不一定是我们要求的最小非负整数解，所以我们要通过特解进一步处理一般解的问题。这时候如果能够手写几个例子，就再好不过了；但是鉴于时间关系，我们不如直接给出引理：

当存在 x' 满足上述方程，则其通解为 x+k\cdot\text{lcm}(m_1,m_2)，换言之在模 \text{lcm}(m_1,m_2) 的同类剩余系里，存在 x\equiv x'。我们需要确认的是再这样的一个剩余系当中存在唯一解，且这个唯一解是合法解。不妨设不存在唯一解，即存在 \omega_1,\omega_2 同时满足这个方程，且 \omega_1\ge\omega_2，则方程作差得到：

\begin{cases}\Delta\omega\bmod m_1=0\\\Delta\omega\bmod m_2=0\end{cases}

因此我们可以确定 \text{lcm}(m_1,m_2)|(\omega_1-\omega_2)，但是实际上这两者的差 \Delta\omega 一定是小于 \text{lcm}(m_1,m_2) 的，但是却能被其整除，所以我们可以断定有且仅有 \Delta\omega=0 于是存在 \omega_1=\omega_2，那么我们会发现实质上这两个解是等同的，于是在该完全剩余系中存在唯一解。

代码可以实现：

#include<bits/stdc++.h>
#define int __int128
using namespace std;
int Exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }int d=Exgcd(b,a%b,x,y),t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}bool flag;
int a1,a2,n1,n2;
void Trivial(){
    int d=a2-a1;
    int g,x,y;
    g=Exgcd(n1,n2,x,y);
    if(!(d%g)){
        x=((x*d/g)%(n2/g)+(n2/g))%(n2/g);
        a1=x*n1 + a1;
        n1=(n1*n2)/g;
    }else flag=1;
}long long n,as[100001],ns[100001];
int ExCRT(){
    a1=as[0];n1=ns[0];
    for(int i=1;i<n;i++){
        a2=as[i];
        n2=ns[i];
        Trivial();
        if(flag)return -1;
    }return a1;
}signed main() { 
    cin>>n;
    flag=false;
    for(int i=0;i<n;i++)
        cin>>ns[i]>>as[i];
    cout<<(long long)ExCRT()<<endl; 
    return 0;
}