扩展欧几里得算法
求解二元一次方程$ax+by=gcd(a,b) $的一组解
理论:裴蜀定理
对于任意整数\(a,b\), 存在一对整数\(x,y\),满足\(ax+by=gcd(a,b)\)
核心代码
int exgcd(int a,int b,int &x,int &y) {
if(b==0){
x=1;y=0;
return a;
}
else{
int d=exgcd(b,a%b,x,y);
int temp=x;
x=y;
y=temp-(a/b)*y;
return d;
}
}