『笔记』扩展欧几里得（exgcd）

定义

扩展欧几里得算法是用来在已知一组 $(a,b)$ 的时，求解一组 $(x,y)$ 使得

\[ax+by=gcd(a,b) \]

思想 and 板子

根据相关的知识可以得到

\[gcd(a,b)=gcd(b,a \bmod \ b) \]

由当 $b=0$ 是即可得出 $x=1,y=0$

即可递推求解

如何来做？

\[ax+by=gcd(a,b)=gcd(b,a \bmod b) \]

\[bx+(a \bmod\ b)y=gcd(b,a \bmod b) \]

\[bx+(a-\lfloor\frac{a}{b}\rfloor\times b)\times y=gcd(b,a\bmod b) \]

\[bx+ay-\lfloor\frac{a}{b}\rfloor\times by=gcd(b,a\bmod b) \]

\[ay+b(x-\lfloor\frac{a}{b}\rfloor\times y)=gcd(b,a\bmod b) \]

进而可以得出结论

\[ax+by \]

\[\to ay+b(x-\lfloor\frac{a}{b}\rfloor\times y) \]

有了结论就可以实现简单的求解

int exgcd(int a,int b)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int gcd=exgcd(b,a%b);
	int tmp=x;
	x=y;
	y=tmp-a/b*y;
	return gcd;
}

为什么要用？

在当前我的理解范围内，它既可以求出最大公约数，并且求出来的 $x,y$ 可以进行解决一些问题

应用

可用于进行对二元一次不定方程的求解

即

\[ax+by=c \]

根据裴蜀定理可得，这个方程有整数解的充要条件为

\[c \ \bmod\ gcd(a,b)=0 \]

同样，该方程可以等同于

\[ax \equiv c\ (\bmod b) \]

P5656 板子可以为较为拓展的应用

1、如何来求 $ax+by=c$ 的一个解

首先我们在有整数解的情况下求出

\[ax+by=gcd(a,b) \]

的解 $(x_0,y_0)$

由$k=\frac{c}{gcd(a,b)}$

得出来

该方程的一个解可以为

$\begin{cases} x=kx_0\\y=ky_0 \end{cases}$

也就是方程在同除完 $k$ 后求出解来，进而乘上 $k$ 得出当前的解，~~因为$a,b$是不变的~~

2、如何根据一组解求出多组解来

首先任意选择一个数$t$，为了方便叙述和计算，一般设$t=1$

设两个整数 $m,n$

我们可以得出

\[a(x+m)+b(y+n)=c \]

\[ax+am+by+bn=c \]

由

\[ax+by=c \]

可知

\[am+bn=0 \]

那么就是寻找一组 $(m,n)$使得该方程成立即可

可以得到

$\begin{cases} m=\frac{b}{gcd(a,b)}\\n=-\frac{a}{gcd(a,b)} \end{cases}$

代进去等式成立，进而就可以得到一组解

$\begin{cases} x_i=x+m\\y_i=y+n \end{cases}$

3、考虑正整数解的最大值最小值，及其正整数解的个数

首先设置一下变量

$\begin{cases} d=gcd(a,b)\\tx=\frac{b}{d} \\ty=\frac{a}{d} \end{cases}$

首先那我们从x的最小值开始找起

可以得到式子

\[x+k\times tx\ge 1 \]

\[k\ge \lceil\frac{1-x}{tx}\rceil \]

得到$x_{min}=x+\lceil\frac{1-x}{tx}\rceil\times tx$

那么此时同样可以得到 $y_{max}=y-\lceil\frac{1-x}{tx}\rceil\times ty$

如果此时没有$y_{max}$不是正整数的话

那么就在求一下

\[y_{max}+k\times ty\ge1 \]

\[k\ge \lceil\frac{1-y_{max}}{ty}\rceil \]

那么 $y$ 的最小正整数解即为 $y_{max}+\lceil\frac{1-y_{max}}{ty}\rceil\times ty$

同样适用于有正整数解情况下的$y_{min}$

如果此时有正整数解

可以很显然的发现$y_{min}=y_{max}\bmod ty$

利用情况一中的结论可以求出

\[x_{max}=x_{min}-\lceil\frac{1-y_{max}}{ty}\rceil\times tx \]

至于解的个数可以参考在$y_{max}\to y_{min}$过程中 $ k $的变化

正整数解的组数即为 $\lfloor\frac{y_{max}-1}{ty}\rfloor+1$

代码请参考P5656

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#define int long long
using namespace std;
int x,y;//用于求解 
int read()//不到卡常不用快读=_= 
{
	char c=getchar();
	int f=1;
	int x=0;
	while(c<'0'||c>'9')
	{
		if(c=='-')
			f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
int exgcd(int a,int b)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int ans=exgcd(b,a%b);
	int tmp=x;
	x=y;
	y=tmp-a/b*y;
	return ans;
}
signed main()
{
	int t;
	t=read();
	while(t--)
	{
		int a,b,c;
		a=read();
		b=read();
		c=read();
		int d=exgcd(a,b);
		if(c%d!=0)//根据裴蜀定理得出，c不是gcd(a,b)的倍数，则一定无整数解 
		{
			cout<<-1<<endl;
			continue;
		}
		x=x*c/d;
		y=y*c/d;//求出一组正整数解
		int tx=b/d;
		int ty=a/d;
		int k=ceil((1.0-x)/tx);//求出x_min正整数;判\断y是否为正整数 
		x+=k*tx;//x_min
		y-=k*ty;//求出此时的ymax 
		if(y<=0)
		{
			int ymin=y+ty*ceil((1.0-y)/ty)*1ll;
			printf("%lld %lld\n",x,ymin); 
		}
		else 
		{
			printf("%lld ",(y-1)/ty+1);//个数 
			printf("%lld ",x);//最小值 
			printf("%lld ",(y-1)%ty+1);//最小值 
			printf("%lld ",x+((y-1)/ty*tx));//max 
			printf("%lld \n",y);//max
		}
		continue;
	} 
	return 0;
}

『笔记』扩展欧几里得（exgcd）

定义

思想 and 板子

应用

推荐阅读