欧几里得算法

Posted on | Post modified:
Words count in article: 181 | Reading time ≈ 1

任务

求两个数 a, b的最大公约数gcd(a, b)

说明

由贝祖定理得，gcd(a, b) = gcd(b, a-b),其中a>=b。通过这样不断的迭代，直到 b = 0,a 就是原来数对的最大公约数。考虑到只使用减法会超时，我们观察到如果a -b仍大于b的话，要进行一次同样的操作就把a减到不足b为止，所以有gcd(a, b) = gcd(b, a mod b)。

接口

  • int gcd(int a, int b);
  • 复杂度：O(logN), 其中N和a, b同阶。
  • 输入：a, b两个整数
  • 输出：a, b的最大公约数

代码

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

有问题？发送 issues 给我~

0%