INFO

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

最大公因数

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

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

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

递归到 $b=\phantom{0}$$\phantom{0}0$ 时，$a$ 即为 $\gcd (a,\phantom{0}$$\phantom{0}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,\phantom{0}$$\phantom{0}b)$，简记为 $[a,\phantom{0}$$\phantom{0}b]$。

设 $\gcd (a,\phantom{0}$$\phantom{0}b)=\phantom{0}$$\phantom{0}d$，则 $\mathrm{\exists }{k}_1,\phantom{0}$$\phantom{0}{k}_2$，$a=\phantom{0}$$\phantom{0}{k}_{1}d$，$b=\phantom{0}$$\phantom{0}{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+\phantom{0}$$\phantom{0}by=\phantom{0}$$\phantom{0}\gcd (a,\phantom{0}$$\phantom{0}b)$ 关于 $x,\phantom{0}$$\phantom{0}y$ 的解，其中 $a,\phantom{0}$$\phantom{0}b$ 是常数。

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

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

由 $\gcd (a,\phantom{0}$$\phantom{0}b)=\phantom{0}$$\phantom{0}\gcd (b,\phantom{0}$$\phantom{0}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+\phantom{0}$$\phantom{0}(amodb)y=\phantom{0}$$\phantom{0}\gcd (a,\phantom{0}$$\phantom{0}b)$，再由其解推出 $ax+\phantom{0}$$\phantom{0}by=\phantom{0}$$\phantom{0}\gcd (b,\phantom{0}$$\phantom{0}amodb)$ 的解。

边界条件：当递归到 $b=\phantom{0}$$\phantom{0}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);
}