高效求解最大公约数与最小公倍数：算法优化与代码实现

1次阅读

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

最大公约数（GCD）和最小公倍数（LCM）是数学和计算机科学中的基础概念，广泛应用于密码学、分数运算、时间调度等领域。在算法竞赛和面试中，高效求解 GCD 和 LCM 是必备技能。本文将深入探讨多种算法实现，分析其性能差异，并提供优化方案和代码示例。

密码学：RSA 加密算法中，GCD 用于生成密钥对
分数运算：约分和通分需要 GCD 和 LCM
时间调度：周期性任务的最优调度需要 LCM
图像处理：像素比例缩放涉及 GCD 计算

时间复杂度：$O(min(a,b))$
从较小数向下逐个尝试，直到找到公约数
优点：实现简单
缺点：效率低下，不适用于大数

时间复杂度：$O(log(min(a,b)))$
基于定理：$GCD(a,b) = GCD(b, a\%b)$
递归实现简洁，但存在爆栈风险
迭代实现更安全高效

时间复杂度：$O(log(min(a,b)))$
优化点：用位移代替除法运算
特别适合大整数运算
核心思想：
若 a 和 b 都是偶数，$GCD(a,b)=2*GCD(a/2,b/2)$
若 a 是偶数 b 是奇数，$GCD(a,b)=GCD(a/2,b)$
否则用较大数减较小数

位运算优化：
a & 1代替 a % 2 判断奇偶
a >> 1代替a / 2
a << 1代替a * 2
迭代代替递归：
避免函数调用开销
防止栈溢出
处理负数：
GCD 结果始终为正
先取绝对值再计算
防止溢出：
先除后乘计算 LCM
使用更大数据类型

#include <iostream>
#include <cstdlib> // for abs

// 迭代版欧几里得算法
int gcd(int a, int b) {a = abs(a);
    b = abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 位运算优化的 Stein 算法
int binary_gcd(int a, int b) {if (a == 0) return abs(b);
    if (b == 0) return abs(a);

    a = abs(a);
    b = abs(b);

    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        ++shift;
    }

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

    do {while ((b & 1) == 0)
            b >>= 1;
        if (a > b) std::swap(a, b);
        b -= a;
    } while (b != 0);

    return a << shift;
}

int lcm(int a, int b) {if (a == 0 || b == 0) return 0;
    return abs(a / gcd(a, b) * b); // 先除后乘防溢出
}

int main() {
    int x, y;
    std::cin >> x >> y;
    std::cout << gcd(x, y) << ' ' << lcm(x, y) << std::endl;
    return 0;
}

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

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

    a, b = abs(a), abs(b)
    shift = 0

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

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

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

    return a << shift

def lcm(a, b):
    if a == 0 or b == 0:
        return 0
    return abs(a // gcd(a, b) * b)

x, y = map(int, input().split())
print(gcd(x, y), lcm(x, y))

边界条件处理：
输入包含 0 时，GCD 为另一个数的绝对值
LCM 在任一数为 0 时应返回 0
递归深度限制：
在 Python 中默认递归深度约 1000 层
大数时可能爆栈，建议用迭代实现
整数溢出问题：
计算 LCM 时先乘后除会导致溢出
应先进行除法运算
负数处理：
结果应为正数
计算前先取绝对值
性能陷阱：
欧几里得算法在最坏情况下（连续斐波那契数）性能下降
大数时建议使用二进制 GCD

GCD 的扩展：
迭代计算：$GCD(a,b,c) = GCD(GCD(a,b),c)$
时间复杂度：$O(n \cdot log(min))$
LCM 的扩展：
类似 GCD：$LCM(a,b,c) = LCM(LCM(a,b),c)$
注意防止中间结果溢出
代码示例：

def multi_gcd(numbers):
    current_gcd = numbers[0]
    for num in numbers[1:]:
        current_gcd = gcd(current_gcd, num)
        if current_gcd == 1:
            break  # 提前终止
    return current_gcd

def multi_lcm(numbers):
    current_lcm = numbers[0]
    for num in numbers[1:]:
        current_lcm = lcm(current_lcm, num)
    return current_lcm