GCD和LCM 欧几里得算法

EndlessLethe原创文章,转载请注明: 转载自小楼吹彻玉笙寒

本文链接地址: GCD和LCM 欧几里得算法


前言

欧几里德算法作为有着非常简短的实现的算法,可能很多初学者(包括当时的我)都不求甚解。本文给出了GCD、LCM的性质,以及欧几里德算法的实现、证明和时间复杂度推导。

什么是欧几里得算法

最大公约数问题是最早被研究的算法问题之一了,并且是ACM竞赛中能涉及到的很多数论内容,比如模线性方程,模线性方程组的基础。

欧几里得算法 (Euclidean algorithm) ,即大部分选手所知的“辗转相除法”,其核心在于不断将两数规模变小,最后实现对数时间内求解两个数的最大公约数。

其核心是:\[gcd(a,b) = gcd(b, a \% b)\]

名词解释

  1. 最大公约数:即最大公因子,能够同时整除a和b的最大因子,记作gcd(a, b),或gcd
  2. 最小公倍数:能够被a和b整除的最小数,记作lcm(a, b),或lcm。
  3. %:指的是取余运算(取模运算),用例: a % b
  4. |:指的是整除运算,a | b表明a可以整除b,即a是b的因子

GCD和LCM的一些性质

  1. a, b都能分解为有限个素数的积
  2. gcd(a, b)中只含a,b的全部公共素因子
  3. lcm(a, b)中含有a,b的所有素因子
  4. \(gcd\%lcm=0\)
  5. \(gcd * lcm = a * b\)
  6. \(lcm/gcd = a/gcd * b/gcd\)
  7. \(gcd(ka, kb) = k * gcd(a, b)\)
  8. \(lcm(ka, kb) = k * lcm(a, b)\)
  9. \(lcm(\frac{a}{b},\frac{c}{d})=\frac{lcm(a,c)}{gcd(b,d)}\)

简单证明

这里只证明第六个性质:\[gcd * lcm = a * b\]
根据\(a / gcd\) 和 \(b / gcd\) 这两个数互质,且两者包含a、b的非公共素因子
故\[lcm = gcd * (a / gcd) * (b / gcd)\\
lcm = (a * b) / gcd\]
所以\(a*b = gcd * lcm\)

Note:我们习惯写为lcm = a / gcd * b,以此来避免溢出。而且通常使用变形后的等式性质七。

直观理解欧几里德算法

我们不妨设\(a = m * gcd\), \(b = n * gcd\)
那么通过恒等式\(gcd(a,b) = gcd(b, a \% b)\),a将减少若干个b即(n*gcd)到\(a \% b * gcd\)
交换后\(a = n * gcd, b = a % b * gcd\)

因为每次交换都会减少很多个gcd,无疑是很快的(后面会证明,至少是对数的)

欧几里德算法实现

等式\(gcd(a,b) = gcd(b, a \% b)\)可以理解为一个数减小,再两个数交换。
因为两个数的值经过循环不断变小,在结束循环前,两个数不可能小于0,且不可能同时为0。
所以最后b先变为0,且有
\[gcd(a_n,b_n)=\cdots=gcd(a_{n−1},b_{n−1})=gcd(a_0,0)\\
a_0 = gcd(a, b)
\]

递归版

ll gcd(ll a, ll b) {
   return !b ? a : gcd(b, a%b);
}

迭代版

ll gcd(ll a, ll b) {
    while (b != 0) {
        ll res = a % b;
        a = b;
        b = res;
    }
    return a;
}

证明gcd(a,b) = gcd(b, a % b)

\[
我们为了简化,默认a>b:\\
设gcd(a,b)=d,gcd(b,a-bx)=e,\\
∵d|a,d|b\\
∴d|a-bx\\
∴d|gcd(b,a-bx),即d|e\\
∵e|b,e|a-bx\\
∴e|bx+(a-bx),即e|a\\
∴e|gcd(a,b),即e|d\\
∴d=e\\
证毕。
\]

斐波那切数列和GCD

斐波那契数列有这样一条性质:
\[gcd(F_n,F_m)=F_{gcd(n,m)}\]

