首页 > 代码库 > 论求最大公约数的方法

论求最大公约数的方法

求最大公约数实际上是一个非常简单的问题,但是在ACM中如何将效率搞的最高也需要一点点技巧。下面将今天收集到的一点资料粘贴在此处。

书上是说: 
1.输入m、n(m为被除数,n为除数)
2.m/n得余数r。
3.判断r=0?是的话n为最大公约数。
4.否则将n赋给m,r赋给n,循环2.
辗转相除法:如: 求(45, 72)

72/45 = 1 余 27 不等于0,再除
45 /27= 1 余 18 不等于0,再除
27/18= 1 余 9 不等于0,再除
18/9 = 2 余 0 等于0,结束。

所以 (45, 72)=9

int gcd(long a,long b){

long r;
r = a%b;//这里是可以不管两者的相对大小的,因为后面两个数还是要互换
while(r!=0){
a=b;
b=r;
r =a%b;
}
return b;
}//这个就是欧几里德的算法

//就是计算有余数时就选择将除数赋值给被除数,将余数赋值给除数,然后循环,直到最后余数为0时停止
当然,当你求得最大公约数时就相当于求得了最小公倍数,
因为最小公倍数=M*N/最大公约数

例题:杭电2503