定义
扩展欧几里得算法是用来在已知一组 ((a,b)) 的时，求解一组 ((x,y)) 使得
思想 and 板子
根据相关的知识可以得到
由当 (b=0) 是即可得出 (x=1,y=0)
即可递推求解
如何来做？
进而可以得出结论
有了结论就可以实现简单的求解
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) 可以进行解决一些问题
应用
可用于进行对二元一次不定方程的求解
即
根据裴蜀定理可得，这个方程有整数解的充要条件为
同样，该方程可以等同于
P5656 板子可以为较为拓展的应用
1、如何来求 (ax+by=c) 的一个解
首先我们在有整数解的情况下求出
的解 ((x_0,y_0))
由(k=frac{c}{gcd(a,b)})
得出来
该方程的一个解可以为
(egin{cases} x=kx_0\y=ky_0 end{cases})
也就是方程在同除完 (k) 后求出解来，进而乘上 (k) 得出当前的解，因为(a,b)是不变的
2、如何根据一组解求出多组解来
首先任意选择一个数(t)，为了方便叙述和计算，一般设(t=1)
设两个整数 (m,n)
我们可以得出
由
可知
那么就是寻找一组 ((m,n))使得该方程 成立即可
可以得到
(egin{cases} m=frac{b}{gcd(a,b)}\n=-frac{a}{gcd(a,b)} end{cases})
代进去等式成立，进而就可以得到一组解
(egin{cases} x_i=x+m\y_i=y+n end{cases})
3、考虑正整数解的最大值最小值，及其正整数解的个数
首先设置一下变量
(egin{cases} d=gcd(a,b)\tx=frac{b}{d} \ty=frac{a}{d} end{cases})
首先那我们从x的最小值开始找起
可以得到式子
得到(x_{min}=x+lceilfrac{1-x}{tx} ceil imes tx)
那么此时同样可以得到 (y_{max}=y-lceilfrac{1-x}{tx} ceil imes ty)
- 如果此时没有(y_{max})不是正整数的话
那么就在求一下
那么 (y) 的最小正整数解即为 (y_{max}+lceilfrac{1-y_{max}}{ty} ceil imes ty)
同样适用于有正整数解情况下的(y_{min})
- 如果此时有正整数解
可以很显然的发现(y_{min}=y_{max}mod ty)
利用情况一中的结论可以求出
至于解的个数可以参考在(y_{max} o y_{min})过程中 $ k $的变化
正整数解的组数即为 (lfloorfrac{y_{max}-1}{ty} floor+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
",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
",y);//max
}
continue;
}
return 0;
}