数学专题B2—裴蜀定理

2025年9月6日 ooliver OI

数学专题B2—裴蜀定理

P4549 裴蜀定理

裴蜀定理

$a x + b y = gcd (x, y)$

题目思路

显然由前置知识可知：对于当前的 $a n s$ 和 $A_{i}$ ， $a n s = gcd (a n s, | A_{i} |)$ 所以代码如下：

#include
using namespace std;
#define int long long
signed main(){
	int n,x,ans;
	cin>>n>>ans;
	for(int i=2;i>x;
		ans=abs(__gcd(ans,abs(x)));
	}
	cout

`#include
using namespace std;
#define int long long
signed main(){
	int n,x,ans;
	cin>>n>>ans;
	for(int i=2;i
		cin>>x;
		ans=abs(__gcd(ans,abs(x)));
	}
	cout
	return 0;
}`

P1082 同余方程

扩展欧几里得

扩展欧几里得是用来解决 $a x + b y = gcd (x, y)$ 的一组解的。设一组解为 $x_{1}, y_{1}$ ，一组解为 $x_{2}, y_{2}$ 根据欧几里得算法（辗转相除法）可知： $a x_{1} + b y_{1} = b x_{2} + (a mod b) y_{2}$ ，所以就有： $\begin{array}{l} a x_{1} + b y_{1} & a m p; = b x_{2} + (a mod b) y_{2} \\ a x_{1} + b y_{1} & a m p; = b x_{2} + (a - b \cdot ⌊ \frac{a}{b} ⌋) y_{2} \\ a x_{1} + b y_{1} & a m p; = a y_{2} + b (x_{2} - ⌊ \frac{a}{b} ⌋ y_{2}) \end{array}$ 解得： $\begin{cases} x_1=y_2 \\ y_1=x_2-\lfloor\frac{a}{b} \rfloor y_2 \end{cases}$ 根据这个递归即可。代码：

void exgcd(int a,int b){
	if(b==0){
		/*
		通过欧几里得算法（辗转相除法），
		最终b一定会变为0，
		这个时候gcd(a,b)=a，
		所以直接令x=1即可，y可以取任意值 
		*/
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);//传递当前方程 
	int lx=x;
	x=y,y=lx-a/b*y;
}

`void exgcd(int a,int b){
	if(b==0){
		/*
		通过欧几里得算法（辗转相除法），
		最终b一定会变为0，
		这个时候gcd(a,b)=a，
		所以直接令x=1即可，y可以取任意值 
		*/
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);//传递当前方程 
	int lx=x;
	x=y,y=lx-a/b*y;
}`

题目思路

题目可以转化为求 $a x + b y = 1$ 的最小正整数解，又因为其保证了有解，所以我们可以知道 $gcd (a, b) = 1$ 。所以直接扩欧。代码：

#include
using namespace std;
int A,B,x,y;
void exgcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	int lx=x;
	x=y,y=lx-a/b*y;
}
int main(){
	cin>>A>>B;
	exgcd(A,B);
	x=(x%B+B)%B;//最小正整数解 
	cout

`#include
using namespace std;
int A,B,x,y;
void exgcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	int lx=x;
	x=y,y=lx-a/b*y;
}
int main(){
	cin>>A>>B;
	exgcd(A,B);
	x=(x%B+B)%B;//最小正整数解 
	cout
	return 0;
}`

P1516 青蛙的约会

题目可以简化为求出一个最小的 $k$ 使得： $x + m k \equiv y + n k (mod L)$ 开始吟唱： $\begin{array}{l} x + m k & a m p; \equiv y + n k (mod L) \\ ∴ x + m k - y - n k & a m p; = z L (z \in N^{*}) \\ x - y + k (m - n) & a m p; = z L \\ z L + k (n - m) & a m p; = x - y \end{array}$ 令 $x_{0} = n - m, y_{0} = L, c = x - y, g = gcd (M, L)$ ，则有 $k x_{0} + z y_{0} = c$ ，此时就可以用扩欧求出 $k x_{0} + z y_{0} = g$ 的一组解。设该解为 $x_{1}, y_{1}$ ，则继续吟唱： $\begin{array}{l} k x_{1} + z y_{1} & a m p; = g \\ k \frac{x_{1} c}{g} + z \frac{y_{1} c}{g} & a m p; = c \\ ∵ k (\frac{x_{1} c}{g} + d z) + z (\frac{y_{1} c}{g} - d k) & a m p; = c \\ ∴ x_{0} & a m p; = \frac{x_{1} c}{g} + d z \\ x 0 ↓ & a m p; ⟹ d ↓ \\ ∵ d b, d a & a m p; \in N^{*}, \\ ∴ d_{min} & a m p; = \frac{1}{g} . \\ ∴ x_{0 min} & a m p; = (\frac{x_{1} c}{g} mod \frac{b}{g} + \frac{b}{g}) mod \frac{b}{g} \end{array}$ 所以得到代码：

#include
using namespace std;
#define int long long
int xx,yy,x,y,m,n,l,g,a1,b1,c1;
int exgcd(int a,int b){
	if(b==0){
		xx=1,yy=0;
		return a;
	}
	int rtn=exgcd(b,a%b),lx=xx;
	xx=yy,yy=lx-a/b*yy;
	return rtn;
}
signed main(){
	cin>>x>>y>>m>>n>>l;
	a1=n-m,b1=l,c1=x-y;
	if(a1

`#include
using namespace std;
#define int long long
int xx,yy,x,y,m,n,l,g,a1,b1,c1;
int exgcd(int a,int b){
	if(b==0){
		xx=1,yy=0;
		return a;
	}
	int rtn=exgcd(b,a%b),lx=xx;
	xx=yy,yy=lx-a/b*yy;
	return rtn;
}
signed main(){
	cin>>x>>y>>m>>n>>l;
	a1=n-m,b1=l,c1=x-y;
	if(a10) a1=-a1,c1=-c1;
	g=exgcd(a1,b1);
	if(c1%g) cout"Impossible";
	else cout
	return 0;
}`