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

· · 题解

扩展中国剩余定理（EXCRT）

​ 题目：​P4777 - 洛谷​

简述

如果给定 n 个同余方程组

\begin{cases} x \equiv b_1 \pmod {a_1} \\ x \equiv b_2 \pmod {a_2} \\ x \equiv b_3 \pmod {a_3} \\ \cdots \\ x \equiv b_n \pmod {a_n} \\ \end{cases}

保证 a 是正整数，b 是非负整数

现在要求找一个非负整数 x，使得 x 最小且满足这 n 同余方程

数据保证 x 不超过 10^{18}

做法

可以考虑将同余方程合并

对于一个合并完后的方程以及一个需要合并的方程：

\begin{cases} x \equiv B \pmod {A} \\ x \equiv b \pmod {a} \\ \end{cases}

可以推出：

x+A\times X=B \ (X\in \mathbb{Z})\\ x+a\times Y=b \ (Y\in \mathbb{Z})

即：

B-A\times X=b-a\times Y

整理得：

A\times X - a\times Y=B-b

我们就可以用 exgcd 求出 A\times X - a\times Y=\gcd(A,a) 其中一个解。再同时乘 (B-b) \ \div \ \gcd(A,a)，可以得到一个解 x_0,y_0。

我们可以从其得到其通解为：

X=x_0+\frac{a}{\gcd(A,a)}\times k\\ Y=y_0-\frac{A}{\gcd(A,a)}\times k

由前面我们可知 x=B-A\times X，将 X 的通解带入，可以得到：

x=B-A\times (x_0+\frac{a}{\gcd(A,a)}\times k)\\ \ =B-A\times x_0 \ -\ \frac{A\times a}{\gcd(A,a)}\times k\\ =B-A\times x_0 \ - \operatorname{lcm}(A,a)\times k

我们可以得到一个同余方程：

x \equiv B-A\times x_0 \pmod {\operatorname{lcm}(A,a)}

对于多个方程只需将其两两合并即可。 以上就是所有思路过程了。

Code

#include<bits/stdc++.h>
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
#define mod 998244353
#define ll __int128
#define lll long long
#define db double
#define pb push_back
#define MS(x,y) memset(x,y,sizeof x)
using namespace std;
const int N=1e5+5,M=1e5+5;
const ll INF=1ll<<60;
int n;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    else{
        ll aa=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return aa;
    }
}
ll A,B,x,y;
int main(){
    lll a,b;
    IOS;cin>>n;
    A=1;B=0;//因为 x mod 1 一定等于零
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        ll gd=exgcd(A,a,x,y);
        x=(B-b)/gd*x;
        B=B-A*x;
        A=a/gd*A;
        B=(B%A+A)%A;
    }
    lll ans=(B%A+A)%A;
    cout<<ans<<"\n";
    return 0;
}
\LARGE{\mathbb{END}}