Codeforces.1349B Orac and Medians

1.Problem
https://codeforces.com/problemset/problem/1349/B

2.Idea
Prime Factorization

3.Source

 int n;  
 ll a[N];  
 map<ll, vector<int>> mp;  
 void pFac(ll H)  
 {  
      for (ll i = 2; i*i <= H; i++) {  
           int cnt = 0;  
           while (H%i == 0) {  
                cnt++;  
                H /= i;  
           }  
           if (cnt > 0) {  
                mp[i].push_back(cnt);  
           }  
      }  
      if (H > 1) {  
           mp[H].push_back(1);  
      }  
 }  
 ll gcd(const ll a, const ll b)  
 {  
      if (b == 0) return a;  
      return gcd(b, a%b);  
 }  
 int main() {  
      scanf("%d\n", &n);  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &a[i]);  
           pFac(a[i]);  
      }  
      if (n == 2) {  
           cout << a[0] * a[1] / gcd(a[0] , a[1]) << endl;  
           return 0;  
      }  
      ll ans = 1;  
      for (auto itr = mp.begin(); itr != mp.end(); itr++) {  
           int p = itr->first;  
           vector<int> v = itr->second;  
           int k = 0;  
           if (v.size() + 2 <= n) continue;  
           sort(v.begin(), v.end());  
           if (v.size() + 1 == n) {  
                k = v[0];  
           }  
           else {  
                k = v[1];  
           }  
           int t = (int)pow(1.0 * p, 1.0 * k);  
           ans = ans * (ll)t;  
      }  
      printf("%d\n", ans);  
      return 0;  
 }