好贷网好贷款

欧几里得算法以及扩展算法

发布时间:2016-12-3 3:58:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"欧几里得算法以及扩展算法",主要涉及到欧几里得算法以及扩展算法方面的内容,对于欧几里得算法以及扩展算法感兴趣的同学可以参考一下。

一、简介   欧几里得算法又称“辗转相除法”,它首次出现于欧几里得的《几何原本》(第VII卷,命题yⅠ和Ⅱ)中,而在中国则可以追溯至东汉出现的《九章算术》。它是用来求最大公约数的算法。 二、证明   对于两个整数a,b.假设他们的最大公约数c = gcd( a, b ),则对于b,a mod b的最大公约数也是c,即:gcd( a,b ) = gcd( b,a mod b )。a = kb + r   证明:     (辗转相除法)     1)令c = gcd(a, b),则设a=xc,b=yc     2)r =a - kb=xc - kyc=(x - ky)*c,则有c也是r的约数,即:c为a mod b的约数。     3)从而可以得到x, ky没有公约数(反证法可以证明)     从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r)。     证毕。 三、算法    1   int gcd( int a, int b ) { 2     return b ? gcd( b, a % b ) : a; 3   } View Code    四、扩展算法     对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在唯一的整数 x,y (注意:这里是整数,也可以为负数),使得 gcd(a,b)=ax+by。     当b = 0时,gcd(a,b)=1,x = 1, y = 0。     又由于有: gcd(a,b)=  gcd(b,a mod b),则有gcd(a,b)=bx' + (a mod b)y' ,由此容易得出可有递归求出x,y。     算法: 1 int exgcd(int a, int b, int &x, int &y) { //x, y 是全局性的 2 int r, swap; 3 if( b == 0 ){ 4 x = 1; 5 y = 0; 6 return a; 7 } 8 9 r = exgcd( b, a%b, x, y ); 10 swap = x 11 x = y; 12 y = ( swap - a/b * y); 13 return r; 14 } View Code    

上一篇:进程间通信IPC(二)——FIFO
下一篇:rtp中的负载类型及时间戳

相关文章

相关评论