// 扩展欧几里得模板
// 扩展欧几里得算法，是在求出 a 和 b 的最大公因数 gcd 的同时 ，求出
// 线性方程 ax + by == g的一个实数解
// 这也是 ，扩展欧几里得 算法的应用之一。
#include
int ex_gcd( int a, int b,int& x ,int& y){
if( b == 0){
x = 1;
y = 0;
return a;
}int r = ex_gcd( b,a%b ,x,y);
int t = x;
x = y;
y = t - a/b * y;
return r;
}
int main(void){ int a,b,r,x,y;
scanf("%d%d",&a,&b);
r = ex_gcd(a,b,x,y);
printf("%d * %d + %d * %d = %d",a,x,b,y,r);
return 0;
}
【扩展欧几里得算法学习参考模板】
