LCM与GCD算法

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

1. 辗转相除法(欧几里得算法)

  • 定理:对于任意的两个整数 a,b(ab)a,b (a \geq b), 有 (a,b)=(b,a%b)(a,b) = (b, a\%b) 。((a,b)(a, b) 表示 aabb 的最大公因数)

证明如下:

   a=qb+ra = qb + r,其中 qq 为整数,0a<b0 \leq a \lt b
   设 d=(a,b)d = (a, b),则 b=mdb = mda=nda = nd
   则 a=qmd+r=nda = qmd + r = nd,进一步推出 r=(nqm)dr = (n-qm)d
   故 dd 也是 rr 的因数,即 d(b,r)=(b,a%b)d \leq (b, r) = (b, a\%b)
   同理,设 p=(a,a%b)=(a,r)p = (a, a\%b) = (a, r),则 r=spr = spb=tpb = tpdpd \leq p
   则 a=qtp+sp=(qt+s)pa = qtp + sp = (qt+s)p
   故 pp 也是 aa 的因数, 即 p(a,b)=dp \leq (a, b) = d
   综上,d=pd = p,原命题得证 。

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

2. 素因子分解

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

证明略 。

由此可知,a=p1a1p2a2pnana = p^{a_1}_1 p^{a_2}_2 \cdots p^{a_n}_nb=p1b1p2b2pnbnb = p^{b_1}_1 p^{b_2}_2 \cdots p^{b_n}_n . 其中 ai,bi0a_i, b_i \geq 0

(a,b)=p1min(a1,b1)p2min(a2,b2)pnmin(an,bn)[a,b]=p1max(a1,b1)p2max(a2,b2)pnmax(an,bn)\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}


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!