CINTA作业二：GCD与EGCD

提示：学习欧几里得算法及其拓展

• CINTA作业二：GCD与EGCD
• 前言
• 一、Bezout定理的证明
• 二、实现GCD算法
• •  1.递归版
  •  2.实现
• 三、实现EGCD算法
• 四、实现一种批处理版本的GCD算法

本章以除法算法为基础，定义整除性、公因子、最大公因子等概念
学会通过欧几里得算法及其拓展快速求出最大公因子

存在性：
 构造集合 S = { am + bn; m, n ∈ in ∈ Z 且 am + bn > 0 }
 显然，S是一个非空集合。
  根据良序原理，集合S中必然存在一个最小值 d = ar + bs
 我们称 d = gcd(a,b)
 写 a = dq + r ’ （0 ≤ leq ≤r '< d）
 当 r ’ > 0 时，
    r ’ = a - dq
      = a - (ar + bs)q
      = a - arq -bsq
      = a(1 - rq) + b(-sq)
 则有 r ’ ∈ in ∈ S，但这与 d 是 S 的最小成员这一事实相矛盾
 因此，r ’ = 0 ⇒ Rightarrow ⇒ d 整除 a
 同理可证，d 整除 b
 综上所述，d 是 a 和 b 的公因子

唯一性：
 假设存在另一个整数 d’ 是 a 和 b 的公因子
 则有 a = d’h， 和 b = d’k;
 所以 d = ar + bs = d’hr + d’ks = d’(hr + ks)
 所以 d’ 整除 d
 d 是 a 和 b 唯一的最大公因子

代码如下（示例）：

                摘自王立斌老师《具体数论与代数》

代码如下：

#include
using namespace std;
int gcd(int a, int b);
void main()
{
	int a,b;
	cout<<"输入两个整数a和b"<<'n';
	cin>>a>>b;
	cout<<'n';
	cout<<"a和b的最大公因子为;"< 
   
三、实现EGCD算法 
代码如下：
 
#include
using namespace std;
int *egcd(int a, int b);
void main()
{
	int a,b;
	cout<<"输入两个整数a和b"<<'n';
	cin>>a>>b;
	cout<<'n';
	int *num;
	num=egcd(a,b);
	cout<<"a("< 
   
四、实现一种批处理版本的GCD算法 
要求如下：
 
 
 
给定一个整数数组，输出其中所有整数的最大公因子。
 输入：一个整数数组a；
 输出：一个整数d，是a数组中所有整数的最大公因子。
 
 
代码如下：
 
#include
using namespace std;
int processing_gcd(int *b);
int gcd(int a,int b);
void main()
{
	int *a = new int[1000];  //定义一个动态数组a
	int x=1;
	int i=-1;
	cout<<"输入一个整数数组a(输入0停止)"<<'n';
	while(x)
	{
		i++;
		cin>>x;
		a[i]=x;
	}
	//int d = processing_gcd(p);
	cout<<"该数组的最大公因子是:"< 
 
C/C++语言自定义函数如何返回数组？