欧几里得算法计算 GCD 和 LCM

引入

例题（B4025 最大公约数）

定义两个正整数的最大公约数 gcd⁡(a,b)gcd(a,b) 为最大的正整数 d，使得 d 可以同时整除 a 和 b。

例如，gcd⁡(9,12)=3gcd(9,12)=3，因为 9÷3 和 12÷3 的余数是 0，而无法找到一个比 3 更大的正整数满足要求。

现在给定两个正整数 a,b，要求出 gcd⁡(a,b)

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	long long a,b,m=0;
	cin >> a >> b;
	for (int i=min(a,b); i >= 1; i--) {
		if (a % i != 0 || b % i != 0) continue;
		m = i;
		break;
	}
	cout << m;
	
	return 0;
}

OK，直接TLE得50分。这个时候就需要用到欧几里得算法来解题。

欧几里得算法讲解

GCD

欧几里得算法的时间复杂度是 O(log(min(a,b)))，比暴力枚举要快得多。以下是使用欧几里得算法的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

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

    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }

    cout << a;
    
    return 0;
}

这个实现通过不断将 a 取模 b，并交换 a 和 b，直到 b 为零时，a 就是最大公约数。这样可以大大提高效率。

PS:在欧几里得算法中，也不需要提前比较 a 和 b 的大小，因为算法本身就会完成这一步骤。

LCM

对于两个正整数 (a) 和 (b)，它们的最小公倍数可以通过以下公式计算：

$$
{lcm}(a, b) = \frac{|a \times b|}{\text{gcd}(a, b)}
$$

以下是计算gcd和lcm的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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) {
    return (a / gcd(a, b)) * b;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << "GCD: " << gcd(a, b) << endl;
    cout << "LCM: " << lcm(a, b) << endl;
    
    return 0;
}

通过先计算出两数的最大公约数，再利用公式计算出最小公倍数，可以高效地求出结果。