MENU

GCD模板及证明

February 24, 2019 • Read: 316 • 算法

欧几里得算法

欧几里得算法,也叫辗转相除,简称GCD,用于计算两个整数的最大公约数

引理

$gcd(a, b)=gcd(b, a\%b)$

证明

设$c = gcd(a,b)$,则一定存在一对互质数$x,y$,使得$a = xc, b = yc$

设$r = a % b$,则$r = a - pb = xc - pyc = (x - py)c$

因为$b=yc$,可知$y$与$x-py$互质,所以$r$与$b$的最大公约数为$c$,即$gcd(b,r) = c = gcd(a,b)$。证毕

模板

int gcd(int n, int m) {
    if (m == 0)
        return n;
    if (n < m)
        return gcd(n, m % n);
    return gcd(m, n % m);
}

也可以写成迭代形式,一般来说迭代比递归快

int gcd(int a, int b) {
    while (b != 0) {
        int r = b;
        b = a % b;
        a = r;
    }
    return a;
}

复杂度

设$a$和$b$是两个自然数,不妨假设$a > b$,此时函数会按照$gcd(a,b)$ -> $gcd(b,a \% b)$ -> $gcd(a \% b, b \% (a \% b))$这样递归下去。当$b > \frac{a}{2}$时,可以认为每次递归的参数减少为原来的一半,时间复杂度为$O(logn)$

Archives Tip
QR Code for this page
Tipping QR Code