欧几里德算法(辗转相处法)练手

定理:gcd(a,b) = gcd(b,a mod b)
服务器君一共花费了217.313 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 定理:gcd(a,b) = gcd(b,a mod b)。

证明:a可以表示成a = kb + r,则r = a mod b。

假设d是a,b的一个公约数,则有:a % d == 0 , b % d == 0,而r = a - kb,因此 r % d == 0 。因此d是(b,a mod b)的公约数。

假设d 是(b,a mod b)的公约数,则b % d == 0 , r % d == 0 ,但是a = kb +r 所以 a % d == 0。因此d也是(a,b)的公约数。

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。欧几里德算法就是根据这个原理来做的。

/*==================================================*\
| GCD 最大公约数
\*==================================================*/
int gcd(int x, int y)
{
     if (!x || !y) return x > y ? x : y;
     for (int t; t = x % y; x = y, y = t);
    
     return y;
}
/*==================================================*\
| 快速 GCD
\*==================================================*/
int kgcd(int a, int b)
{
	if (a == 0) return b;
	if (b == 0) return a;
	if (!(a & 1) && !(b & 1)) 
		return kgcd(a>>1, b>>1) << 1;
	else if (!(b & 1)) 
		return kgcd(a, b>>1);
	else if (!(a & 1)) 
		return kgcd(a>>1, b);
	else return 
		kgcd(abs(a - b), min(a, b));
}
/*==================================================*\
| 扩展 GCD
| 求x, y使得gcd(a, b) = a * x + b * y;
\*==================================================*/
int extgcd(int a, int b, int & x, int & y)
{
	if (b == 0) 
	{ 
		x=1; y=0; 
		return a; 
	}
	int d = extgcd(b, a % b, x, y);
	
	int t = x; x = y; y = t - a / b * y;
	
	return d;
}

本文地址:http://www.nowamagic.net/librarys/veda/detail/213,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/213

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《Python在Unix和Linux系统管理中的应用》 Noab Gift (作者), Jeremy M.Jones (作者)

《Python在Unix和Linux系统管理中的应用(影印版)》作者们还构建了一个可以免费下载的Ubuntu虚拟机。该虚拟机包含了这《Python在Unix和Linux系统管理中的应用(影印版)》的源代码,还可以用来运行书中的实例,包括SNMP、IPython、SQLAlchemy和许多其他工具。《Python在Unix和Linux系统管理中的应用》展示了Python语言如何提供一种更加高效的方式来处理Unix和Linux服务器管理工作中的各种任务。《Python在Unix和Linux系统管理中的应用(影印版)》的每一章都会提出一个特定的管理问题,例如并发或数据备份,然后通过实际的例子提供基于Python的解决方案。

更多计算机宝库...