C++---辗转相除法

辗转相除法（又称欧几里得算法）是计算两个整数最大公约数（Greatest Common Divisor, GCD）的经典算法。其核心思想基于“两个数的最大公约数等于其中较小数与两数相除余数的最大公约数”，通过反复迭代简化问题，最终得到结果。

gcd(a,b) == gcd(b,a%b)，a>b

一、辗转相除法的核心原理

1. 数学基础

对于任意两个正整数 a 和 b（假设 a ≥ b），设 a 除以 b 的商为 q，余数为 r（即 a = b×q + r，其中 0 ≤ r < b），则有：
gcd(a, b) = gcd(b, r)
当 r = 0 时，b 即为 a 和 b 的最大公约数。

2. 迭代过程示例

以 a = 48、b = 18 为例，步骤如下：

• 第1次迭代：48 ÷ 18 = 2 余 12 → gcd(48, 18) = gcd(18, 12)
• 第2次迭代：18 ÷ 12 = 1 余 6 → gcd(18, 12) = gcd(12, 6)
• 第3次迭代：12 ÷ 6 = 2 余 0 → 余数为0，此时 6 即为最大公约数。

二、C++基本实现方式

1. 递归实现

利用递归的自调用特性，直接体现辗转相除法的数学定义：

#include <iostream>
using namespace std;// 递归版本：计算a和b的最大公约数（a、b为非负整数）
int gcd(int a, int b) {a = max(a,b);b = min(a,b);// 边界条件：若b为0，返回a（此时a即为最大公约数）if (b == 0) {return a;}// 递归调用：gcd(a, b) = gcd(b, a % b)return gcd(b, a % b);
}int main() {int a = 48, b = 18;cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << endl; // 输出6return 0;
}

2. 迭代实现

通过循环替代递归，避免递归调用的栈开销，更适合处理大数值：

#include <iostream>
using namespace std;// 迭代版本：计算a和b的最大公约数
int gcd(int a, int b) {a = max(a,b);b = min(a,b);// 循环直到b为0，此时a即为结果while (b != 0) {int temp = b;       // 保存当前b的值b = a % b;          // 计算新的余数（下次迭代的b）a = temp;           // 更新a为上次的b}return a;
}int main() {int a = 100, b = 35;cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << endl; // 输出5return 0;
}

三、关键细节与优化

1. 处理非正整数的情况

上述实现默认输入为非负整数，若输入包含负数，需先取绝对值（因 gcd(a, b) = gcd(|a|, |b|)）：

int gcd(int a, int b) {a = abs(a);  // 取绝对值，支持负数输入b = abs(b);while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}

2. 性能分析：为何高效？

辗转相除法的时间复杂度为 O(log(min(a, b)))，远优于枚举法（O(min(a, b))）。原因是每次迭代后，余数 r 至少比除数 b 小一半（数学证明：若 a ≥ b，则 a % b < b/2），因此迭代次数随数值增长呈对数级增加。

例如，计算 gcd(10⁶, 1) 仅需1次迭代，而 gcd(10⁶, 10⁶-1) 也只需约20次迭代。

3. 与“更相减损术”的对比

中国古代的“更相减损术”原理为 gcd(a, b) = gcd(a-b, b)（a > b），但效率低于辗转相除法。例如计算 gcd(1000000, 1) 时，更相减损术需迭代999999次，而辗转相除法仅需1次。

四、扩展应用

1. 计算最小公倍数（LCM）

利用公式 lcm(a, b) = |a × b| / gcd(a, b)，可通过辗转相除法间接求最小公倍数：

int lcm(int a, int b) {if (a == 0 || b == 0) {return 0;  // 0与任何数的LCM为0}return abs(a * b) / gcd(a, b);
}

注意：计算 a × b 可能溢出（如 a 和 b 接近 INT_MAX 时），优化写法为 abs(a) / gcd(a, b) * abs(b)（先除后乘，减少溢出风险）。

2. 处理大数：使用long long类型

当输入数值超过 int 范围（如 10⁹ 以上），需用 long long 避免溢出：

long long gcd(long long a, long long b) {a = abs(a);b = abs(b);while (b != 0) {long long temp = b;b = a % b;a = temp;}return a;
}

3. C++17标准库中的std::gcd

C++17在 <numeric> 头文件中内置了 std::gcd 函数，可直接调用（需编译器支持C++17及以上标准）：

#include <iostream>
#include <numeric>  // 包含std::gcd
using namespace std;int main() {int a = 48, b = 18;cout << "gcd = " << gcd(a, b) << endl; // 输出6return 0;
}

注意：std::gcd 要求输入为非负整数，且至少有一个不为0，否则行为未定义。

五、常见错误与避坑指南

1. 忽略负数处理：若直接传入负数，a % b 结果可能为负（C++中负数取余结果的符号与被除数一致），导致迭代异常。例如 gcd(-48, 18) 需先取绝对值。
2. 溢出风险：计算 a × b 求LCM时，即使 a 和 b 为 int 类型，乘积也可能超过 int 范围，建议用 long long 中转。
3. 递归栈溢出：递归实现虽简洁，但对于极端大数值（如 10¹⁸）可能触发栈溢出，优先选择迭代实现。

---

辗转相除法是C++中计算最大公约数的高效算法，其核心是通过反复求余简化问题，时间复杂度为对数级。实际开发中，需注意处理负数、避免溢出，并根据场景选择递归或迭代实现。对于C++17及以上环境，std::gcd 提供了标准实现，可直接使用。掌握辗转相除法不仅能解决GCD/LCM问题，还能为理解更复杂的数论算法（如模运算、素数判定）奠定基础。