#sx002. 辗转相除法(欧几里得算法)

辗转相除法(欧几里得算法)

辗转相除法(欧几里得算法)

题目描述

​ 给定两个正整数 a 和 b,请使用辗转相除法(欧几里得算法) 计算它们的最大公约数(GCD,Greatest Common Divisor)。

算法概念

​ 辗转相除法,又称欧几里得算法(Euclidean Algorithm),是用于计算两个正整数最大公约数的一种经典算法。其核心思想基于一个数学原理:对于任意两个正整数 a 和 b(a ≥ b),有 gcd(a, b) = gcd(b, a mod b)。通过反复将较大数替换为较小数,较小数替换为余数,直到余数为 0,此时的除数即为最大公约数。

算法原理与步骤

  1. 输入两个正整数 a 和 b(通常约定 a ≥ b,但算法本身对输入顺序无严格要求)。
  2. 计算 a 除以 b 的余数 r = a % b。
  3. 若 r = 0,则 b 即为 a 和 b 的最大公约数,算法结束。
  4. 若 r ≠ 0,则将 b 作为新的 a,将 r 作为新的 b,重复步骤 2 和 3。
  5. 递归实现时,函数 gcd(a, b) 的返回逻辑为:若 a % b == 0,返回 b;否则返回 gcd(b, a % b)。

​ 举例:计算 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

​ 此时余数为 0,最后的除数为 1,因此最大公约数为 1。

输入格式

​ 一行两个正整数 a 和 b,用空格隔开。

输出格式

​ 一行一个整数,表示 a 和 b 的最大公约数。

输入输出样例

48 18
6

数据规模与约定

​ 1 ≤ a, b ≤ 10^9

​ 时间限制:1 秒(辗转相除法递归深度不超过 O(log min(a, b)),通常不超过 50 层,完全满足)

提示

​ 代码提示:

// 递归计算最大公约数
int gcd(int a, int b) {
    // TODO: 如果 a % b == 0,返回 b
    // 提示:递归终止条件

    // TODO: 否则递归调用 gcd(b, a % b)
    // 提示:return gcd(b, a % b)
}

int main() {
    // 注意:若 a < b,gcd 函数内部第一次递归会交换顺序,因此无需额外处理
    cout << gcd(a, b) << endl;
}

​ 运用提示:

​ 辗转相除法是求最大公约数最高效的方法之一,时间复杂度为 O(log min(a, b))。

​ 递归实现中,需要确保递归终止条件正确,避免无限递归。当 a % b == 0 时,b 即为最大公约数。

​ 若 a < b,函数首次调用会执行 gcd(a, b) = gcd(b, a % b),相当于自动交换了顺序,因此不需要在调用前额外判断大小。

​ 扩展知识:两个正整数的最小公倍数(LCM,Least Common Multiple)与最大公约数之间存在关系:LCM(a, b) = a × b ÷ GCD(a, b)。可以通过最大公约数快速计算最小公倍数。