扩展欧几里德算法是什么？

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

下面是一个使用C++的实现：

intexGcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
intr=exGcd(b,a%b,x,y);
intt=x;x=y;y=t-a/b*y;
return r;
}

把这个实现和Gcd的递归实现相比，发现多了下面的x,y赋值过程，这就是扩展欧几里德算法的精髓。

扩展欧几里德定理
　　对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整 　　数对 x，y ，使得 gcd（a，b）=ax+by。
c++语言实现
　　#include 　　using namespace std; 　　int x,y,q; 　　void extend_Eulid(int a,int b) 　　{ 　　if(b == 0) 　　{ 　　x = 1;y = 0;q = a; 　　} 　　else 　　{ 　　extend_Eulid(b,a%b); 　　int temp = x; 　　x = y; 　　y = temp - a/b*y; 　　} 　　} 　　int main() 　　{ 　　int a,b; 　　cin>>a>>b; 　　if(a < b) 　　swap(a,b); 　　extend_Eulid(a,b); 　　printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b); 　　return 0; 　　}