LCM与GCD算法

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