最大公约数（GCD）与欧几里得算法

最大公约数（Greatest Common Divisor，GCD）

两个数最大公约数顾名思义，两个数的所有公约数中最大的。

若正整数 $a,b$ 的质因数分解为

则其最大公约数为

两个数 $a$ 与 $b$ 的最大公约数通常记作

或直接记作

假定 $a \ge b>0$ 显然两个数的最大公约数不会超过较小的数字 $b$，

于是我们得到了一种枚举的方式得到最大公约数，只要枚举 $b$ 到 $1$ 之间的所有值即可得到 $a$，$b$ 的最大公约数。但这显然太慢了，考虑 $(a,b) = 1$ 的情况我们要花费 $O(\min(a,b))$ 的时间这是完全无法接受的。

辗转相减

设 $(a,b) = g$，

如果 $a = b$ 则 $a = b = g$，

此外的情况，假定 $a > b$，

则我们发现 $g|a$ 又 $g|b$ 则 $g|(a-b)$

也就是说 $(b,a-b) \ge g$

假设 $(b,a-b) = c > g$，

则 $c|(a-b), c|b$ 从而 $c|(a-b+b)$ 则 $c|a$。

注意到此时 $c$ 是 $a$ 与 $b$ 的公因子且大于 $g$ 这与 $(a,b) = g$ 矛盾，因此，

我们知道 $(a,b) \ge 1$，而算法每运行一次，总会使得两个数的总值严格下降，直到 $a=b$。

int gcd(int a,int b)
{
    if(a==b) return a;
    if(a<b) swap(a,b);
    return gcd(a-b,b);
}

我们已经得到了一个“非常好”的递归算法。但求 $(2,10^{18})$ 不就爆炸了吗。

欧几里得算法 辗转相除

此时我们注意到，我们总是把一个较大的数减到小于等于较小的数为止，然后才会换减数。

这个过程像极了爱情除法。我们用整数除法把较大的数 $a$ 除以较小的数 $b$，如果能整除说明较小的数$b = (a,b)$，否则我们会从 $a$ 里减掉最多次数的 $b$，即从 $a$ 中减掉 $\left\lfloor \frac{a}{b} \right\rfloor $ 次 $b$，得到

而这个结果相当于 $a$ 对 $b$ 取模（取余）。

int gcd(int a,int b)
{
    if(a<b) swap(a,b);
    if(a%b==0) return b;
    return gcd(a%b,b);
}

辗转相除的复杂度

设 $a \ge b$, 若 b|a，则已经得出答案 $T(a,b) = O(1)$

若 $b \nmid a$ 则 $a \neq b$，$a' = a \ \mathrm{mod} \ b$。由 $a > b$ 则 $a-a' > b$ 而 $a' < b$

从而得出结论 $a' < \frac{a}{2}$

也就是说每次取模操作必然使得较大的数字减半则

也就是说我们已经得到了对数级别的优秀算法。

但是这个界其实不是紧界，实际上我们可以通过构造序列证明一个更紧的界。

这里我们考虑让迭代次数尽可能多，这显然就是让 $a$ $b$ 为斐波那契数列的相邻两项嘛

考虑 $a, b(a \ge b)$ 一共需要 $n$ 次取模操作才能得到 $(a,b)$。

令 $A_{n+2} = a, A_{n+1} = b$

则 $A_{i} = A_{i+2} \ \mathrm{mod} \ A_{i+1} ( 0 \le i \le n)$

此时 $A_1 = (a,b) \ge 1$，$A_0 = 0$

考虑斐波那契数列 $F_0 = 0, F_1 = 1, F_i = F_{i-1} + F_{i-2} (i \ge2)$

有

假设 $\forall 0 \le i \le k, F_i \le A_i$ 成立则

于是对于 $b = A_{n+1} \ge F_{n+1}$

换句话说如果较小的数 $b < F_{n+1}$ 则需要的次数将不会超过 $n$ 次。（这里可以采用反证法，考虑存在一个 $b<F_{n+1}$ 且需要次数大于 $m>n$ 的情况，此时我们知道对于 $m$ 次操作而言，$A_{m+1} \ge F_{m+1}$ 而这与假设 $b=A_{m+1} < F_{m+1}$ 相违背）

我们知道对于 $F_{n+1}=N$，$n$ 是 $O(\log(N))$ 的因此对于辗转相除而言复杂度是 $O(\log(\min(a,b)))$ 的。

关于 % 运算

首先我们可以发现，当我们运行

return gcd(a%b,b)

时，其实我们已经知道第一个参数不会大等第二个参数了，因此我们可以考虑将这个语句写成

return gcd(b,a%b)

来尽量减少 swap 操作。

其实

if(a<b) swap(a,b)

这个语句是不必要的，因为如果如果大小关系是反的，经过一次我们修改过的取模操作，那么就会得到正确的大小关系。

注意到如果已经得到 $b|a$ 的一组输入了，其实我们这时知道了 $(a,b) = b$ 但是每次递归中检查

if(a%b==0) return b;

这里取模再判断的操作是一个非常昂贵的操作。如果我们对于这样的 $a,b$ 如果再多递归一次的话，我们会发现我们总会得到一组 $(b,0)$ 这样的输入，换句话说，我们可以考虑将循环终止条件改为判断

if(b==0) return a;

至此我们可以写出一个简短而优美的版本

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

非递归

虽然我们知道对于 gcd 而言递归深度不会很深，但是递归依旧存在。此时我们可以考虑进一步优化这个递归为迭代形式。

int gcd(int a,int b)
{
    int t;
    while(b)
    {
        t=b; 
        b=a%b; 
        a=t;
    }
    return a;
}