CINTA作业二：GCD与EGCD

1.给出Bezout定理的完整证明

2.实现GCD算法的迭代版本

#include
using namespace std;
int GCD(int a, int b)
{
 while (a%b)
 {
  int k;
  if (a%b != 0)
  {
   k = b;
   b = a % b;
   a = k;
  }
  else
   return b;
 }
 return b;
}
int main( )
{
 int a, b, p;
 cout << "输入两个整数" << endl;
 cin>>a>>b;
 if ( a==0||b == 0)
  cout << "输入错误" << endl;
 else
  p = GCD(a, b);
 cout << "gcd(a,b)=" << p << endl;
  return 0;
}

#include
using namespace std;
int egcd(int a, int b, int s0, int s1, int r0, int r1, int q)
{
	if (b == 0)
	{
		cout << a << ' ' << r0 << ' ' << s0;
	}
	else
	{
		egcd(b, a % b, r1, r0 - q * r1, s1, s0 - q * s1, a / b);
	}
}
int main()
{
	int a, b, r0, r1, s0, s1, q;
	r0 = 1;
	r1 = 0;
	s0 = 0;
	s1 = 1;
	q = 0;
	cin >> a >> b;
	egcd(a, b, r0, r1, s0, s1, q);
	return 0;
}

#include 
using namespace std;
unsigned int gcd(unsigned int a, unsigned int b)
{
	int m, n;
	if (a == 0) return b;
	if (b == 0) return a;
	for (m = 0; 0 == (a & 1); ++m)
	{
		a >>= 1;
	}
	for (n = 0; 0 == (b & 1); ++n)
	{
		b >>= 1;
	}
	if (n < m)
	{
		m = n;
	}
	while (true)
	{
		if (a < b)
		{
			a = a ^ b;
			b = b ^ a;
			a = a ^ b;
		}
		if (0 == (a -= b))
		{
			return b << m;
		}
		while (0 == (a & 1))
		{
			a >>= 1;
		}
	}
}
unsigned int main()
{
	unsigned int a, b, c = 0;
	cin >> a >> b;
	c = gcd(a, b);
	cout << c << endl;
	return 0;
}