Great Common Divisor

最大公约数

分析

使用 **欧几里得算法（即辗转相除法）**来求两个数的最大公约数，其基本原理为：

当 b != 0 时，不断对 a % b 进行递归；
当 b == 0，说明余数为 0，返回的 a 就是最大公约数

时间复杂度

单次 gcd(a, b) 的时间复杂度为 O(log min(a, b))

所以总复杂度为 O(n * logN)，其中 N 为输入数据的最大值

空间复杂度

空间复杂度为 O(logN)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


#include <iostream>

// 欧几里得算法实现，递归方式求最大公约数
int gcd(int a, int b)
{
  return b ? gcd(b, a % b) : a; // 如果 b 不为 0，继续递归；否则返回 a
}

int main()
{
  int n;
  std::cin >> n; // 读入整数 n，表示有 n 对数字

  while (n -- )
  {
    int a, b;
    std::cin >> a >> b;         // 读入一对整数 a 和 b
    std::cout << gcd(a, b) << '\n'; // 输出这对数的最大公约数
  }

  return 0;
}