关于欧几里得算法和拓展欧几里得算法程序

关于欧几里得算法和拓展欧几里得算法
求解两个数的最大公约数，有三种比较常用的算法：蛮力法、更相减损法以及欧几里得算法。在这里我们只讨论欧几里得算法，蛮力法的时间复杂度过大，不适合求解数据量比较大情况。而更相减损法与欧几里得算法其实有共通性。
首先，欧几里得算法，可以用一个函数gcd()表示，我们假设现在有两个数a和b。
1、gcd(a,b)= gcd(b,a)
2、gcd(a,b)=gcd(b,a%b)
3、gcd(a,0)=a
通过以上三个公式,我们就可以求解两个数的最大公约数了。
这里给一个例子：假设我们要求104，195的最大公约数
gcd(104,195)=gcd(195,104)=gcd(104,91)=gcd(91,13)=gcd(13,0)=13
根据上面的例子，可以看出欧几里得算法比蛮力法快
下面，我将给出该算法的几个代码版本。
递归：

int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); }

以上为尾递归，我们可以将其改为非递归版本：

int gcd(int a,int b) { int tmp; while(b!=0) { tmp=a; a=b; b=tmp%b; } return a; }

另外，拓展欧几里得算法不仅可以计算出两个数的最大公约数，还能给出
ax+by=gcd(a,b)的一个x，y的解（x，y不止一组解）
我们已经知道了欧几里得算法的一些公式，通过这些公式我们便可以很方便的推导出拓展欧几里得算法。
1、ax+by=gcd(a,b)=gcd(b,a%b)
2、 gcd(b,a%b)=bx+(a%b)y
3、gcd(a,0)=ax+0y=a 得x=1，y=0
(注：以上三个式子中，x，y相互无关)
通过上面的式子，我们可以知道
前一组x，y的解与后一组x，y的解有关。
我们设 ax+by=gcd(a,b)、gcd(b,a%b)=bx’+(a%b)y’
已知a%b=a-[a/b]*b（[a/b]表示a/b后截掉小数部分）
gcd(b,a%b)=bx’+(a-[a/b]*b)y’=ay’+b(x’-[a/b]*y’)
再根据我们设的式子，不难看出
ax+by= ay’+b(x’-[a/b]*y’)
所以，后一个的解可以推出前一个的解，可得
x=y’
y=x’-[a/b]*y’
这样，我们可以很方便得写出递归版本的程序

int exgcd(int a,int b,int *x,int *y) { if(b==0) { *x=1; *y=0; return a; } else { int d,t; d=exgcd(b,a%b,x,y); t=*x; *x=*y; *y=t-(a/b)*(*y); return d; } }

【关于欧几里得算法和拓展欧几里得算法】此程序可以用非递归版本实现，可以通过栈来保存每次递归中a和b的值来实现。