从算法到实现：如何高效求解最大公约数与最小公倍数（附1036题解）

1次阅读

没有评论

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

最近在刷编程竞赛题时遇到了一个经典问题（题目编号 1036），要求同时计算两个数的最大公约数 (GCD) 和最小公倍数(LCM)。这类问题看似简单，但想要写出高效且健壮的代码，还是有不少学问的。今天就来分享一下我的解题思路和优化经验。

题目给出两个整数（比如 6 和 15），要求输出它们的最大公约数和最小公倍数。最直观的暴力解法是：

最大公约数：从较小数开始向下枚举，找到第一个能同时整除两数的值
最小公倍数：从较大数开始向上枚举，找到第一个能被两数同时整除的值

这种方法在小数字时可行，但当遇到大数（比如 1e9 级别）时，效率就会变得极低。时间复杂度是 O(min(a,b))，显然不适合编程竞赛的场景。

更高效的解法是使用欧几里得算法，基于一个关键数学原理：

gcd(a, b) = gcd(b, a \mod b)

这个递推关系会不断缩小问题规模，直到 b = 0 时，a 就是最终结果。其时间复杂度是 O(log min(a,b))，效率提升非常明显。

数学简图说明：
假设 a =24, b=18
1. 24 ÷ 18 = 1 余 6 → gcd(18,6)
2. 18 ÷ 6 = 3 余 0 → gcd(6,0)
3. 返回 6

递归实现（简洁但需要注意栈深度）：

def gcd_recursive(a, b):
    """递归实现 GCD"""
    return a if b == 0 else gcd_recursive(b, a % b)

迭代实现（推荐）：

def gcd_iterative(a, b):
    """迭代实现 GCD，避免递归栈溢出"""
    while b:
        a, b = b, a % b
    return a

计算 LCM 时需要注意：

def lcm(a, b):
    """计算最小公倍数"""
    return a * b // gcd_iterative(a, b)  # 先除后乘避免溢出

使用位运算和迭代进一步优化：

int gcd(int a, int b) {if (a == 0) return b;
    if (b == 0) return a;

    // 移除公因子 2
    int shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);

    do {b >>= __builtin_ctz(b);
        if (a > b) std::swap(a, b);
        b -= a;
    } while (b);

    return a << shift;
}

实际编码时需要特别注意：