欧几里得算法¶

又叫辗转相除法，用于求两数的最大公约数（Greatest common divisor）和最小公倍数（Least common multiple）。

引理¶

不妨设 \(a > b\)，这个算法的基础是

由于 \(a > b\)，假设

设 \(a\) 和 \(b\) 的公约数为 \(c\)，根据 整除 的性质有

这说明 \(a\) 和 \(b\) 的所有公约数也是 \(b\) 和 \(a \bmod b\) 的公约数。

反过来，设 \(b\) 和 \(a \bmod b\) 的公约数为 \(c\)，根据 整除 的性质也有

这说明 \(b\) 和 \(a \bmod b\) 的所有公约数也是 \(a\) 和 \(b\) 的公约数。

所以，\(a, b\) 的公约数和 \(b,(a \bmod b)\) 的公约数都是一样的，那最大公约数也是一样。

递归实现¶

利用上面的性质不断递归，直到 \(b\) 变成 \(0\)。这时候，上一轮 \(a \bmod b = 0\)，即 \(b \mid a\)，最大公约数肯定是 \(b\)（这一轮的 \(a\)）。

暂时不考虑负数。

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

这个函数不要求 \(a>b\)，如果 \(a<b\) 的话，就会递归调用 \(\gcd(b,a)\)。

迭代实现¶

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

最小公倍数¶

时间复杂度¶

为了简单，只考虑 \(a,b\) 均为正数，并且用 floor 方式计算 模运算 的商的情况。

实际上就是计算 \(a \bmod b\) 减小至 \(0\) 的速度。不妨设 \(a>b\)，如果 \(b \le \dfrac{1}{2}a\)，有

如果 \(\dfrac{1}{2}a < b < a\)，由于 \(a\) 比 \(b\) 大，所以 \(\left\lfloor \dfrac{a}{b} \right\rfloor \ge 1\)，因此

结合 \((1)(2)\) 可得 \((a \bmod b) \le \dfrac{1}{2}a\)。

在计算 \(\gcd(a,b)\) 时，会递归调用 \(\gcd(b,a \bmod b)\)，再递归调用 \(\gcd(a \bmod b, b \bmod (a \bmod b))\)，... 根据刚才的结论，有

所以，每调用两次 \(\gcd\)，第二个参数至少减少一半，时间复杂度为 \(O(\log b)\)。

相关文章

• 扩展欧几里得算法
• 欧拉定理（数论）
• 欧拉函数（数论）
• 同余