回顾
由贝祖定理可知：ax+by=gcd(a,b)
(a,y)为一组解
（x+kb,y-ka）也为解
所以有无数组解
一、扩展欧几里得算法
x，y为整数，ax+by=gcd(a,b),求解一组x,y使得上式成立。
二、算法推导
1.由欧几里得（辗转相除法）可知：
2.递归边界为：b==0时，x=1,y=0
推导：由欧几里得（辗转相除法）可知：
gcd(a,b)=gcd(b,a%b)
的边界条件时 r=0时
即gcd(a,0)=a
a*x1+0*y1=a
我们可以构造一组x1,y1
x1=1,y1可以为任意数
不妨 x1=1,y1=0
那么 x1=1,y1=0就是一组解。
（由此依次往回返，令x=y1,y=x1-a/b*y1,就可以得到ax+by=gcd(a,b)的一组解（x,y）.）
3.如果ax+by=c,c为gcd(a,b),c=p*gcd(a,b),我们如何找到整数解（x,y）使得ax+by=c成立呢？
推导：假设ax1+by1=gcd(a,b) 式子1
由上可知：（x1,y1）的求解方法已知
始终可以找到（x1,y1）
让式子1两边乘p:apx1+bpy1=p*gcd(a,b)=c
所以：x=px1,y=py1(这样就找到了一组解）
其实求ax+by=c的解（x,y）
令p=c/gcd(a,b)
就是求：a/p*x+b/p*y=gcd(a,b)的整数解
三、求解步骤
1.求gcd(a,b)求解（x1,y1），ax1+by1=gcd（a,b）
2.求q=c/gcd(a,b)
3.x=qx1,y=qy1
(由贝祖定理可知，也可以推出无数组解）
四、算法实现
1.代码一：
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{ int ret,tmp;
if(b==0)
{
x=1;y=0;return a;}
ret=exgcd(b,a%b,x,y);
tmp=x;x=y;y=tmp-a/b*y;
return ret;
}
int main()
{
int a,b,x,y,z;
scanf("%d%d",&a,&b);
z=exgcd(a,b,x,y);
printf("%d %d %d\n",z,x,y);
return 0;
}
思考：此时求出的整数解（x,y）并不能保证x为最小整数，若要保证x为最小整数怎么办？
综上可知，只要让：x=(x%b+b)%b，y=(z-a*x)/b
利用ax+by=1(ret=gcd(a,b))
y=(ret-ax)/b
2.代码二：
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{ int ret,tmp;
if(b==0)
{
x=1;y=0;return a;}
ret=exgcd(b,a%b,x,y);
tmp=x;x=y;y=tmp-a/b*y;
return ret;
}
int main()
{
int a,b,x,y,z;
scanf("%d%d",&a,&b);
z=exgcd(a,b,x,y);
x=(x%b+b)%b；
y=(z-a*x)/b；
printf("%d %d %d\n",z,x,y);
return 0;
}
标签：gcd,int,欧几里得,扩展,exgcd,ret,y1,x1 From： https://www.cnblogs.com/ddfy198811/p/17025511.html