# CINTA作业二 GCD与EGCD
>1、给出Bezout定理的完整证明。
>2、实现GCD算法的迭代版本。
>3、实现EGCD算法。输入：a、b两个整数，输出：r、s、d三个整数，满足ar+bs=d
>4、实现一种批处理版本的GCD算法，即，给定一个整数数组，输出其中所有整数的最大公因子。输入：一个整数数组a；输出：一个整数d，是a数组中所有整数的最大公因子。

## 1.Bezout:
Let a and b be nonzero integers.
Then there exist integers r and s such that
gcd(a, b) = ar + bs
Furthermore, the greatest common divisor of a and b is unique

证明：
>* 构造集合 S = {am + bn : m, n ∈ Z 且am + bn ≥ 0}.
> 取S集合中最小值d=ar+bs
>* 首先证明d是a,b的公因子
> 设a=dq+p,则 p=a-dq,将d=ar+bs代入该式
> 得p=a-q(ar+bs)=a(1-qr)+b(-sq)
> r,s,q,p ∈ Z
> 则p也在S集合内
> 由于-qr<r,-sq<s,则p=0
> 所以a=dq 同理可证b=dq'
> d 是 a和b的公因子
> * 证明如果存在a 和b 的公因子d′，则d′ | d
> 如果存在a 和b 的公因子d′
> 则a=d'q, b=d'q'
> 又d=ar+bs
> d=d'qr+d'q's=d'(qr+q's)
> q,p,r,s∈ Z
> 所以d'|d
>* 综上所述：d=gcd(a,b)

## 实现GCD算法的迭代版本

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
	int i;
	while (b)
	{
		i = a % b;
		a = b;
		b = i;
	}
	return a;
}
int main()
{
	int a = 9, b = 3;
	cout << gcd(a, b);
	return 0;
}

## EGCD算法

#include <iostream>
using namespace std;
void egcd(int a, int b,int *p)
{
	int r0 = 1,r1 = 0, s0 = 0, s1 = 1;
	while (b != 0)
	{
		int q = a / b;
		int r = r0, s = s0;
		a = b;
		b = a % b;
		r0 = r1;
		r1 = r - q * r1;
		s0 = s1;
		s1 = s - q * s1;
	}
	
	p[0]= a;
	p[1] = r0;
	p[2] = s0;
	
	
}
int main()
{
	int a, b;
	cin >> a >> b;
	int m[3] = { 0,0,0 };
	egcd(a, b, m);//数组名就表示指向数组的指针
	cout << m[0] << " " << m[1] << " " << m[2];
	return 0;
}

## 批处理版本的GCD算法

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
	int i;
	while (b)
	{
		i = a % b; 
		a = b;
		b = i;
	}
	return a;
}

int pgcd(int* p, int size)
{
	int g = 0;
	for (int i = 0; i < size; i++)
	{
		if (i == 0)
		{
			g = gcd(p[0], p[1]);
		}
		else
			g = gcd(g, p[i]);
	}
	return g;
}
int main()
{
	
	int size;
	cout << "请输入数组长度：";
	cin >> size;
	int* m = new int[size];
	for (int j = 0; j < size; j++)
	{
		cin >> m[j];
	}
	cout<<pgcd(m, size);
	delete m;
	return 0;

}