共计 2147 个字符，预计需要花费 6 分钟才能阅读完成。

引言：无处不在的 GCD 与 LCM 问题

在 LeetCode 1979 题中，我们需要找到数组所有元素的最大公约数；在 RSA 加密算法里，互质判断依赖 GCD 计算；而在调度系统中，周期任务的时间片分配又涉及 LCM 运算。本文将从欧几里得算法出发，带你掌握工业级 GCD/LCM 实现技巧。

一、算法原理与时间复杂度对比

1.1 暴力枚举法

最直观的做法是遍历所有可能的公约数：

• 实现思路 ：从 min(a,b) 开始递减检查
• 时间复杂度：$O(min(a,b))$
• 缺点：当 a =1e9, b= 1 时浪费严重

def gcd_naive(a, b):
    for i in range(min(abs(a), abs(b)), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

1.2 欧几里得算法

基于数学定理：$gcd(a,b) = gcd(b, a\ mod\ b)$

• 递归实现：

  def gcd_euclid(a, b):
      return a if b == 0 else gcd_euclid(b, a % b)

• 迭代实现：

  int gcd_iter(int a, int b) {while (b != 0) {
          int temp = b;
          b = a % b;
          a = temp;
      }
      return abs(a); // 保证结果为正
  }

• 时间复杂度：$O(\log(min(a,b)))$

二、多语言实现方案

2.1 Python 标准库方案

import math

def compute_gcd_lcm():
    try:
        a = int(input("Enter first number:"))
        b = int(input("Enter second number:"))

        if a == 0 or b == 0:
            raise ValueError("Input cannot be zero")

        gcd = math.gcd(a, b)
        lcm = abs(a * b) // gcd

        print(f"GCD: {gcd}, LCM: {lcm}")
    except ValueError as e:
        print(f"Invalid input: {e}")

2.2 C++ 工业级实现

#include <iostream>
#include <cstdlib>
#include <climits>

constexpr int64_t safe_multiply(int64_t a, int64_t b) {if (a > INT64_MAX / b) throw std::overflow_error("Multiplication overflow");
    return a * b;
}

int64_t gcd(int64_t a, int64_t b) noexcept {while (b != 0) {
        int64_t t = b;
        b = a % b;
        a = t;
    }
    return llabs(a);
}

int main() {
    try {
        int64_t a, b;
        std::cout << "Enter two integers:";

        if (!(std::cin >> a >> b) || a == 0 || b == 0) {throw std::invalid_argument("Input must be non-zero integers");
        }

        int64_t gcd_val = gcd(a, b);
        int64_t lcm_val = llabs(safe_multiply(a, b)) / gcd_val;

        std::cout << "GCD:" << gcd_val 
                  << "\nLCM:" << lcm_val << std::endl;
    } catch (const std::exception& e) {std::cerr << "Error:" << e.what() << std::endl;
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

三、高级优化技巧

3.1 Stein 算法（二进制 GCD）

利用位运算加速：

def gcd_binary(a, b):
    if a == 0: return abs(b)
    if b == 0: return abs(a)

    shift = 0
    while ((a | b) & 1) == 0:
        a >>= 1
        b >>= 1
        shift += 1

    while (a & 1) == 0:
        a >>= 1

    while b != 0:
        while (b & 1) == 0:
            b >>= 1
        if a > b:
            a, b = b, a
        b -= a

    return a << shift

3.2 LCM 的快速计算

利用数学恒等式：
$$
LCM(a,b) = \frac{|a \times b|}{GCD(a,b)}
$$

注意先做除法防溢出：

int64_t safe_lcm(int64_t a, int64_t b) {int64_t g = gcd(a, b);
    return (a / g) * b;  // 先除后乘
}

四、生产环境注意事项

1. 整数溢出：
2. Python 默认支持大整数

3. C++ 需使用 int64_t 并检查乘法溢出

4. 线程安全：

5. 纯函数无状态，可多线程调用

6. 避免使用静态变量存储中间结果

7. 异常处理：

8. 校验输入范围
9. 处理零值特殊情况

五、进阶思考方向

1. 扩展多个数的 GCD：

   def multi_gcd(numbers):
       return reduce(math.gcd, numbers)

2. 分布式 GCD 计算：

3. Map 阶段：计算各分片数据的 GCD

4. Reduce 阶段：合并分片结果

5. GPU 并行优化：

6. 使用 CUDA 实现 SIMD 版本的 Stein 算法

结语

从欧几里得的几何原本到现代密码学，高效的 GCD 算法始终焕发活力。建议读者在理解基本原理后，尝试实现文中的各种优化方案，并思考如何将其应用到实际工程场景中。