最大公约数和最小公倍数

Posted on Edited on In

题目描述
最大公约数（GCD，Greatest Common Divisor）指两个或多个整数共有约数中最大的一个。最小公倍数（LCM，Least Common Multiple）指两个或多个整数公有的倍数中最小的一个。本问题要求计算两个正整数的最大公约数和最小公倍数。

输入格式
输入共 1 行，包含两个正整数 a 和 b（用空格分隔）。

输出格式
输出共 2 行，第一行是 a 和 b 的最大公约数，第二行是 a 和 b 的最小公倍数。

数据范围
1 ≤ a, b ≤ 1000000

输入样例：

1
48 36

输出样例：

1
2
12
144

注意事项

  • 计算最大公约数常用的算法有欧几里得算法（辗转相除法）和更相减损术。
  • 最小公倍数可以通过公式 LCM(a, b) = a * b / GCD(a, b) 计算，但需要注意乘法溢出的问题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

// 计算最大公约数（欧几里得算法/辗转相除法）
long long gcd(long long a, long long b)
{
    while (b != 0)
    {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算最小公倍数
long long lcm(long long a, long long b)
{
    // 先计算最大公约数，然后使用公式 LCM(a, b) = a * b / GCD(a, b)
    // 为了避免乘法溢出，先进行除法运算
    return a / gcd(a, b) * b;
}

int main()
{
    long long a, b;
    cin >> a >> b;
    
    long long greatest_common_divisor = gcd(a, b);
    long long least_common_multiple = lcm(a, b);
    
    cout << greatest_common_divisor << endl;
    cout << least_common_multiple << endl;
    
    return 0;
}

时间复杂度

  • 时间复杂度：O(log min(a, b))，其中 a 和 b 是输入的两个正整数。
  • 空间复杂度：O(1)。

代码解释

  • 计算最大公约数的欧几里得算法（辗转相除法）的核心思想是：如果 a 和 b 是两个正整数，且 a ≥ b，那么 gcd(a, b) = gcd(b, a % b)。当 b 变为 0 时，a 就是最大公约数。
  • 计算最小公倍数的公式是 LCM(a, b) = a * b / GCD(a, b)。为了避免乘法溢出，我们先计算 a / gcd(a, b)，然后再乘以 b。
  • 在代码中，我们使用 long long 类型来存储中间结果，以避免在处理较大的输入时发生溢出。