题解 | #最大公因数与最小公倍数#

题目链接

最大公因数与最小公倍数

题目描述

给定两个正整数 $a$ 与 $b$ ，请你计算它们的最大公因数（GCD）与最小公倍数（LCM）。

解题思路

本题的核心是求解两个数的最大公因数和最小公倍数。

最大公因数 (GCD) 我们可以使用辗转相除法（欧几里得算法）来高效地计算两个正整数的最大公因数。该算法的原理是：两个整数的最大公因数等于其中较小的数和两数相除余数的最大公因数。用公式表示为： $\gcd(a, b) = \gcd(b, a \pmod b)$ 。当 $a \pmod b = 0$ 时， $\gcd(a, b) = b$ 。我们可以通过递归或循环实现。
最小公倍数 (LCM) 最小公倍数可以通过最大公因数计算得出。它们之间存在一个重要的关系： $a \cdot b = \gcd(a, b) \cdot \operatorname{lcm}(a, b)$ 因此，我们可以推导出计算最小公倍数的公式： $\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$

为了防止在计算 $a \cdot b$ 时发生整数溢出（即使使用 long long，两个大数相乘也可能溢出），我们可以将公式变形为： $\operatorname{lcm}(a, b) = \frac{a}{\gcd(a, b)} \cdot b$ 先做除法可以有效避免溢出的风险。

代码

c++
java
python

#include <iostream>

using namespace std;

// 辗转相除法求最大公因数
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    long long a, b;
    cin >> a >> b;
    long long g = gcd(a, b);
    // 使用 a / gcd * b 的方式防止溢出
    long long l = a / g * b;
    cout << g << " " << l << "\n";
    return 0;
}

import java.util.Scanner;

public class Main {
    // 辗转相除法求最大公因数
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        
        long g = gcd(a, b);
        // 使用 a / gcd * b 的方式防止溢出
        long l = a / g * b;
        
        System.out.println(g + " " + l);
    }
}

# 辗转相除法求最大公因数
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

a, b = map(int, input().split())

g = gcd(a, b)
# 使用 a // gcd * b 的方式防止溢出
l = a // g * b

print(g, l)

算法及复杂度

算法：辗转相除法（欧几里得算法）
时间复杂度： $O(\log(\min(a, b)))$ ，这是辗转相除法的时间复杂度。
空间复杂度： $O(\log(\min(a, b)))$ ，主要是递归调用栈的深度。如果使用循环实现，空间复杂度为 $O(1)$ 。