在编写算法题或者处理分数化简、比例计算时，求两个整数的最大公约数（Greatest Common Divisor，简称GCD）几乎是绕不开的基础操作。很多初学者会直接用循环从较小数开始向下试探，找到第一个能同时整除两个数的值就返回，这种方法虽然直观，但当输入达到10^9量级时，最坏情况需要循环数亿次，效率完全无法接受。其实早在两千多年前，欧几里得就在《几何原本》中给出了一个优雅的解法——辗转相除法，它的核心思想建立在“两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数”这一性质之上。本文将围绕C++语言，从原理推导、代码实现、边界处理到性能对比，完整梳理求最大公约数的各种方案。
辗转相除法的数学原理与正确性证明
假设有两个正整数a和b，且a大于等于b。用a除以b得到商q和余数r，可以写成a = bq + r，其中0 ≤ r < b。此时gcd(a, b)与gcd(b, r)相等。为什么？设d是a和b的任意公约数，那么d能整除a和b，于是d也能整除a - bq，即d整除r，所以d是b和r的公约数。反过来，如果e是b和r的公约数，那么e整除b和r，也就整除bq + r = a，所以e也是a和b的公约数。因此a、b的公约数集合与b、r的公约数集合完全相同，最大公约数自然相等。反复应用这个规则，每轮将较大的数替换为余数，余数严格递减且非负，最终必然会在有限步内出现余数为0的情况。当余数为0时，上一轮的除数就是最大公约数。例如求gcd(1071, 462)：1071 = 462×2 + 147，462 = 147×3 + 21，147 = 21×7 + 0，所以gcd为21。整个过程只涉及取模运算，无需因式分解，时间复杂度为O(log min(a,b))。
更相减损术也是中国古代的一种求最大公约数方法，其规则是“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也”。比如求gcd(98, 63)，因为都是奇数不可半，就用大数减小数：98-63=35，63-35=28，35-28=7，28-7=21，21-7=14，14-7=7，最终得到7。这个方法本质上是辗转相除法的减法版本，当两数差距很大时，减法需要执行的次数远多于取模，例如a=10^9、b=1时，辗转相除法一次取模就结束，而更相减损术需要执行10^9次减法。因此在实际编程中，除非环境不支持取模运算，否则优先使用辗转相除法。
C++中辗转相除法的递归与迭代实现
递归版本的实现非常简洁，直接对应数学定义。函数接收两个整数参数，基准条件是当第二个数为0时返回第一个数；否则递归调用自身，参数为第二个数和第一个数对第二个数取模的结果。需要特别注意，递归深度在最坏情况下与输入的对数相关，对于int范围内的数，递归深度不超过50层，完全不会栈溢出。但如果传入的是非常大的自定义大整数类型，递归深度依然可控，因为每次至少减半。下面给出递归代码：
// 递归版辗转相除法，假设a和b都是非负整数
int gcd_recursive(int a, int b) {
if (b == 0) {
return a;
}
return gcd_recursive(b, a % b);
}
迭代版本则是用while循环不断更新两个变量，直到余数为零。迭代实现避免了函数调用开销，在追求极致性能的场合（例如数百万次调用）可能比递归略快，但现代编译器对尾递归有优化，实际差异很小。迭代写法如下：
// 迭代版辗转相除法，同样假设a和b都是非负整数
int gcd_iterative(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
无论递归还是迭代，都需要处理输入为0的情况。如果a=0且b=0，按照数学定义gcd(0,0)没有意义，但实际编程中为了鲁棒性，通常约定返回0。如果仅有一个数为0，例如a=0, b=5，那么gcd(0,5)应返回5。仔细观察上述代码：递归版本当b=0时返回a，如果a=0则返回0；迭代版本循环结束返回a，也能正确处理。但是对于负数输入，取模运算的结果符号在不同编译器下可能不同。C++11之前，负数取模是实现定义的；C++11之后规定余数的符号与被除数相同。例如-15 % 6的结果可能是-3（C++11后），这会导致gcd计算出现负值。正确做法是先将输入转为绝对值，或者对结果取绝对值。更优雅的方式是使用std::abs，但要注意INT_MIN的绝对值会溢出。工程中一般建议对输入做非负约束，或者使用long long类型。
边界处理、性能优化与标准库函数
如果只处理正整数，辗转相除法已经足够高效。但竞赛和实际应用中经常出现负数、大整数，甚至需要一次性求多个数的最大公约数。对于负数，可以先取绝对值：int gcd(int a, int b) { if (a < 0) a = -a; if (b < 0) b = -b; return gcd_recursive(a,b); }。但针对INT_MIN取绝对值会溢出，因为int范围是-2147483648到2147483647，-(-2147483648)超出上限。解决方法是把参数类型改为long long，或者使用无符号类型。对于大整数场景，比如需要计算10^18级别的两个数的GCD，直接使用long long即可，算法复杂度对数级，完全够用。如果需要更高精度，可以使用C++的boost库中的cpp_int，或者自己实现大整数类并重载取模运算符。
一个常见的性能误区是：对两个数先排序，确保a大于等于b再进行取模。实际上辗转相除法不需要这个前提，即使a小于b，第一轮a % b的结果就是a本身（例如gcd(3,10)会变成gcd(10,3)），效果等价于交换。因此多写一步比较交换反而可能降低性能。另一个优化方向是使用位运算加速：当两个数都是偶数时，可以先提取公因子2；当一奇一偶时，偶数可以直接折半；当两个都是奇数时，用大数减小数再继续。这就是二进制GCD算法（Stein算法），它避免了昂贵的除法取模操作，在硬件除法较慢的嵌入式设备上可能有优势。但现代x86和ARM处理器的整数除法指令已经很快，Stein算法的优势并不明显，且代码复杂容易出错，所以常规开发中直接使用辗转相除法更稳妥。
C++17标准在头文件<numeric>中引入了std::gcd函数，可以直接使用：
#include <numeric>
#include <iostream>
int main() {
int a = 1071, b = 462;
std::cout << std::gcd(a, b) << std::endl; // 输出21
// 支持负数，结果恒为正
std::cout << std::gcd(-12, 18) << std::endl; // 输出6
return 0;
}
std::gcd内部实现等同于辗转相除法，并且对负数做了规范化，返回类型与参数类型一致，但保证结果非负。如果你使用的是C++14及更早标准，可以自己封装一个模板函数，同时处理多个数：
// 自定义变参模板求多个数的最大公约数
template<typename T>
T gcd(T a, T b) {
if (a < 0) a = -a;
if (b < 0) b = -b;
while (b != 0) {
T r = a % b;
a = b;
b = r;
}
return a;
}
template<typename T, typename... Args>
T gcd(T first, Args... rest) {
return gcd(first, gcd(rest...));
}
这段代码在C++11及以上版本可以编译，能一次性求出任意多个数的最大公约数，例如gcd(24, 36, 60)会先计算gcd(36,60)=12，再计算gcd(24,12)=12。在数论问题中，这种能力非常实用。最后需要强调，虽然标准库提供了std::gcd，但理解底层辗转相除法的实现逻辑有助于应对面试手写代码、处理非标准整数类型以及在一些不允许使用C++17特性的旧平台上工作。