辗转相除法

辗转相除法（欧几里得算法）能极快地求最大公约数，它基于一条性质：

$$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$$

做法是用大数除小数取余，再拿"小数"和"余数"重复，直到余数为 0，此时的除数就是答案。

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

举例 $\gcd (12,8)$：$12\%8=4\Rightarrow \gcd (8,4)$；$8\%4=0\Rightarrow \gcd (4,0)$，返回 4。每步余数迅速变小，复杂度只有 $O(\log (\min (a,b)))$，比逐个试快无数倍。

用它可以顺手求最小公倍数：$\mathrm{lcm}(a,b)=a/\gcd (a,b)\times b$。坑：先除后乘，写成 a/gcd*b 而不是 a*b/gcd，避免 a*b 中途溢出。递归写法简洁，也可写成 while 循环版，效果一样。