如何高效求解最大公约数与最小公倍数：从欧几里得到现代优化

1次阅读

没有评论

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

最大公约数 (GCD) 和最小公倍数 (LCM) 在计算机科学和工程领域有着广泛的应用。例如：

密码学中 RSA 算法依赖大数 GCD 计算
信号处理中的滤波器设计需要 LCM 确定采样周期
游戏开发中碰撞检测使用 GCD 简化分数运算

最直观的方法是枚举所有可能的公约数：

从较小数开始向下遍历
第一个能同时整除两数的即为 GCD

时间复杂度：O(min(a,b))

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

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

数学证明：

设 d = gcd(a,b)，则 d | a 且 d |b
a 可以表示为 b *q + r
因此 d |r，即 d 也是 b 和 r 的公约数
递归直到余数为 0，最后非零余数即为 GCD

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

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

def gcd(a, b):
    """递归实现欧几里得算法"""
    if b == 0:
        return abs(a)  # 处理负数
    return gcd(b, a % b)

def lcm(a, b):
    """利用 GCD 计算 LCM"""
    return abs(a * b) // gcd(a, b) if a and b else 0

if __name__ == "__main__":
    try:
        x, y = map(int, input().split())
        print(gcd(x, y), lcm(x, y))
    except ValueError:
        print("请输入两个整数")

import java.math.BigInteger;
import java.util.Scanner;

public class GCD {
    // 处理大数情况
    static BigInteger gcd(BigInteger a, BigInteger b) {return b.equals(BigInteger.ZERO) ? a.abs() : gcd(b, a.mod(b));
    }

    public static void main(String[] args) {Scanner sc = new Scanner(System.in);
        try {BigInteger x = sc.nextBigInteger();
            BigInteger y = sc.nextBigInteger();
            BigInteger gcd = gcd(x, y);
            BigInteger lcm = x.multiply(y).abs().divide(gcd);
            System.out.println(gcd + " " + lcm);
        } catch (Exception e) {System.out.println("输入格式错误");
        }
    }
}

使用 Stein 算法（二进制 GCD 算法）：

若 a 和 b 都是偶数，gcd(a,b)=2*gcd(a/2,b/2)
若 a 是偶数，b 是奇数，gcd(a,b)=gcd(a/2,b)
否则用更相减损术

def gcd_binary(a, b):
    if a == 0: return b
    if b == 0: return a
    shift = 0
    # 移除公共的 2 的因子
    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