

最大公约数

最大公约数¶

最大公约数即为 Greatest Common Divisor，常缩写为 gcd。

一组整数的公约数，是指同时是这组数中每一个数的约数的数。是任意一组整数的公约数。

一组整数的最大公约数，是指所有公约数里面最大的一个。

那么如何求最大公约数呢？我们先考虑两个数的情况。

欧几里得算法¶

如果我们已知两个数和，如何求出二者的最大公约数呢？

不妨设

我们发现如果是的约数，那么就是二者的最大公约数。下面讨论不能整除的情况，即，其中。

我们通过证明可以得到，过程如下：

设，显然有。设，则。

由右边的式子可知为整数，即所以对于的公约数，它也会是的公约数。

反过来也需要证明：

设，我们还是可以像之前一样得到以下式子。

因为左边式子显然为整数，所以也为整数，即，所以的公约数也是的公约数。

既然两式公约数都是相同的，那么最大公约数也会相同。

所以得到式子

既然得到了，这里两个数的大小是不会增大的，那么我们也就得到了关于两个数的最大公约数的一个递归求法。

// C++ Version
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

# Python Version
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

递归至 b==0（即上一步的 a%b==0) 的情况再返回值即可。

上述算法被称作欧几里得算法（Euclidean algorithm）。

如果两个数和满足，我们称和互质。

欧几里得算法的时间效率如何呢？下面我们证明，欧几里得算法的时间复杂度为。

当我们求的时候，会遇到两种情况：

，这时候；
，这时候，而对取模会让至少折半。这意味着这一过程最多发生次。

第一种情况发生后一定会发生第二种情况，因此第一种情况的发生次数一定 不多于 第二种情况的发生次数。

从而我们最多递归次就可以得出结果。

事实上，假如我们试着用欧几里得算法去求斐波那契数列相邻两项的最大公约数，会让该算法达到最坏复杂度。

多个数的最大公约数¶

那怎么求多个数的最大公约数呢？显然答案一定是每个数的约数，那么也一定是每相邻两个数的约数。我们采用归纳法，可以证明，每次取出两个数求出答案后再放回去，不会对所需要的答案造成影响。

最小公倍数¶

接下来我们介绍如何求解最小公倍数（Least Common Multiple, LCM）。

一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。0 是任意一组整数的公倍数。

一组整数的最小公倍数，是指所有正的公倍数里面，最小的一个数。

两个数的¶

设，

我们发现，对于和的情况，二者的最大公约数等于

最小公倍数等于

由于

所以得到结论是

要求两个数的最小公倍数，先求出最大公约数即可。

多个数的¶

可以发现，当我们求出两个数的时，求最小公倍数是的复杂度。那么对于多个数，我们其实没有必要求一个共同的最大公约数再去处理，最直接的方法就是，当我们算出两个数的，或许在求多个数的时候，我们将它放入序列对后面的数继续求解，那么，我们转换一下，直接将最小公倍数放入序列即可。

扩展欧几里得算法¶

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求的一组可行解。

证明¶

设

由欧几里得定理可知：

所以

又因为

所以

因为，所以

将不断代入递归求解直至（最大公约数，下同）为 0 递归 x=1,y=0 回去求解。

// C++ Version
int Exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int d = Exgcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}

# Python Version
def Exgcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = Exgcd(b, a % b)
    return d, y, x - (a // b) * y

函数返回的值为，在这个过程中计算即可。

迭代法编写拓展欧几里得算法¶

因为迭代的方法避免了递归，所以代码运行速度将比递归代码快一点。

int gcd(int a, int b, int& x, int& y) {
  x = 1, y = 0;
  int x1 = 0, y1 = 1, a1 = a, b1 = b;
  while (b1) {
    int q = a1 / b1;
    tie(x, x1) = make_tuple(x1, x - q * x1);
    tie(y, y1) = make_tuple(y1, y - q * y1);
    tie(a1, b1) = make_tuple(b1, a1 - q * b1);
  }
  return a1;
}

如果你仔细观察和，你会发现，他们在迭代版本的欧几里德算法中取值完全相同，并且以下公式无论何时（在 while 循环之前和每次迭代结束时）都是成立的：和。因此，该算法肯定能正确计算出。

最后我们知道就是要求的，有。

矩阵的解释¶

对于正整数和的一次辗转相除即使用矩阵表示如

其中向下取整符号表示不大于的最大整数。我们定义变换。

易发现欧几里得算法即不停应用该变换，有

令

那么

满足即扩展欧几里得算法，注意在最后乘了一个单位矩阵不会影响结果，提示我们可以在开始时维护一个的单位矩阵编写更简洁的迭代方法如

int exgcd(int a, int b, int &x, int &y) {
  int x1 = 1, x2 = 0, x3 = 0, x4 = 1;
  while (b != 0) {
    int c = a / b;
    std::tie(x1, x2, x3, x4, a, b) =
        std::make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c);
  }
  x = x1, y = x2;
  return a;
}

这种表述相较于递归更简单。

应用¶

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

最大公约数