fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.   ios::sync_with_stdio(0);
  6.   cin.tie(0);
  7.  
  8.   int N;
  9.   cin >> N;
  10.  
  11.   vector<int> A(N);
  12.   for (int i = 0; i < N; i++) {
  13.     cin >> A[i];
  14.   }
  15.  
  16.   const int M = 1e5 + 5;
  17.   const int MOD = 1e9 + 7;
  18.  
  19.   const auto Power = [&](int a, long long x) {
  20.     int res = 1;
  21.     while (x > 0) {
  22.       if (x & 1) {
  23.         res = 1ll * res * a % MOD;
  24.       }
  25.       a = 1ll * a * a % MOD;
  26.       x /= 2;
  27.     }
  28.     return res;
  29.   };
  30.  
  31.   vector<int> isprime(M, 1);
  32.   vector<int> factorize(M, 1);
  33.  
  34.   for (int i = 2; i < M; i++) {
  35.     if (isprime[i]) {
  36.       for (int j = i; j < M; j += i) {
  37.         isprime[j] = 0;
  38.         factorize[j] = i;
  39.       }
  40.     }
  41.   }
  42.  
  43.   vector<vector<pair<int, int>>> occ(M);
  44.   for (int i = 0; i < N; i++) {
  45.     while (A[i] > 1) {
  46.       int p = factorize[A[i]];
  47.       A[i] /= p;
  48.       if (!occ[p].empty() && occ[p].back().first == i) {
  49.         occ[p].back().second += 1;
  50.       } else {
  51.         occ[p].emplace_back(i, 1);
  52.       }
  53.     }
  54.   }
  55.  
  56.   int ans = 1;
  57.   for (int p = 2; p < M; p++) {
  58.     if (occ[p].empty()) {
  59.       continue;
  60.     }
  61.  
  62.     long long total_power_sum = 0;
  63.     int current_power_sum = 0;
  64.  
  65.     vector<array<int, 3>> st;
  66.     st.push_back({-1, MOD, 0});
  67.     occ[p].emplace_back(N, 0);
  68.  
  69.     for (int i = 0; i + 1 < (int) occ[p].size(); i++) {
  70.       auto [id, freq] = occ[p][i];
  71.       while (!st.empty() && st.back()[1] <= freq) {
  72.         current_power_sum -= st.back()[2];
  73.         st.pop_back();
  74.       }
  75.       int add = freq * (id - st.back()[0]);
  76.       current_power_sum += add;
  77.       st.push_back({id, freq, add});
  78.       total_power_sum += 1ll * current_power_sum * (occ[p][i + 1].first - id);
  79.     }
  80.  
  81.     ans = 1ll * ans * Power(p, total_power_sum) % MOD;
  82.   }
  83.  
  84.   cout << ans << '\n';
  85.   return 0; 
  86. }
  87.  
Success #stdin #stdout 0s 6256KB
comments (?)
stdin
copy 
4
6 12 60 36
stdout
copy 
773725433
https://ideone.com/ifIFgc
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!