最大公约数求法——欧几里得与更相减损术

· · 算法·理论

模板题目

最大公约数（gcd），也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。 ——百度百科

最大公约数在初等数论中的应用十分广泛，包括裴蜀定理等。 有许多题目都要求我们求最大公约数，因此学会如何求它是很重要的。

辗转相除法

1.证明

2.代码与用法

实例：求 1997 和 615 的最大公约数。

1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
至此，最大公约数为 1

OKOK 那么好，给出代码：

int gcd(int x, int y) {
    return !y ? x : gcd(y, x % y);
}

其实，在 c++ 中的 algorithm 库中就有一个函数来求最大公约数，它的名字叫 __gcd() ,用法与我们手写的是一样的，而它也使用了辗转相除法（用了非递归求法）。

两个数的最大公约数即函数返回的值，时间复杂度为 O(\log n)。

其还有 exgcd 的用法，用于求同余方程的解，而这也是我们向初等数论进阶的重要一步。

更相减损术

1.介绍

这是一个相当冷门的求法。

这个做法最早来自《九章算术》，原文是：

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

译文：

（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

步骤：

  1. 任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

  2. 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

实例：求 260 和 104 的最大公约数。

此时 65 是奇数而 26 不是奇数，故把 65 和 26 辗转相减：
65-26=39
39-26=13
26-13=13
所以，260 与 104 的最大公约数等于 13 乘以第一步中约掉的两个 2，即 13*2*2=52。

2.代码

int gengxiangjiansunshu(int a, int b) {
    int cnt = 0;
    while (!(a & 1) && !(b & 1)) {//"可半者半之"
        a >>= 1, b >>= 1;
        cnt++;
    }
    while (a != b)//"不可半者，副置分母、子之数，以少减多，更相减损，求其等也"
        if (a > b)
            a -= b;
        else if (b > a)
            b -= a;
    return cnt ? a * (1 << cnt) : a;
}

或

int gengxiangjiansunshu(int a, int b) {
    int cnt = 0;
    while (!(a & 1) && !(b & 1)) {
        a >>= 1, b >>= 1;
        cnt++;
    }
    while (a != b) {
        if (a > b)
            a -= b;
        else if (b > a)
            b -= a;
        while (!(a & 1))    a >>= 1;
        while (!(b & 1))    b >>= 1;
    }
    return cnt ? a * (1 << cnt) : a;
}

与辗转相除法一样，函数返回值即为两个数的最大公约数。

由于只会进行 \log 次减法，所以复杂度仍为 O(\log n)。

再推荐几道题吧。

B3736 P1029 P9391 P1372 P2118 P4057 P4549

还有自己改编的一道：U309031