LCM（最小公倍数）和 GCD（最大公因数）在做 ACM 题时经常会用到，求两个整数的 LCM 和 GCD 有两种方法。

1. 辗转相除法（欧几里得算法）

• 定理：对于任意的两个整数 $a,b (a \geq b)$， 有 $(a,b) = (b, a\%b)$ 。（$(a, b)$ 表示 $a$ 和 $b$ 的最大公因数）

证明如下：

   $a = qb + r$，其中 $q$ 为整数，$0 \leq a \lt b$ 。
   设 $d = (a, b)$，则 $b = md$，$a = nd$ 。
   则 $a = qmd + r = nd$，进一步推出 $r = (n-qm)d$ 。
   故 $d$ 也是 $r$ 的因数，即 $d \leq (b, r) = (b, a\%b)$ 。
   同理，设 $p = (a, a\%b) = (a, r)$，则 $r = sp$，$b = tp$，$d \leq p$ 。
   则 $a = qtp + sp = (qt+s)p$ 。
   故 $p$ 也是 $a$ 的因数， 即 $p \leq (a, b) = d$ 。
   综上，$d = p$，原命题得证 。

所以要求两个数的最大公因数，只需根据递推式不断进行递推，并更新 $a = b$, $b = a\%b$, 直到 $a\%b = 0$ 为止，则此时的 $a$ 即为 $(a, b)$ . 求得 $(a, b)$ 以后，则 $[a, b]$ （最小公倍数）便可由 $ab/(a, b)$ 求得 。

2. 素因子分解

• 定理：任意一个正整数都能分解成若干个素数的幂的乘积的形式。

证明略 。

由此可知，$a = p^{a_1}_1 p^{a_2}_2 \cdots p^{a_n}_n$，$b = p^{b_1}_1 p^{b_2}_2 \cdots p^{b_n}_n$ . 其中 $a_i, b_i \geq 0$ 。
故

$$\begin{array}{c} (a, b) = p^{\min(a_1,b_1)}_1 p^{\min(a_2,b_2)}_2 \cdots p^{\min(a_n,b_n)}_n \\ [a, b] = p^{\max(a_1,b_1)}_1 p^{\max(a_2,b_2)}_2 \cdots p^{\max(a_n,b_n)}_n \end{array}$$