fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef vector<int> big_int;
  6.  
  7. bool les(big_int a, big_int b)
  8. {
  9.     double A = 0, B = 0;
  10.     for(int i = 1; i < 60; i++)
  11.         A += a[i] * log(i);
  12.     for(int i = 1; i < 60; i++)
  13.         B += b[i] * log(i);
  14.     return A < B;
  15. }
  16.  
  17. big_int tr(int t)
  18. {
  19.     big_int ret(60);
  20.     for(int i = 2; i * i <= t; i++)
  21.         while(t % i == 0)
  22.             ret[i]++, t /= i;
  23.     if(t)
  24.         ret[t]++;
  25.     return ret;
  26. }
  27.  
  28. const int mod = 1e9 + 7;
  29.  
  30. int bpow(int x, int n)
  31. {
  32.     if(n == 0)
  33.         return 1;
  34.     int t = bpow(x, n >> 1);
  35.     if(n % 2 == 0)
  36.         return 1LL * t * t % mod;
  37.     else
  38.         return 1LL * x * t % mod * t % mod;
  39. }
  40.  
  41. int get(big_int t)
  42. {
  43.     int ret = 1;
  44.     for(int i = 0; i < 60; i++)
  45.         ret = 1LL * ret * bpow(i, t[i]) % mod;
  46.     return ret;
  47. }
  48.  
  49. main()
  50. {
  51.     //freopen("input.txt", "r", stdin);
  52.     //freopen("output.txt", "w", stdout);
  53.     ios::sync_with_stdio(0);
  54.     cin.tie(0);
  55.     int n, q;
  56.     cin >> n >> q;
  57.     big_int ans[n + 1];
  58.     for(int i = 1; i <= n; i++)
  59.     {
  60.         big_int t(60);
  61.         t[2] = 1000000;
  62.         ans[i] = t;
  63.     }
  64.     map<big_int, int> lens;
  65.     for(int i = 0; i < n; i++)
  66.     {
  67.         int t;
  68.         cin >> t;
  69.         big_int T = tr(t);
  70.         map<big_int, int> nlens;
  71.         nlens[T] = 1;
  72.         for(auto it: lens)
  73.         {
  74.             big_int TT = T;
  75.             for(int i = 0; i < 60; i++)
  76.                 TT[i] = max(TT[i], it.first[i]);
  77.             nlens[TT] = max(nlens[TT], it.second + 1);
  78.         }
  79.         lens = nlens;
  80.         for(auto it: lens)
  81.             if(les(it.first, ans[it.second]))
  82.                 ans[it.second] = it.first;
  83.     }
  84.     for(int i = n - 1; i; i--)
  85.         if(les(ans[i + 1], ans[i]))
  86.             ans[i] = ans[i + 1];
  87.     int ANS[n + 1];
  88.     for(int i = 1; i <= n; i++)
  89.         ANS[i] = get(ans[i]);
  90.     while(q--)
  91.     {
  92.         int x;
  93.         cin >> x;
  94.         cout << ANS[x] << "\n";
  95.     }
  96.  
  97. }
Runtime error #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4lksQD
language:
C++14 (gcc 8.3)
created:
9 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!