最大公约数与最小公倍数

发表于 更新于
本文展示了一种快速计算最大公倍数的方法，同时也是 LaTex 测试

欧几里得算法（计算最大公倍数）

设

同时 和 有共同约数

则

显然 也有约数
可知 和 与 有相等的最大公约数.
由此证明了

同时，我们有

我们只需不断计算使 即可.
由此给出该算法的 C++ 实现

1
2
3
4
5
6
7
8
9
long long gcd(long long m,long long n) {
    long long t = 1;
    while (t != 0) {
        t = m % n;
        m = n;
        n = t;
    }
    return m;
}

计算最小公倍数

我们不加证明地给出

所以仅需计算 和 即可.
实际应用中可能需要交换乘法和除法的顺序以避免溢出.

对于多个数的情况，有

C++实现

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
#include <iostream>
using namespace std;

long long gcd(long long m,long long n) {
    long long t = 1;
    while (t != 0) {
        t = m % n;
        m = n;
        n = t;
    }
    return m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    long long a;
    cin >> a;  // first number
    long long lcm = a;

    for (int i = 1; i < N; i++) {
        cin >> a;
        lcm = (lcm / gcd(lcm, a)) * a; //avoid overflow
    }
    cout << lcm << "\n";

    return 0;
}