最大公约数算法：从数学原理到C++工程实践

1. 最大公约数问题背景

在数学和编程领域，求两个数的最大公约数（Greatest Common Divisor，简称GCD）是一个基础但重要的问题。GCD在分数化简、密码学算法、时间调度等场景都有广泛应用。比如在RSA加密算法中就需要频繁计算两个大数的GCD。

我最早接触这个问题是在大学的数据结构课上，当时老师给出了暴力枚举法：从较小的数开始逐个尝试，直到找到能同时整除两个数的最大值。这种方法虽然直观，但当处理大数时效率极低。后来在算法课上学习了更高效的辗转相除法（又称欧几里得算法），其时间复杂度仅为O(log min(a,b))。

2. 辗转相除法原理剖析

2.1 数学基础证明

辗转相除法基于一个核心数学原理：gcd(a,b) = gcd(b, a mod b)。这个定理的证明其实非常优雅：

1. 设d是a和b的公约数，则d|a且d|b
2. 根据模运算定义，a = kb + r（其中r = a mod b）
3. 因此r = a - kb，由于d能整除a和b，必然也能整除r
4. 所以d也是b和r的公约数
5. 反之亦然，因此两者的公约数集合完全相同

这个性质使得我们可以将大数问题不断递归转化为更小的数对，直到其中一个数为0时，另一个数就是所求的GCD。

2.2 算法流程详解

标准辗转相除法的执行步骤：

1. 输入两个正整数a和b（假设a > b）
2. 计算a除以b的余数r = a % b
3. 如果r == 0，则b就是GCD
4. 否则令a = b，b = r，重复步骤2-3

以计算gcd(48, 18)为例：

• 48 ÷ 18 = 2余12 → gcd(18,12)
• 18 ÷ 12 = 1余6 → gcd(12,6)
• 12 ÷ 6 = 2余0 → 得到GCD=6

3. C++实现方案

3.1 递归版本实现

cpp复制int gcd_recursive(int a, int b) {
    if (b == 0) 
        return a;
    return gcd_recursive(b, a % b);
}

这个版本最直观地反映了算法定义，但需要注意：

• 递归深度会影响栈空间使用
• 默认要求第一个参数大于第二个参数
• 对负数输入需要先