C++计算最大公约数（GCD）

欧几里得算法（辗转相除法）

欧几里得算法基于以下数学原理：两个数的最大公约数等于其中较小数与两数相除余数的最大公约数。递归或循环实现均可。

递归实现代码

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

• 终止条件：当 b 为0时，a 即为GCD。
• 递归步骤：将 b 和 a % b 作为新参数传入。

迭代实现代码

int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

• 通过循环不断更新 a 和 b 的值，直到余数为0。

更相减损法（优化版）

适用于大数运算，避免取模运算的开销，但迭代次数可能增多。

int gcd_subtraction(int a, int b) {
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

• 通过不断相减缩小数值，直到两数相等。

标准库实现（C++17及以上）

C++17引入了 <numeric> 头文件中的 std::gcd，需确保编译器支持。

#include <numeric>
#include <iostream>

int main() {
    std::cout << std::gcd(48, 18); // 输出6
    return 0;
}

处理负数和零

上述代码默认处理正整数，若需支持负数或零，可添加绝对值处理：

int gcd_abs(int a, int b) {
    a = abs(a);
    b = abs(b);
    if (a == 0) return b;
    if (b == 0) return a;
    return gcd_iterative(a, b);
}

性能注意事项

避免递归实现
递归调用可能导致栈溢出，尤其处理大数时。迭代方法（如欧几里得算法）通常更高效且安全。示例迭代实现：

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

利用内置函数
现代编译器（如GCC、Clang）提供__gcd内建函数，可能使用特定指令集优化。例如：

#include <algorithm>
int gcd = std::__gcd(a, b); // 需注意非标准库函数

处理负数和零
提前处理特殊情况避免额外计算：

int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    if (a == 0) return b;
    if (b == 0) return a;
    // 继续欧几里得算法
}

数学优化

二进制GCD算法（Stein算法）
适合硬件位操作优化，减少模运算开销：

int binary_gcd(int u, int v) {
    if (u == 0) return v;
    if (v == 0) return u;
    int shift = __builtin_ctz(u | v);
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if (u > v) std::swap(u, v);
        v -= u;
    } while (v != 0);
    return u << shift;
}

预计算小数值
高频调用时可缓存常用数对的结果，以空间换时间。

硬件相关优化

使用SIMD指令
如AVX2指令集可并行计算多个GCD，但需特定场景：

#include <immintrin.h>
// 示例：需根据具体指令集实现

编译器优化标志
启用-O3或-march=native允许编译器使用特定CPU指令优化算术运算。

算法选择依据

• 小整数：欧几里得算法足够高效。
• 大整数或频繁调用：二进制GCD或内置函数更优。
• 批处理：考虑SIMD并行化。### 性能注意事项

避免递归实现
递归调用可能导致栈溢出，尤其处理大数时。迭代方法（如欧几里得算法）通常更高效且安全。示例迭代实现：

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

性能优化

利用内置函数
现代编译器（如GCC、Clang）提供__gcd内建函数，可能使用特定指令集优化。例如：

#include <algorithm>
int gcd = std::__gcd(a, b); // 需注意非标准库函数

处理负数和零
提前处理特殊情况避免额外计算：

int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    if (a == 0) return b;
    if (b == 0) return a;
    // 继续欧几里得算法
}

数学优化

二进制GCD算法（Stein算法）
适合硬件位操作优化，减少模运算开销：

int binary_gcd(int u, int v) {
    if (u == 0) return v;
    if (v == 0) return u;
    int shift = __builtin_ctz(u | v);
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if (u > v) std::swap(u, v);
        v -= u;
    } while (v != 0);
    return u << shift;
}

预计算小数值
高频调用时可缓存常用数对的结果，以空间换时间。

硬件相关优化

使用SIMD指令
如AVX2指令集可并行计算多个GCD，但需特定场景：

#include <immintrin.h>
// 示例：需根据具体指令集实现

编译器优化标志
启用-O3或-march=native允许编译器使用特定CPU指令优化算术运算。