作业CINTA作业二:GCD与EGCD

作业内容:

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

1、定理证明:

证明:
构造集合S = S =S= {a m + b n : m , n ∈ Z 且 a m + b n > = 0 am+bn:m,n∈Z且am+bn>=0am+bn:m,n∈Z且am+bn>=0}。
显然集合SSS非空,根据良序原则,取其中最小值d = a x + b y d=ax+byd=ax+by.
下面证明d dd为a aa和b bb的公因子.
根据除法定理,有a = q d + r , 0 < = r < d a = qd+r,0<=r<da=qd+r,0<=r<d,q ∈ Z q∈Zq∈Z,则有r = a − q d = a − q ( a x + b y ) = ( 1 − q x ) a + ( − q y ) b ∈ S r = a - qd = a - q(ax+by) = (1-qx)a + (-qy)b∈Sr=a−qd=a−q(ax+by)=(1−qx)a+(−qy)b∈S,又因为d dd是S SS中的最小值,所以r = 0 r = 0r=0,则a ∣ d a|da∣d,同理b ∣ d b|db∣d。所以d dd为a aa和b bb的公因子。
下面证明如果存在a aa和b bb的公因子d ′ d′d′,则 d ′ ∣ d d′|dd′∣d。
设d’是a和b的公因子,则有d = a x + b y d=ax+byd=ax+by = d ′ ( a ′ x + b ′ y ) d'(a'x+b'y)d 
 y)。所以d ′ ∣ d d′|dd′∣d。
所以ddd为aaa和bbb的最大公因子,即d = g c d ( a , b ) d = gcd(a,b)d=gcd(a,b)。
所以定理成立

2、GCD算法迭代版本

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

int main()
{
	int a, b, c = 0;
	cin >> a >> b;
	c = gcd(a, b);
	cout << c << endl;
	return 0;
}

3、EGCD算法:

#include<iostream>
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;
}

4、批处理GCD算法:

#include <iostream>
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;
}

上一篇:牛客练习赛89E-牛牛小数点【数论】


下一篇:CF703E Mishka and Divisors 题解