辗转相除

最大公约数

步骤

1. $a$ 对 $b$ 取余，得到余数 $r_1$。
2. $r_1$ 对 $a$ 取余，得到余数 $r_2$
3. $r_2$ 对 $r_1$ 取余，得到余数 $r_3$
4. 重复步骤 $r_i$ = $r_{i-1} \space \% \space r_{i-2}$
5. 直到 $r_i$ 为 0，$r_{i-1}$ 为答案

图解

设 - 为最大公约数d的长度
a = ------- (7d)
b = ----- (5d)

a %= b
a = -- (2d)
b = ----- (5d)

b %= a
a = -- (2d)
b = - (d)

a %= b
a = 0 
b = - (d)

代码

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

最小公倍数

步骤

1. 求出 $a$ 和 $b$ 的最大公约数 $d$。
2. 最小公倍数 $l$ 等于 $\frac{a \cdot b}{d}$。

代码

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