欧几里得算法

$a$ 和 $b$ 的最大公因数记作 $gcd(a,b)$，简记为 $(a,b)$.

若 $a,b$ 有公因数 $d$，则 $a \bmod b = a - b \cdot\left\lfloor\frac{a}{b}\right\rfloor$ 也有因数 $d$. 也就是说，$a$ 和 $b$ 的所有公因数，同时也是 $b$ 和 $a \bmod b$ 的公因数，因此它们的最大公因数也相等.

$$gcd(a,b)=gcd(b,a \bmod b)$$

递归到 $b=0$ 时，$a$ 即为 $gcd(a,b)$.

时间复杂度为 $O(log{(a+b)})$.

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

$a$ 和 $b$ 的最小公倍数记作 $lcm(a,b)$，简记为 $[a,b]$.

设 $gcd(a,b)=d$，则 $a=k_1d,b=k_2d$，所以：

$$lcm(a,b)=k_1k_2d=\frac{k_1d\cdot k_2d}{d}=\frac{ab}{gcd(a,b)}$$

时间复杂度为 $O(log{(a+b)})$.

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

扩展欧几里得算法用于求方程 $ax+by=gcd(a,b)$ 关于 $x,y$ 的解，其中 $a,b$ 是常数.

设 $ax_1+by_1=gcd(a,b)$,

设 $bx_2+(a \bmod b)y_2=gcd(b,a \bmod b)$,

由 $gcd(a,b)=gcd(b,a \bmod b)$ 可知：

$$\begin{aligned} ax_1+by_1&=bx_2+(a \bmod b) y_2\\ &=bx_2+(a-\left\lfloor\frac{a}{b}\right\rfloor\cdot b) y_2\\ &=bx_2+ay_2-\left\lfloor\frac{a}{b}\right\rfloor\cdot by_2\\ &=ay_2+b(x_2-\left\lfloor\frac{a}{b}\right\rfloor\cdot y_2) \end{aligned}$$

$$∴\left\{\begin{aligned}x_1&=y_2\\y_1&=x_2-\left\lfloor\frac{a}{b}\right\rfloor\cdot y_2\end{aligned}\right.$$

因此，考虑先递归求解 $bx+(a \bmod b)\ y=gcd(a,b)$，再由其解推出 $ax+by=gcd(b,a \bmod b)$ 的解.

边界条件：当递归到 $b=0$ 时，一定有一组解 $\left\{\begin{aligned}x&=1\\y&=0\end{aligned}\right.$.

struct Set {
    int x, y;
    Set(int x, int y) : x(x), y(y) {}
};

Set exGcd(int a, int b) {       // 求解 ax + by = gcd(a, b)
    if (b == 0)
        return Set(1, 0);
    Set ans = exGcd(b, a % b);  // 先递归求解 bx + (a % b)y = gcd(b, a % b)
    return Set(ans.y, ans.x - (a / b) * ans.y);
}