欧几里德定理等

发布于 2017-12-24  733 次阅读


欧几里得算法(Euclid)

欧几里得重要结论:
1:gcd(a,b) = gcd(b,a %b)
2:gcd(a,0) = a

背景:
欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数。
——百度百科

代码

int n_gcd(int a,int b) // 求a,b最大公约数 
{
	if(b == 0)
		return a;
	return n_gcd(b , a%b); // 欧几里德定理gcd(a,b) == gcd(b , a%b) 
}

利用欧几里德算法求2个数的最小公倍数

代码

#include 
#include 
#include 
using namespace std;
int gcd(int a, int b) // 欧几里德算法 
{
	if(b == 0)
		return a;
	return gcd(b, a % b);
}
int main()
{
	int num1, num2, sum, ans, res;
	while(~scanf("%d %d", &num1, &num2))
	{
		sum = num1 * num2;		
		res = gcd(num1, num2);
		ans = sum / res; // 最小公倍数为2个数的积除以2个数的最大公约数 
		cout << ans << endl;	
	}	
} 

拓展欧几里得(Extend- Euclid)

背景:
扩展欧几里德算法是用来在已知a, b求解一组x,y [x,y都是整数],使它们满足贝祖等式: ax+by = gcd(a, b) =d(解一定存在,根据数论中的相关定理)。
扩展欧几里德常用在求解模线性方程及方程组中。
——百度百科

代码

int e_gcd(int a,int b,int &x,int &y) // 扩展欧几里德定理 
{
	int ans,temp;
	if(b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	ans = e_gcd(b,a%b,x,y);
	temp = x;
	x = y;
	y = temp - a/b*y;
	return ans;
} 

乘法逆元

代码

int cal(int a,int m) // 求a对m的乘法逆元 
{
	/*
		a * x = 1 (mod m),x是a关于m的乘法逆元
		等价于:a * x + m * y = 1 
	*/ 
	int x,y,gcd,ans;
	gcd = e_gcd(a,m,x,y);
	if(1 % gcd != 0)
		return -1;
	x *= 1 / gcd;
	m = abs(m);
	ans = x % m;
	if(ans <= 0)
		ans += m;
	return ans;
} 

http://blog.csdn.net/ACMore_Xiong/article/details/47694909
http://blog.csdn.net/zhjchengfeng5/article/details/7786595
http://blog.csdn.net/zhjchengfeng5/article/details/7786595