证明见参考文献VII“斐波那契数列与gcd之间一个有趣的定理

时间复杂度

最差时间复杂度

这里给结论:欧几里得算法最差的情况下就是斐波那契数列相邻的两项
即:\[F_{s} \leq a \leq F_{s+1}\]
a为两个数中较大的,s为最大操作次数(最坏时间复杂度),F为斐波那契数列。

平均时间复杂度

给结论:\(s = (12 * \ln 2 * \ln N) / π ^ 2 + 1.47\) (N为其中较小的那个数)

不过上面的结论需要大量的数学推导,我们不妨根据斐波那切数列的通项公式来理解:
则s的增长速度是对数,时间复杂度是对数的

证明

我给出一个自己的证明,其他证明可以见参考文献:
\[
为了方便理解递推关系式,设一共会辗转n次,a_n=a, b_n=b\\
即gcd(a_n,b_n)=\cdots=gcd(a_{n−1},b_{n−1})=gcd(a_0,0)\\
因为有gcd(a_n,b_n) = gcd(b_n, a_n \% b_n) = gcd(a_{n-1}, b_{n-1})\\
存在关系a_{n-1}=b_n,a_n=t * b_n+b_{n-1}\\
不妨推广为a_{k-1}=b_k,a_k=t * b_k+b_{k-1}\\
将a_k、b_k用a_{k-1}、b_{k-1}表示\\
得到递推式:ak=tb_k+b_{k-1}=ta_{k-1}+a_{k-2}\\b_k=a_{k-1}
\]

为了让an和bn尽量小(达到最坏时间复杂度),我们应该让t=1:\[a_k=a_{k-1}+a_{k-2}\\b_k=a_{k-1}\]

第0次第1次第2次第3次第4次第n次
agcdgcd2*gcd3*gcd5*gcdFn*gcd
b0gcdgcd2*gcd3*gcdFn-1*gcd

故对于\(a=F_n * gcd,b=F_{n-1} * gcd\),欧几里德算法会达到最坏的复杂度。

题目总结

  • Uva 11388
    只需要利用性质六即可

  • HIT OJ 2010 GCD & LCM Inverse
    可以根据性质六+暴力枚举通过HIT OJ,但不能通过POJ 2429,代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
   return !b ? a : gcd(b, a%b);
}

int main() {
    ll x, y;
    while (cin >> x >> y) {
        ll t = y / x;
        for (ll i = sqrt(t); i > 0; i--) {
            if (t % i == 0) {
                if (gcd(t / i, i) == 1) {
                    cout << i * x << " " << y / i << endl;
                    break;
                }
            }
        }    
        }
        return 0;   
}
  • Zoj 1577 GCD & LCM
    需要素因子分解,暴力分解可过

  • POJ 2429 GCD & LCM Inverse
    将HIT OJ 2010暴力枚举修改为素因子分解,然后暴力计算最接近sqrt(lcm/gcd)的组合,即可通过POJ。

  • POJ 3101
    可以根据相对速度,也可以根据公式\(\frac{x}{a}%\frac{1}{2}=\frac{x}{b}%\frac{1}{2}=\frac{x}{c}%\frac{1}{2}\)
    化简一下都是同一个东西,然后根据分数的gcd公式。需要高精度。

参考文献

I. 欧几里得算法原理
II. 关于lcm,gcd的一些性质
III. ACM数论之旅3—最大公约数gcd和最小公倍数lcm(苦海无边,回头是岸( ̄∀ ̄))
IV. 欧几里得算法证明
V. 数论学习小记 其之三 Gcd与Lcm
VI. 【POJ3101】Astronomy——分子的最小公倍数
VII. 斐波那契数列与gcd之间一个有趣的定理
VIII. gcd常见结论及gcd与斐波那契结合–hdu6363.
IX. 辗转相除法求最大公约数(gcd)的斐波那契数列(fib)最坏时间复杂度的证明
X. 欧几里得算法(即辗转相除法)的时间复杂度
XI. 欧几里得算法时间复杂度简单分析

1 评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注