LCM与GCD算法
LCM与GCD算法
hotarugali
发布于 2022-03-03 19:57:27
发布于 2022-03-03 19:57:27
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 。 故
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-09-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录