Hexo
0%

最大公约数

Posted on In ,
Symbols count in article: 909 Reading time ≈ 1 mins.

最大公约数

欧几里得算法

求出a和b的最大公约数

1
2
3
4
5
6
7
8
int gcd(int a, int b) {
  while (b != 0) {
    int tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

更相减损术

大整数取模的时间复杂度较高，而加减法时间复杂度较低。针对大整数，我们可以用加减代替乘除求出最大公约数。

$gcd(a,b)\ = \ gcd(a-b,b)$

多个数的最大公约数

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

最小公倍数

两个数

$gcd(a,b)\ \times lcm(a,b)\ = \ a \times b$

多个数

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

扩展欧几里得算法

常用于求$ax\ +\ by\ =\ gcd(a,b)$​ 的一组可行解

递归求法

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
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;
}