扩展欧几里得，exgcd（入门）
gcd(a,b)=gcd(b,a%b)
gcd(a,b)中要求a，b是非负数
//xa+yb=gcd
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1; y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
} ax+by=d通过exgcd求出了x0，y0（ax+by=gcd的解）后求出x和y的通解： x=（x0-b/gcd）*k
y=（y0+a/gcd）*k
另类的方法（不常用，不实用）
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1; y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int tmp=y;
y=x-a/b*y;
x=tmp;
return d;
} 
哔哩哔哩公司氛围 502人发布