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 。 故
