Advertisement
Dang_Quan_10_Tin

QUIZZ

Jun 25th, 2022
635
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.12 KB | None
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define ull unsigned long long
  5. #define pb push_back
  6. #define pii pair<int, int>
  7. #define pll pair<ll, int>
  8. #define pld pair<ld, ll>
  9. #define fi first
  10. #define se second
  11. using namespace std;
  12. const int N = 2e5+5;
  13. const int M = 1e4+5;
  14. const ll mod = 1e9+7;
  15. const ll inf = 1e15;
  16. const ld base = 1e-6;
  17. int n, t, m, k, a[N], ans, lab[N], d[N], tong, l[N], r[N];
  18. vector<pii> adj[N];
  19. vector<int> vi;
  20. ll pw(ll k, ll n)
  21. {
  22.  
  23.     ll total = 1;
  24.     for(; n; n >>= 1)
  25.     {
  26.         if(n&1)total = total * k % mod;
  27.         k = k * k % mod;
  28.     }
  29.     return total;
  30. }
  31. void sol()
  32. {
  33.     cin >> n;
  34.     for(int i = 2; i < N; i ++)
  35.     {
  36.         if(!d[i])
  37.             for(int j = i; j < N; j += i)d[j] = i;
  38.     }
  39.     for(int i = 1; i <= n; i ++)
  40.     {
  41.         cin >> a[i];
  42.         while(a[i] > 1)
  43.         {
  44.             k = d[a[i]];
  45.             m = 1;
  46.             while(a[i] % k ==0)
  47.             {
  48.                 m *= k;
  49.                 a[i] /= k;
  50.             }
  51.             adj[k].pb({i, m});
  52.         }
  53.     }
  54.     ans = 1;
  55.     for(int i = 2; i < N; i ++)
  56.     {
  57.         if(adj[i].empty())continue;
  58.         vi.clear();
  59.         m = adj[i].size();
  60.         for(int j = 0; j < m; j ++)
  61.         {
  62.             while(!vi.empty() && adj[i][vi.back()].se <= adj[i][j].se)vi.pop_back();
  63.             l[j] = vi.empty() ? 0 : adj[i][vi.back()].fi;
  64.             vi.pb(j);
  65.         }
  66.         vi.clear();
  67.         for(int j = m-1; j >= 0; j --)
  68.         {
  69.             while(!vi.empty() && adj[i][vi.back()].se < adj[i][j].se)vi.pop_back();
  70.             r[j] = vi.empty() ? n+1 : adj[i][vi.back()].fi;
  71.             ans = 1ll * pw(adj[i][j].se % mod, 1ll*(adj[i][j].fi-l[j]) * (r[j]-adj[i][j].fi) ) * ans % mod;
  72.             vi.pb(j);
  73.         }
  74.     }
  75.     cout << ans;
  76. }
  77. int main()
  78. {
  79.     cin.tie(0);
  80.     cout.tie(0);
  81.     ios_base::sync_with_stdio(0);
  82.     #define task "QUIZZ"
  83.     if(fopen(task".inp", "r"))
  84.     {
  85.         freopen(task".inp", "r", stdin);
  86.         freopen(task".out", "w", stdout);
  87.     }
  88.     int test = 1;
  89.     //cin >> test;
  90.     while(test -- > 0)sol();
  91.     return 0;
  92. }
  93.  
Advertisement
RAW Paste Data Copied
Advertisement