题解：P4777 【模板】扩展中国剩余定理（EXCRT）

MoCaRabbit · 2025-07-29 16:06:04 · 题解

这个文章大部分是差不多去年这个时候写的，今天略做修改，上交题解。

CRT 是构造，exCRT 是合并模拟合并同余方程组的过程。

我们先看两个方程的情况。

转换一下成以下式子。

现在要使它变为 kx+b=a 的形式。

那相当于 x=k_1p+a=k_2q+b。

于是 k_1p+a=k_2q+b。

移项得 k_1p-k_2q=b-a。

首先 p,q 已知，b,a 已知。

那么就解一个不定方程呗！

先使 p,q 互质。

变为 k_1p'-k_2q'=\frac{b-a}{d}。

现在只有 d|b-a 时有解。

用 exGCD 干就完了。

exGCD 只能求出方程的一组解。

学过一点小奥的就知道，求出一组解 k_1',k_2'。

通解就是以下式子（证明显然）。

那么 x=k_1p+a=a+\frac{b-a}{d}k_1'p。

接着，最小解 x' 出现了。

那这有什么用呢？

当然。

感性理解一下，所有通解 x \equiv x' \pmod {\operatorname{lcm}(p,q)}

于是，两个方程被合并了。

搞成 x \equiv a+\frac{b-a}{d}k_1'p \pmod {\operatorname{lcm}(p,q)}。

都是定值。

于是，n 个方程就被合并为了一个方程 x \equiv l \pmod m。

然后 l \bmod m 最小。

完结撒花。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int __int128
int exgcd(int a,int b,int &x,int &y){
    int d=0;
    if(b==0){
        x=1,y=0;
        return a;
    }
    else{
        d=exgcd(b,a%b,x,y);
        int p=x;
        x=y,y=p-a/b*y;
    }
    return d;
}
long long n;
int ans,mod; 
signed main() {
    scanf("%lld",&n);
    scanf("%lld%lld",&mod,&ans);
    for(int i=2;i<=n;i++){
        long long a,b;
        scanf("%lld%lld",&a,&b);
        int c,d;
        int p=exgcd(mod,a,c,d);
        if((b-ans)%p){
            cout<<-1;
            return 0;
        }
        int lcm=a/p*mod;
        int k=c*(b-ans)/p%(a/p);
        if(k<0) k+=a/p;
        ans=(mod*k+ans)%lcm,mod=lcm;
    }
    printf("%lld",(long long)(ans%mod));
    return 0;
}

正确性在算法讲解里面讲清楚了的。