Euclid算法的扩展

有时候真的感觉时间不够用，村里人事挺多的，时间就这么浪费了。

Euclid算法是求最大公约数的，介绍请点击在这。

Euclid算法的扩展如下

引理 如果d整除a和b，同时存在整数x和y，使得d = ax+by成立，那么一定有d = gcd（a，b）。

证明如下

1. d能整除 a和b，d <= gcd(a,b).
2. d能整除 a和b，d就能整除 ax和by，gcd(a,b) <= d.

so gcd(a,b) == d

递归思想从上往下 

a，b ----->  b, a mod b

从下往上

b*x‘ + (a mod b)*y‘ = d     ----->    a*x + b*y = d

but how can we get x and y? Solution follows

if(b == 0)

 x = 1, y = 0, d = a

test.cpp

#include<iostream>
using namespace std;


class xyd
{
public:
	int x ;
	int y ;
	int d ;
};


// function Euclid 
xyd * Euclid_extra(int a,int b);

// function main 
int main()  
{  
	int a,b,i = 0;  
	xyd * R = new xyd;
	int max;
	while( i<55 )  
	{  
		a = rand()%10;  
		b = rand()%10;  
		if( a<b )
		{
			max = b;
			b = a;
			a = max;
		}
		R = Euclid_extra(a,b) ;
		if( R )
		{
			cout<<"a="<<a<<",b="<<b<<",R->x="<<R->x<<",R->y="<<R->y<<",d="<<R->d<<endl;
			cout<<"a*x + b*y = "<<R->d<<endl;
		}
		i++;  
	}  
	system("pause");  
	return 0;  
}  

// function Euclid 
xyd * Euclid_extra(int a,int b)
{
	if( a <= 0 || b < 0 )
	{
		cout<<"exception of Euclid_extra input"<<endl ;
		return NULL ;
	}
	else
	{
		int max;
		if( a<b )
		{
			max = b;
			b = a;
			a = max;
		}
		xyd * R = new xyd; 
		if(b == 0)
		{
			R -> x = 1;
			R -> y = 0;
			R -> d = a;
			return R;
		}
		else
		{
			R = Euclid_extra(b,a%b);
		}
		xyd * R2 = new xyd;
		R2 -> x = R -> y;
		R2 -> y = (R -> x) -  (  (a/b) * (R->y)  );
		R2 -> d = R->d;
		return R2;
	}
}

算法之旅 Euclid算法的扩展