最大公约数 (GCD) 与最小公倍数 (LCM) 的 C++ 实现

实际工程中推荐迭代版，因为递归层数过深可能导致栈溢出。

2. 更相减损术

源自《九章算术》，原理是用大数减小数，直到两数相等。虽然古老，但在某些特定场景（如位运算优化）下仍有价值。

#include <iostream>
using namespace std;

int gcd_subtraction(int a, int b) {
    // 确保 a >= b，简化逻辑
    if (a < b) swap(a, b);
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

注意：对于数值差异巨大的情况，减法效率远低于取模运算。

3. 其他方法

• 分解质因数：将两数分解为质因子乘积，取公共部分相乘。适合小数据量教学。
• 穷举法：从 min(a,b) 向下遍历，找到第一个能同时整除两者的数。简单但效率低，不推荐用于大数。

实战应用：等差数列求项数

一道经典的算法题：已知 N 个整数，求包含这些数的最短等差数列有多少项。

思路分析：

1. 将数组排序。
2. 计算相邻元素的差值。
3. 所有差值的最大公约数即为该等差数列的公差 d。
4. 若公差为 0（所有数相同），项数即为 N；否则项数为 (max - min) / d + 1。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int n;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i];

    // 特殊情况：只有两个数，必然构成等差数列
    if (n == 2) {
        cout << 2 << endl;
        return 0;
    }

    sort(vec.begin(), vec.end());

    // 计算相邻差值
    vector<int> dif(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        dif[i] = vec[i + 1] - vec[i];
    }

    // 求所有差值的 GCD
    int d = dif[0];
    for (size_t i = 1; i < dif.size(); ++i) {
        d = gcd(d, dif[i]);
    }

    // 处理公差为 0 的情况（所有数字相同）
    if (d == 0) {
        cout << n << endl;
    } else {
        // 项数 = (末项 - 首项) / 公差 + 1
        cout << (vec[n - 1] - vec[0]) / d + 1 << endl;
    }

    return 0;
}

总结

学习算法时，直接看代码往往难以理解其本质。建议先掌握数学原理（如欧几里得算法的几何意义或代数性质），再编写代码，这样记忆更牢固。在实际开发中，C++ 标准库 <numeric> 提供了 std::gcd 和 std::lcm（C++17 起），可直接调用，但手写实现有助于应对面试或底层优化需求。