欧几里得算法（GCD）¶

GCD是Great Common Divisor的缩写。

用函数gcd来计算自然数a和b的最大公约数。设a / b的商是p，余数是q。则 $a = b \times p +q$ ，则gcd(b, q)肯定可以整除a，也可以整除b，因为gcd函数的第二个参数始终在减小，最终会有gcd(a, b) = gcd(c, 0)，所以最大公约数是c。

如果存在a < b的情况，那么gcd(a,b) = gcd(b, a % b) = gcd(b, a)，也就是一次递归就会使第一个参数大于第二个参数。

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

时间复杂度低于 $\log(\max(a, b))$ 。

二进制法¶

如果想进一步提高GCD的效率，可以通过不断除以2来降低常数，依据的原理是 $$ GCD(x, y) = GCD(x - y, y) $$ 始终假设 $x \geq y$ ，如果不满足就交换数值。如果x == y，则GCD(x, y) = x，否则：

若x， y均为偶数，则GCD(x, y) = 2 * GCD(x / 2, y / 2);
若x为偶数，y为奇数，则GCD(x, y) = GCD(x / 2, y);
若x为奇数，y为偶数，则GCD(x, y) = GCD(x, y / 2)；
若x为奇数，y为偶数，则GCD(x, y) = GCD(x - y, y).

int GCD(int x, int y)
{
    if (!x) return y; 
    if (!y) return x;
    int num1 = 0, num2 = 0;
    for ( ; (x & 1) == 0; ++num1) x >>= 1; //去掉x里面的2并计数
    for ( ; (y & 1) == 0; ++num2) y >>= 1; //去掉y里面的2并计数
    if (num2 < num1) num1 = num2; //x和y里面共同包含的因子2的个数

    //此时x和y都是奇数
    while (true) {
        if (y > x) x ^= y ^= x ^= y; //位运算加速数值交换
        //判断是否符合退出条件，顺便计算GCD(x - y, y)
        if ((x -= y) == 0) return y <<= num1; //x和y相等的情况，输出结果
        //两个奇数相减后x变为偶数，需要去掉2
        while ((x & 1) == 0) x >>= 1;
    }
}

最小公倍数¶

最小公倍数全称Least Common Multiple，简写为LCM。

两个数x和y的最小公倍数就是x和y的最大公约数，乘上两数与最大公约数的商。

inline int LCM(int x, int y)
{
    return x / GCD(x, y) * y;
}

如果直接计算x * y / GCD(x, y)，存在溢出的风险。

常用技巧：gcd(a*t+b, a) = gcd(a,b)，可以用来解决POJ 2773。

典型题目：

POJ 2773
LeetCode 1071.Greatest Common Divisor of Strings（字符串中的GCD）
P1029 最大公约数和最小公倍数问题（GCD模板题）