欧几里德算法 – 专业青少年编程

最大公约数和最小公倍数（Least Common Multiple）是竞赛中频繁出现的考点。

GCD定义
整数a和b的最大公因数是指能同时整除a和b的最大整数，记为gcd(a, b)。
例如：gcd(15, 81) = 3，gcd(0, 44) = 44，gcd(0, 0) = 0，gcd(-6, -15) = 3，gcd(-17，289) = 17。
注意：由于-a的因子和a的因子相同，因此gcd(a, b) = gcd(|a|, |b|)。编码时只需要关注正整数的最大公因数。
GCD性质
（1）gcd(a,b) = gcd(a, a+b) = gcd(a, ka+b)
（2）gcd(ka, kb) = k·gcd(a, b)
（3）定义多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)
（4）若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素。这个定理很重要。
（5）gcd(a+cb, b) = gcd(a, b)
GCD编码
编程时可以直接用c++函数std::__gcd(a, b)。注意：参数a和b都应该是正整数，否则可能会返回负数。下面介绍三种算法。

3.1 欧几里得算法
用辗转相除法求gcd，即gcd(a, b) = gcd(b, a mod b)。代码是：

int gcd(int a, int b){  // 一般要求a>=0, b>0。若a=b=0，代码也正确，返回0
	return b? gcd(b, a%b):a;
}

这是竞赛中最常用的编码，它极为高效，“拉梅定理”给出了复杂度分析。
拉梅定理：用欧几里得算法计算两个正整数的最大公因数，需要的除法次数不会超过两个整数中较小的哪个十进制数的位数的5倍。
推论：用欧几里得算法求gcd(a, b)，a > b，需要O ( ( l o g ₂ a ) _³ ) 次位运算。
欧几里得算法的缺点是需要做除法取模运算，而高精度大数的除法比较耗时，此时可以用“更相减损术”2和stein算法，它们只用到了减法和移位操作。

不过，在竞赛中不太可能直接使用“更相减损术”和stein算法求最大公约数。下面的介绍，只是为了帮助读者理解GCD的性质。

3.2 更相减损术
计算基于这一性质：gcd(a, b) = gcd(b, a-b) = gcd(a, a-b)。

计算步骤：用较大的数减较小的数，把所得的差与较小的数比较，然后继续做减法操作，直到减数和差相等为止。
编码也很简单：

int gcd(int a, int b){
   while(a != b){   //a==b时结束计算
	   if(a > b)  a = a - b;
	   else       b = b - a;
   }
   return a;
}

更相减损术虽然避免了欧几里得的取模计算，但是计算次数比欧几里得算法多很多，极端情况下需要计算O ( m a x ( a , b ) ) O(max(a, b))O(max(a,b))次，例如a = 100，b = 1时，需计算100次。

3.3 Stein算法
它是更相减损术的改进。求gcd(a, b)时，可以分为几个情况进行优化：
1）a、b都是偶数。gcd(a, b) = 2gcd(a/2, b/2)，计算减半。
2）a奇b偶（或a偶b奇）。根据这一原理：若k与y互为质数，有gcd(kx, y) = gcd(x, b)。k = 2时，有gcd(a, b) = gcd(a/2, b)，即偶数减半。
3）a、b都是奇数。gcd(a, b ) = gcd( (a+b)/2, (a-b)/2 )。
算法的结束条件仍然是gcd(a, a) = a。
除2操作用移位就可以了，所以Stein算法只用到加减法和移位。
关于高精度大数的GCD计算，读者可以用下面这一题练习，类似的题有hdu 5050。

SuperGCD 洛谷 P2152

4. LCM

a和b的最小公倍数lcm(a, b)，可以从算术基本定理推理得到。注意先做除法再做乘法，如果先做乘法可能会溢出。

int lcm(int a, int b){ 
	return a / gcd(a, b) * b;
}

5. 题目

GCD的题目一般和其他知识点结合出题。
hdu 2104，互素判定
hdu 3092，GCD+完全背包
hdu 5970，GCD+循环节
hdu 5584，LCM问题
洛谷 P2568 ，GCD + 莫比乌斯反演
洛谷 P2398，GCD求和
洛谷 P1890，询问区间内的GCD
poj 1722，GCD思维题
poj 2685，GCD+快速幂
poj 3101，大数GCD
poj 2429，GCD + Rabin-Miller测试

Level2题解（11-20）

4. LCM

5. 题目