17370845950

C++17起可用std::gcd，需包含且参数非负；否则可用递归、迭代欧几里得或二进制GCD算法，注意绝对值处理与边界条件。

std::gcd 是 C

++17 标准库提供的现成函数

如果你用的是 C++17 或更高版本，std::gcd 已经直接可用，无需手写。它定义在 头文件中，接受两个整数（要求为有符号或无符号整型），返回其最大公约数。

注意：参数必须同类型，且不能为负数（行为未定义）；实际使用前建议取绝对值：

int a = -48, b = 18;
int result = std::gcd(std::abs(a), std::abs(b)); // 返回 6

常见坑点：

• std::gcd(0, 0) 抛出 std::domain_error
• 传入负数不保证结果正确，标准只要求对非负整数有定义
• GCC 9+、Clang 7+、MSVC 2019 16.10+ 支持；旧编译器需自行实现

欧几里得算法（递归版）最直观易懂

这是最经典的 GCD 实现，基于 a % b == 0 ? b : gcd(b, a % b) 的数学性质。适合教学和快速手写验证。

关键细节：

• 必须处理 b == 0 的边界，否则栈溢出
• 推荐统一用 long long 防止中间取模时溢出（尤其输入是 int 但乘积大）
• 递归深度一般很小（O(log min(a,b))），但极端情况（如斐波那契相邻数）仍可能触发栈限制

long long gcd_recursive(long long a, long long b) {
    if (b == 0) return std::abs(a);
    return gcd_recursive(b, a % b);
}

欧几里得算法（迭代版）更安全高效

生产环境优先选这个——无函数调用开销，无栈溢出风险，且逻辑清晰可控。

典型错误写法是忽略符号处理或漏掉最后一步赋值：

• 别直接用 a % b 而不先取绝对值，负数取模在 C++ 中向零截断，可能导致循环不收敛
• 循环条件应为 b != 0，不是 a != 0
• 每次更新必须是 std::tie(a, b) = std::make_tuple(b, a % b) 或分步赋值，顺序不能错

long long gcd_iterative(long long a, long long b) {
    a = std::abs(a);
    b = std::abs(b);
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

二进制 GCD（Stein 算法）适合无除法场景

当目标平台不支持高效取模（比如某些嵌入式芯片或汇编优化场景），可以用只依赖位运算的 Stein 算法。它避免了 % 和 /，全部用 &、^、>> 实现。

核心逻辑是利用：
– 若 a、b 均为偶数，则 gcd(a,b) = 2 * gcd(a/2, b/2)
– 若 a 偶 b 奇，则 gcd(a,b) = gcd(a/2, b)
– 若 a 奇 b 奇，则 gcd(a,b) = gcd(|a−b|/2, min(a,b))

容易被忽略的点：

• 必须预处理符号（只对正数操作）
• |a−b|/2 要写成 (a > b ? a - b : b - a) >> 1，不能直接 abs(a-b)>>1（避免溢出）
• 需要记录公共因子 2 的次数，最后乘回去

实际项目中除非明确受限于硬件指令集，否则没必要替换为该版本。