#sx002. 辗转相除法(欧几里得算法)
辗转相除法(欧几里得算法)
辗转相除法(欧几里得算法)
题目描述
给定两个正整数 a 和 b,请使用辗转相除法(欧几里得算法) 计算它们的最大公约数(GCD,Greatest Common Divisor)。
算法概念
辗转相除法,又称欧几里得算法(Euclidean Algorithm),是用于计算两个正整数最大公约数的一种经典算法。其核心思想基于一个数学原理:对于任意两个正整数 a 和 b(a ≥ b),有 gcd(a, b) = gcd(b, a mod b)。通过反复将较大数替换为较小数,较小数替换为余数,直到余数为 0,此时的除数即为最大公约数。
算法原理与步骤
- 输入两个正整数 a 和 b(通常约定 a ≥ b,但算法本身对输入顺序无严格要求)。
- 计算 a 除以 b 的余数 r = a % b。
- 若 r = 0,则 b 即为 a 和 b 的最大公约数,算法结束。
- 若 r ≠ 0,则将 b 作为新的 a,将 r 作为新的 b,重复步骤 2 和 3。
- 递归实现时,函数 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)。可以通过最大公约数快速计算最小公倍数。