stickyman/
共15个网摘 [
1 ] |
访问stickyman的个人空间
stickyman收录，使用标签：C++, Java, 最大公约数, 欧几里德, 算法, 辗转相除法，时间：2008-1-29 0:31:34 | 相关网摘，我也收藏
欧几里德算法描述：
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb r，则r = a mod b
假设d是a,b的一个公约数，则有d|a, d|b，而r = a - kb，因此d|r ,因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则d | b , d |r ，但是a = kb r ,因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证
http://blog.minidx.com/2008/01/29/450.html
共15个网摘 [
1 ]