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)$