从算法到实现：用函数高效求解最大公约数与最小公倍数

1次阅读

没有评论

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

最大公约数 (GCD) 和最小公倍数 (LCM) 是基础但重要的数学概念，在计算机科学中有广泛应用。例如：

密码学：RSA 加密算法依赖大整数的 GCD 计算
数据压缩：有理数的最简分数表示需要 GCD 运算
调度算法：周期性任务的最优调度时间与 LCM 相关
图形学：屏幕像素比例化简需要 GCD 运算

时间复杂度：$O(min(a,b))$
实现方式：从较小数开始递减测试
缺点：对大数效率极低

时间复杂度：$O(\log(min(a,b)))$
数学原理：$GCD(a,b) = GCD(b, a\ mod\ b)$
优势：对数级时间复杂度

时间复杂度：$O(max(a,b))$
实现方式：反复用大数减小数
缺点：比欧几里得算法效率低

def gcd_recursive(a: int, b: int) -> int:
    """
    递归实现欧几里得算法
    时间复杂度: O(log(min(a,b)))
    """
    return a if b == 0 else gcd_recursive(b, a % b)

def gcd_iterative(a: int, b: int) -> int:
    """
    迭代实现欧几里得算法
    时间复杂度: O(log(min(a,b)))
    """
    while b:
        a, b = b, a % b
    return abs(a)  # 保证结果非负

根据数论原理：
$$LCM(a,b) = \frac{|a \times b|}{GCD(a,b)}$$

实现代码：

def lcm(a: int, b: int) -> int:
    """
    计算最小公倍数
    基于公式 LCM(a,b) = |a*b| / GCD(a,b)
    """
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // gcd_iterative(a, b)

def gcd(a: int, b: int) -> int:
    """
    计算最大公约数（带参数校验）Args:
        a: 第一个整数
        b: 第二个整数
    Returns:
        最大公约数（非负）Raises:
        TypeError: 输入不是整数时抛出
    """
    if not isinstance(a, int) or not isinstance(b, int):
        raise TypeError("参数必须是整数")

    a, b = abs(a), abs(b)  # 处理负数
    while b:
        a, b = b, a % b
    return a


def lcm(a: int, b: int) -> int:
    """
    计算最小公倍数
    Args:
        a: 第一个整数
        b: 第二个整数
    Returns:
        最小公倍数（非负）"""
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // gcd(a, b)


if __name__ == "__main__":
    # 测试用例
    print(gcd(48, 18))  # 输出: 6
    print(lcm(48, 18))  # 输出: 144
    print(gcd(0, 5))    # 输出: 5
    print(lcm(0, 5))    # 输出: 0

(0, 0)情况：
GCD 数学定义未定义，代码返回 0
LCM 应返回 0
大整数情况：
处理 $2^{63}-1$ 等大数时，确保不会整数溢出
Python 原生支持大整数，但其他语言需要注意
负数输入：
GCD 结果应为正数
LCM 结果应为非负

利用位运算加速：

def gcd_stein(a: int, b: int) -> int:
    """
    Stein 算法实现 GCD
    使用位运算加速
    """
    if a == 0:
        return b
    if b == 0:
        return a

    # 提取公共的 2 的幂
    shift = 0
    while ((a | b) & 1) == 0:
        a >>= 1
        b >>= 1
        shift += 1

    # 确保 a 是奇数
    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

忽略整数溢出：
在 C /Java 等语言中，a* b 可能导致溢出
应先计算 GCD，再除法
错误处理非整数输入：
使用 isinstance 检查类型
提前处理浮点数等非法输入
负数处理不当：
GCD 结果应始终为正
在计算前取绝对值

GCD 扩展：$GCD(a,b,c) = GCD(GCD(a,b),c)$
LCM 扩展：$LCM(a,b,c) = LCM(LCM(a,b),c)$

实现示例：

def gcd_multiple(*numbers):
    """计算多个数的 GCD"""
    from functools import reduce
    return reduce(gcd, numbers)

def lcm_multiple(*numbers):
    """计算多个数的 LCM"""
    from functools import reduce
    return reduce(lcm, numbers)

本文系统介绍了 GCD/LCM 的算法原理和 Python 实现，关键要点包括：