HDU-2028 Lowest Common Multiple Plus

代碼

#include <iostream>
#include <algorithm>

using namespace std;

long long int gcd(long long int n, long long int m){
    if(n<m){
        swap(n, m);
    }
    while(n%m){
        long long int r = n%m;
        n = m;
        m = r;
    }
    return m;
}

int main() {

    int n;
    while(cin>>n){
        long long int a[n];
        for(int i=0; i<n; i++){
            cin>>a[i];
        }
        sort(a, a+n);
        for(int i=0; i<n-1; i++){
            long long int t = gcd(a[i], a[i+1]);
            a[i+1] = a[i]*a[i+1]/t;
        }
        cout<<a[n-1]<<endl;
    }

    return 0;
}
           

注解

1、求最大公約數的輾轉相除法gcd

2、最小公倍數=二數乘積 除以 最大公約數

3、n個數的最小公倍數的求法，就是任取2個求出他們的最小公倍數，用結果當做一個數，再與其他數一起連乘。

結果