辗转相除法

辗转相除法（欧几里得算法）求最大公约数，快得惊人。做法：用大数除以小数取余数，再用刚才的小数除以这个余数，反复下去，直到余数为 0，此时的除数就是答案。

依据是一条性质：$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$。因为 $a$ 和 $b$ 的公共因数，同时也是 $b$ 和余数的公共因数，越换数越小，最后必然停下。

算 $\gcd (48,18)$：
$$48\mathrm{mod}18=12\to 18\mathrm{mod}12=6\to 12\mathrm{mod}6=0$$
余数为 0，除数是 6，所以答案是 6。

int gcd(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

复杂度约 $O(\log \min (a,b))$，极快。常见坑：循环条件是 while (b)，即 b 变成 0 就停，最后返回的是 a 不是 b；谁大谁小不用提前排——第一轮取模会自动调整过来。