INFO

若无特殊说明，本章涉及的变量皆为正整数。

最大公因数

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

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

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

递归到 $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$ 的最小公倍数记作 $\mathrm{lcm}(a,b)$，简记为 $[a,b]$。

设 $\gcd (a,b)=d$，则 $\mathrm{\exists }{k}_1,k_2$，$a=k_{1}d$，$b=k_{2}d$，所以：

$$\mathrm{lcm}(a,b)=k_1{k}_{2}d=\frac{k_{1}d\cdot k_{2}d}{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$ 是常数。

设 $a{x}_1+b{y}_1=\gcd (a,b)$,

设 $b{x}_2+(amodb)y_2=\gcd (b,amodb)$,

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

$$\begin{array}{rl}& a{x}_1+b{y}_1\\ =& b{x}_2+(amodb)y_2\\ =& b{x}_2+(a-\lfloor \frac{a}{b}\rfloor \cdot b)y_2\\ =& b{x}_2+a{y}_2-\lfloor \frac{a}{b}\rfloor \cdot b{y}_2\\ =& a{y}_2+b(x_2-\lfloor \frac{a}{b}\rfloor \cdot y_2)\end{array}$$$$\therefore \{\begin{array}{rl}{x}_1& =y_2\\ y_1& =x_2-\lfloor \frac{a}{b}\rfloor \cdot y_2\end{array}$$

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

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

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);
}