『笔记』扩展欧几里得（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
#include
#include
#include
#include
#include
#include
#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<