【題解】Codeforces 1350C. Orac and LCM

#include <iostream>
#include <map>
using namespace std;
 
int n, a;
map <int, pair<int, int> > mp;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    cin >> a;
    for (int i = 2; i <= a; i++){
        if (a % i != 0) continue;
        int cnt = 0;
        while (a % i == 0){
            a /= i;
            cnt++;
        }
        mp[i].first = cnt;
    }
    cin >> a;
    for (int i = 2; i <= a; i++){
        if (a % i != 0) continue;
        int cnt = 0;
        while (a % i == 0){
            a /= i;
            cnt++;
        }
        if (mp[i].first){
            if (mp[i].first > cnt) mp[i].second = cnt;
            else{
                mp[i].second = mp[i].first;
                mp[i].first = cnt;
            }
        }
        else mp[i].first = cnt;
    }
    n -= 2;
    while (n--){
        cin >> a;
        for (auto p:mp){
            int cnt = 0;
            while (a % p.first == 0){
                a /= p.first;
                cnt++;
            }
            if (cnt < mp[p.first].first){
                if (cnt < mp[p.first].second){
                    mp[p.first].first = mp[p.first].second;
                    mp[p.first].second = cnt;
                }
                else mp[p.first].first = cnt;
            }
        }
    }
    long long ans = 1;
    for (auto p:mp){
        for (int i = p.second.first; i > 0; i--){
            ans *= p.first;
        }
    }
    cout << ans << "\n";
}