1,两个数互质:如果说两个数的公因数只有1,则可以说这两个数互质。
欧几里得算法求最大公约数:
首先求最大公约数,假设我们要求a和b的最大公约数
设a mod b = c;
可以得到一下的递推过程:
a = kb + c ;
假设a , b 的最大公约数为d,则可以得到:
a = md , b = nd;
可知m , n 互质;
c = a - kb = md - knd = (m-kn)d;
我们已经知道m,n互质,则可以知道n和m-kn互质,则c和b的最大公约数也是d;
所以由以上的推论,我们可以得到,a , b的最大公约数等于b和a mod b 的最大公约数,递归迭代运算,直到两个数相等的时候,此时的a和b的值即为最大公约数。
int -2147483648 ~ +2147483647 (4 Bytes)
unsigned int 0 ~ 4294967295 (4 Bytes)
long == int
long long -9223372036854775808 ~ +9223372036854775807 (8 Bytes)
欧几里得算法求最大公约数的局限性:
在应用辗转相除法求最大公约数的时候,如果利用上面的方法求最大公约数,如果要对大整数求最大公约数,辗转相除法的效率就出现了一定的问题,实际上对于大整数来说,大整数相除的时间开销是非常昂贵的,这就是辗转相除法的局限性。
解决方法:
可以借鉴欧几里得的辗转相除法,既然是取模运算导致的问题,那么我们就不用取模运算,换用“-”运算,即 f(x,y)=f(x-y,y);深入考虑一下发现在算法运行的过程可能会出现x<y的情况,这时候要交换x和y,但是结果不受影响。再来看看代码吧。
BigInt GCD(BigInt x,BigInt y)
{
if(x < y) return GCD(y,x);
return (!y) ? x : GCD(x-y,y);
}
代码中用到的BigInt是大整数类,可以存储成百上千位的整数。这个类怎么实现呢?这里不多说,具体网上有好多的相关文章来讲解高精度算法的,要是看书籍的话,强烈推荐ACM大牛刘汝佳的《算法竞赛入门经典》一书,对高精度的介绍还是非常好的。
对于大数运算问题是解决了,然而,细心的读者会发现,这个算法引入了另外一个问题,那就是当x和y相差很多时,算法的迭代次数会过高,导致了算法的效率较低,例如计算GCD(100000000000001,1)。这种情况确实存在啊,于是我们要考虑其他的优化了。
两个数的最小公倍数=两个数的乘机/最大公约数;