扩展中国剩余定理（EXCRT）

简述

如果给定

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

CPP

#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}}

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

文章操作

扩展中国剩余定理（EXCRT）

简述

做法

Code

相关推荐

评论

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