GCD与LCM

最大公约数（GCD）

最大公约数，也称为最大公因数或最大公因子，是两个或多个整数共有的最大正整数。通常用符号 $\text{gcd}(a, b)$ 表示，其中 $a$ 和 $b$ 是整数。最大公约数有广泛的应用，例如简化分数、判断两个数的互质性等。

整除的定义：

$a$ 能整除 $b$，记为 $a|b$。其中，$a$ 和 $b$ 为整数，且 $a \neq 0$，$b$ 是 $a$ 的倍数，$a$ 是 $b$ 的约数（因子）。

1. 若 $a, b, c$ 都是整数，且 $a|b, b|c$ 则 $a|c$。
2. 若 $a, b, m, n$ 为整数，且 $c|a, c|b$，则 $c|(m \cdot a + n \cdot b)$。
3. 定理：带余除法。 若 $a$ 和 $b$ 都为整数且 $b > 0$，且存在唯一的整数 $q, r$，使得 $a = b \cdot q + r$，其中 $0 \leq r < b$。

GCD

1. 定义

整数 $a$ 和 $b$ 的最大公约数是指能同时整除 $a$ 和 $b$ 的最大整数，记为 $\text{gcd}(a, b)$。
注意：由于 $-a$ 的因子和 $a$ 的因子相同，因此 $\text{gcd}(a, b) = \text{gcd}(|a|, |b|)$，代码中只关注正整数的情况。

2. 性质

• $\text{gcd}(a, b) = \text{gcd}(a, a + b) = \text{gcd}(a, k \cdot a + b)$
• $\text{gcd}(ka, kb) = k \cdot \text{gcd}(a, b)$
• 多个整数的最大公约数：$\text{gcd}(a, b, c) = \text{gcd}(\text{gcd}(a, b), c)$
• 若 $\text{gcd}(a, b) = d$ 则 $\text{gcd}\left(\frac{a}{d}, \frac{b}{d}\right) = 1$，即 $\frac{a}{d}$ 和 $\frac{b}{d}$ 互质
• $\text{gcd}(a + cb, b) = \text{gcd}(a, b)$

3. 代码

• 可以使用 C++ 自带函数 std::__gcd(a, b)，注意参数必须为正整数，否则可能会返回负数。
• 可以使用欧几里得算法求解。
• 更相减损术。

欧几里得算法

int gcd(int a,int b)
{
	return b ? gcd(b,a % b) : a;
}

比如要求$a = 7和b = 42$的最大公约数
计算 $a \div b$ 的商和余数，即 $q = \lfloor \frac{7}{42} \rfloor = 0$，$r = a \mod b = 7$。
由于余数 $r$ 不为零，将 $b$ 赋值给 $a$，将 $r$ 赋值给 $b$，即 $a = b$，$b = r$。
再次计算新的 $a \div b$ 的商和余数，即 $q = \lfloor \frac{42}{7} \rfloor = 6$，$r = a \mod b = 0$。
由于余数 $r$ 为零，辗转相除法结束。最终的最大公约数为当前的 $b$，即 $\text{gcd}(7, 42) = 7$。
通过辗转相除法，我们得到了数 7 和 42 的最大公约数为 7。
这个过程一直重复直到余数为零。每一步都将两个数的位置互换，然后进行除法运算，直到余数为零为止。

LCM

$a和b的最小公倍数表示为lcm(a,b)$其中 $\text{lcm}(a, b) = \frac{a \cdot b}{\text{gcd}(a, b)}$。

算术基本定理

又称唯一分解定理。
任何大于 1 的正整数 $n$ 都可以唯一分解为有限个素数的乘积，即

$$n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}$$

其中 $p_1, p_2, \ldots, p_k$ 为素数，而 $e_1, e_2, \ldots, e_k$ 为对应素数的指数。这个分解是唯一的，即不存在其他方式将 $n$ 表示成素数的乘积。

证明：$\text{lcm}(a, b) = \frac{a \cdot b}{\text{gcd}(a, b)}$

根据算术基本定理，我们可以将正整数 $a$ 和 $b$ 分别分解为其素因数的乘积：

$a = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}$
$b = p_1^{f_1} \cdot p_2^{f_2} \cdot \ldots \cdot p_k^{f_k}$

其中 $p_1, p_2, \ldots, p_k$ 为素数，而 $e_1, e_2, \ldots, e_k$ 和 $f_1, f_2, \ldots, f_k$ 分别为 $a$ 和 $b$ 中对应素数的指数。

最小公倍数 $\text{lcm}(a, b)$ 是 $a$ 和 $b$ 的所有素因数的最大指数的乘积：

$$\text{lcm}(a, b) = p_1^{\max(e_1, f_1)} \cdot p_2^{\max(e_2, f_2)} \cdot \ldots \cdot p_k^{\max(e_k, f_k)}$$

最大公约数 $\text{gcd}(a, b)$ 是 $a$ 和 $b$ 的所有素因数的最小指数的乘积：

$$\text{gcd}(a, b) = p_1^{\min(e_1, f_1)} \cdot p_2^{\min(e_2, f_2)} \cdot \ldots \cdot p_k^{\min(e_k, f_k)}$$

现在，我们将 $\text{lcm}(a, b)$ 和 $\text{gcd}(a, b)$ 代入等式 $\text{lcm}(a, b) = \frac{a \cdot b}{\text{gcd}(a, b)}$ 进行验证：

$$\text{lcm}(a, b) = p_1^{\max(e_1, f_1)} \cdot p_2^{\max(e_2, f_2)} \cdot \ldots \cdot p_k^{\max(e_k, f_k)}$$

$$\frac{a \cdot b}{\text{gcd}(a, b)} = \frac{p_1^{e_1 + f_1} \cdot p_2^{e_2 + f_2} \cdot \ldots \cdot p_k^{e_k + f_k}}{p_1^{\min(e_1, f_1)} \cdot p_2^{\min(e_2, f_2)} \cdot \ldots \cdot p_k^{\min(e_k, f_k)}}$$

通过约简，我们可以看到它们是相等的。

这样，我们就证明了 $\text{lcm}(a, b) = \frac{a \cdot b}{\text{gcd}(a, b)}$。

代码

注意最好先除后乘，以防爆炸。

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