题目链接

最大公因数与最小公倍数

题目描述

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

解题思路

本题的核心是计算最大公因数（GCD）和最小公倍数（LCM）。

1. 最大公因数 (GCD)

计算最大公因数最经典、最高效的算法是欧几里得算法（Euclidean Algorithm），也称为辗转相除法。

其原理基于以下定理： 两个整数的最大公因数等于其中较小的数和两数相除余数的最大公因数。 用数学公式表示为：。

算法步骤如下：

  1. 令 。
  2. 当 不为 时，令 , ，然后回到步骤 1。
  3. 当 为 时，此时的 就是原始 和 的最大公因数。

例如，计算 :

  • 此时余数为 ，所以最大公因数是 。

2. 最小公倍数 (LCM)

最小公倍数可以通过最大公因数计算得出。它们之间存在一个重要的关系： 两个正整数的乘积等于它们的最大公因数和最小公倍数的乘积。 即：

由此，我们可以推导出计算 LCM 的公式：

3. 数据溢出问题

需要注意的是，题目中 和 的范围最高可达 。如果直接计算 ，结果可能会达到 ，这会超出标准的 32 位整型（int）的表示范围，导致数据溢出。

为了避免这个问题，我们需要：

  • 使用 64 位整型（C++中的 long long，Java中的 long）来存储最小公倍数的结果。
  • 在计算时，为了防止中间过程溢出，最好使用以下等价的计算顺序： 因为 必然能整除 ，所以 是一个整数，这样可以保证中间乘积不会过大。

代码

#include <iostream>

using namespace std;
using LL = long long;

// 使用欧几里得算法计算最大公因数
LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    LL a, b;
    cin >> a >> b;

    LL common_divisor = gcd(a, b);
    // 使用 a / gcd * b 的方式防止中间结果溢出
    LL common_multiple = a / common_divisor * b;

    cout << common_divisor << " " << common_multiple << endl;

    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 commonDivisor = gcd(a, b);
        // 使用 a / gcd * b 的方式防止中间结果溢出
        long commonMultiple = a / commonDivisor * b;

        System.out.println(commonDivisor + " " + commonMultiple);
    }
}

# Python 3.9 及以上版本内置了 math.gcd
# 为了演示算法，我们手动实现
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

common_divisor = gcd(a, b)
# Python的int可以处理大数，不会溢出
# 但好习惯是使用 a // gcd * b
common_multiple = a // common_divisor * b

print(common_divisor, common_multiple)

算法及复杂度

  • 算法：欧几里得算法
  • 时间复杂度：，辗转相除法的迭代次数是对数级别的。
  • 空间复杂度：（对于迭代实现）。如果使用递归实现，空间复杂度为 ，用于存储递归调用栈。