[GESP样题 五级] 小杨的锻炼

传送门：点我进入洛谷

本题主要考察 初等数论 中 辗转相除法（欧几里得算法） 知识点，如果有遗忘可以复习。

在学习辗转相除法的时候，我们通过证明已经得出​\gcd(a,b) = \gcd(b, a \bmod b)的结论，所以 gcd函数可以写成：

int gcd(int a, b){
    return b ? gcd(b, a % b) : a;
}

那么该如何通过这种辗转相除法来求出 最小公倍数 呢？

证明过程

我们可以用质因数分解中指数的特性。对任意质数​p，设其在​a, b中的指数为​m, n，则：

• ​\text{gcd}(a,b)取指数最小值​\min(m,n)，
• ​\text{lcm}(a,b)取指数最大值​\max(m,n)。

由于​m + n = \min(m,n) + \max(m,n)，将​a, b分解为质因数乘积后，两边乘积的指数必然相等，故：​a \times b = \text{gcd}(a,b) \times \text{lcm}(a,b)
移项即得公式：​ \text{lcm}(a, b) = \frac{a \times b}{\text{gcd}(a, b)}

注意：因为​a, b可能较大，所以会有 int风险，需要开 long long

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

LL lcm(int a, int b){
    return a / gcd(a, b) * b;
}

int main(){
    int n;
    cin >> n;
    LL res = 1;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        res = lcm(res, x);
    }
    cout << res;
    return 0;
}