求最大公约数实际上是一个非常简单的问题，但是在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
原文：http://www.cnblogs.com/tianxia2s/p/3858674.html