首页 > 代码库 > 编程之美----最大公约数问题
编程之美----最大公约数问题
求两个很大的数的最大公约数问题。
解法一：辗转相除法，但当数很大时，取模运算很耗时间。
解法二：利用f(x,y) = f(x-y, y)可以避免取模，但是当第一个数很大，而第二个数很小如1时，也比较耗时。
解法三：对于y和x来说，如果y=k*y1, x= k*x1,那么f(y,x)=k*f(y1,x1)。如果x=p*x1,假设p是素数，并且y%p!=0,那么f(x,y)=f(p*x1,y)=f(x1,y)。于是对于二进制表示的大整数而言可以每次除二了。
1 BigInt gcd(BigInt x, bigInt y) 2 { 3 if(x<y) 4 return gcd(y,x); 5 if(y==0) 6 return x; 7 else 8 { 9 if(IsEven(x))10 {11 if(IsEven(y))12 return (gcd(x>>1,y>>1)<<1);13 else 14 return gcd(x>>1,y);15 }16 else 17 {18 if(IsEven(y))19 return gcd(x,y>>1);20 else 21 return gcd(y,x-y);22 }23 }24 }
编程之美----最大公约数问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。