---
# System prepended metadata

title: CINTA作业二 GCD与EGCD

---

# 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算法的迭代版本
```c++
#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算法

```c++
#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算法
```c++
#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;

}
```