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

设
$$ a = bq + r $$
同时 $a$ 和 $b$ 有共同约数 $t$
$$ a = ut $$
$$ b = vt $$
则
$$
a \mod b = (u - vq)t
$$
显然 $a \mod b$ 也有约数 $t$
可知 $a$ 和 $b$ 与 $a \mod b$ 有相等的最大公约数.
由此证明了
$$
\gcd(a, b) = \gcd(b, a \mod b)
$$
同时，我们有
$$
\gcd(a, 0) = a
$$
我们只需不断计算使 $a \mod b = 0$ 即可.
由此给出该算法的 C++ 实现

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;
}

计算最小公倍数

我们不加证明地给出
$$
lcm(a, b) = \frac{\left| a \times b \right|}{\gcd(a, b)}
$$
所以仅需计算 $ a \times b $ 和 $ \gcd(a, b) $ 即可.
实际应用中可能需要交换乘法和除法的顺序以避免溢出.

对于多个数的情况，有
$$
lcm(a1​,a2​,a3​,…,an​)=lcm(lcm(a1​,a2​),a3​,…)
$$
C++实现

#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;
}