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 < 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}_1p^{a_2}_2...p^{a_n}_n$ ， $b = p^{b_1}_1p^{b_2}_2...p^{b_n}_n$ . 其中 $a_i,b_i\geq0$ 。
故 $(a, b) = p^{min(a_1,b_1)}_1p^{min(a_2,b_2)}_2...p^{min(a_n,b_n)}_n$ $[a, b] = p^{max(a_1,b_1)}_1p^{max(a_2,b_2)}_2...p^{max(a_n,b_n)}_n$