GCD 模板及证明

欧几里得算法

欧几里得算法，也叫辗转相除，简称 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)$