扩展的欧几里德算法

关于的扩展的欧几里德算法:

扩展欧几里德定理
对于与不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么存在整数 x，y 使得 gcd（a，b）=ax+by。

现在我们要求求出这个x和y，以及最大公约数，怎么办？下面给你解答！

关于代码的实现：

总体来说，有两种方式，以下一一概述：

1.递推法：

具体代码实现如下：

#include<iostream>
#include<cstdio>
using namespace std;

int extended_euclidean(int n,int m,int &x,int &y)//扩展的欧几里德算法的另一种形式
{
	int x1=1, x2=0, x3=n;
	int y1=0, y2=1, y3=m;
	while(x3%y3!=0)
	{
		int d=x3/y3;
		int t1,t2,t3;
		t1=x1-d*y1;
		t2=x2-d*y2;
		t3=x3-d*y3;
		x1=y1; x2=y2; x3=y3;
		y1=t1; y2=t2; y3=t3;
	}
	x=y1; y=y2;
	return y3;
}
//关于递推式的推法以前听老师讲过，不过忘了，现在就只有结论了

int main()
{
	int g,x,y;
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		g=extended_euclidean(n,m,x,y);
		printf("%d和%d的最大公约数是：%d\n",n,m,g);
		printf("%d=%d*%d+%d*%d\n",g,x,n,y,m);
	}
	return 0;
}

递推法的关键在于递推公式:

这个公式以前我们老师推导过，不过，现在我已经忘了，无妨，大家拿过来用就可以了！

上面的算法依靠的也是这个递推式！

2.递归法：

代码如下：

//扩展的欧几里德算法的递归形式,可以推广至全部整数范围
//回代形式

#include<iostream>
using namespace std;

int extended_euclidean(int n,int m,int &x,int &y)
{
	if(m==0) { x=1;y=0;return n; }
	int g=extended_euclidean(m,n%m,x,y);
	int t=x-n/m*y;
	x=y;
	y=t;
	return g;
}
int main()
{
	int g,x,y;
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		g=extended_euclidean(n,m,x,y);
		printf("%d和%d的最大公约数是：%d\n",n,m,g);
		printf("%d=%d*%d+%d*%d\n",g,x,n,y,m);
	}
}

求解 x ，y 的方法的理解
我们不妨设 n>m。
1，显然当 m=0，gcd（n，m）=n。此时 x=1，y=0；
2，nm<>0 时
设 nx1 +my1
=gcd(n,m);
mx2 +(n%m)y2
=gcd(m,n%m);
根据朴素欧几里德原理有 gcd(n,m)=gcd(m,n%m);
则:nx1 +my1 =mx2 +(n%m)y2
;
即:nx1 +my1 =mx2 +(n-(n/m)*m)y2 =ny2 +mx2-(n/m)*my2
;
根据恒等定理得：x1 =y2 ; y1 =x2-(n/m)*y2
;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是递归定义了，因为 gcd 不断的递归求解一定会有个时候 m=0，所以递归可以
结束。