Guest User

Untitled

a guest
Jan 7th, 2015
307
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <list>
  2. #include <map>
  3. #include <set>
  4. #include <deque>
  5. #include <stack>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <sstream>
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <memory.h>
  15. #include <ctime>
  16. #include <bitset>
  17.  
  18. using namespace std;
  19.  
  20. #define ABS(a) ((a>0)?a:-(a))
  21. #define MIN(a,b) ((a<b)?(a):(b))
  22. #define MAX(a,b) ((a<b)?(b):(a))
  23. #define FOR(i,a,n) for (int i=(a);i<(n);++i)
  24. #define FI(i,n) for (int i=0; i<(n); ++i)
  25. #define pnt pair <int, int>
  26. #define mp make_pair
  27. #define PI 3.1415926535897
  28. #define MEMS(a,b) memset(a,b,sizeof(a))
  29. #define LL long long
  30. #define U unsigned
  31.  
  32. bool isPrime(int v)
  33. {
  34.     FOR(i, 2, v)
  35.     {
  36.         if (v%i == 0)
  37.             return false;
  38.     }
  39.     return true;
  40. }
  41. vector<vector<double> > l;
  42. pnt fact[100][5];
  43. int sz[100];
  44. vector<int> all[61][61];
  45. int ans[20010];
  46. int now[65][5];
  47. int a[20010];
  48. int max1[100];
  49. int max2[100];
  50. int mod = 1000000007;
  51. int total[70];
  52.  
  53. void gentest()
  54. {
  55.     printf("20000 20000\n");
  56.     FOR(i, 0, 20000)
  57.     {
  58.         printf("%d ", rand() % 60 + 1);
  59.     }
  60.     FOR(i, 0, 20000)
  61.         printf("%d\n", i + 1);
  62. }
  63.  
  64. int main()
  65. {
  66. #ifdef Fcdkbear
  67.     freopen("in.txt", "r", stdin);
  68.     freopen("out.txt", "w", stdout);
  69.     double beg = clock();
  70. #endif
  71.  
  72.     int n, q;
  73.     scanf("%d%d", &n, &q);
  74.     FOR(i, 0, n)
  75.         cin >> a[i];
  76.     l.resize(61);
  77.     FOR(i, 2, 61)
  78.     {
  79.         if (isPrime(i))
  80.         {
  81.             double now = 0;
  82.             int v = 1;
  83.             l[i].push_back(0);
  84.             while (v*i <= 60)
  85.             {
  86.                 now += log(i);
  87.                 v *= i;
  88.                 l[i].push_back(now);
  89.             }
  90.         }
  91.     }
  92.     FOR(i, 2, 61)
  93.     {
  94.         int v = i;
  95.         FOR(j, 2, i+1)
  96.         {
  97.             if (i%j)
  98.                 continue;
  99.             if (isPrime(j))
  100.             {
  101.                 int cnt = 0;
  102.                 while (v%j == 0)
  103.                 {
  104.                     cnt++;
  105.                     v /= j;
  106.                 }
  107.                 fact[i][sz[i]] = mp(j, cnt);
  108.                 sz[i]++;
  109.             }
  110.         }
  111.     }
  112.     FOR(i, 1, 61)
  113.     {
  114.         FOR(j, 1, 61)
  115.         {
  116.             FOR(k, 0, sz[i])
  117.                 all[i][j].push_back(fact[i][k].first);
  118.             FOR(k, 0, sz[j])
  119.                 all[i][j].push_back(fact[j][k].first);
  120.             sort(all[i][j].begin(), all[i][j].end());
  121.             all[i][j].resize(unique(all[i][j].begin(), all[i][j].end()) - all[i][j].begin());
  122.         }
  123.     }
  124.     MEMS(ans, -1);
  125.     FOR(i, 0, q)
  126.     {
  127.         //if (i % 100 == 0)
  128.             //fprintf(stderr, "%d\n", i);
  129.         int x;
  130.         scanf("%d", &x);
  131.         if (ans[x] != -1)
  132.         {
  133.             printf("%d\n", ans[x]);
  134.             continue;
  135.         }
  136.         MEMS(now, 0);
  137.         double bLog = 1e40;
  138.         double nowLog = 0;
  139.         int res = 0;
  140.         int how = -1;
  141.         MEMS(total, 0);
  142.         FOR(j, 0, n)
  143.         {
  144.             int sub = 1;
  145.             if (j >= x)
  146.             {
  147.                 sub = a[j - x];
  148.                 total[sub]--;
  149.                 if (total[sub])
  150.                     sub = 1;
  151.             }
  152.             int add = a[j];
  153.             total[add]++;
  154.             if (total[add] > 1)
  155.                 add = 1;
  156.             if ((sub != 1) || (add != 1)) {
  157.                 FOR(k, 0, all[sub][add].size())
  158.                 {
  159.                     max1[k] = 0;
  160.                     for (int c = (int)l[all[sub][add][k]].size() - 1; c > 0; --c)
  161.                     {
  162.                         if (now[all[sub][add][k]][c])
  163.                         {
  164.                             max1[k] = c;
  165.                             break;
  166.                         }
  167.                     }
  168.                 }
  169.                 FOR(k, 0, sz[sub])
  170.                     now[fact[sub][k].first][fact[sub][k].second]--;
  171.                 FOR(k, 0, sz[add])
  172.                     now[fact[add][k].first][fact[add][k].second]++;
  173.                 FOR(k, 0, all[sub][add].size())
  174.                 {
  175.                     max2[k] = 0;
  176.                     for (int c = (int)l[all[sub][add][k]].size() - 1; c > 0; --c)
  177.                     {
  178.                         if (now[all[sub][add][k]][c])
  179.                         {
  180.                             max2[k] = c;
  181.                             break;
  182.                         }
  183.                     }
  184.                     nowLog += l[all[sub][add][k]][max2[k]];
  185.                     nowLog -= l[all[sub][add][k]][max1[k]];
  186.                 }
  187.             }
  188.             if ((nowLog < bLog) && (j+1>=x))
  189.             {
  190.                 bLog = nowLog;
  191.                 how = j;
  192.             }
  193.         }
  194.         MEMS(now, 0);
  195.         FOR(j, how - x + 1, how + 1)
  196.         {
  197.             FOR(k, 0, sz[a[j]])
  198.                 now[fact[a[j]][k].first][fact[a[j]][k].second]++;
  199.         }
  200.         LL val = 1;
  201.         FOR(j, 2, 61)
  202.         {
  203.             int s = l[j].size();
  204.             s--;
  205.             for (int k = s; k >= 0; --k)
  206.             {
  207.                 if (now[j][k])
  208.                 {
  209.                     FOR(c, 0, k)
  210.                     {
  211.                         val *= j;
  212.                         val %= mod;
  213.                     }
  214.                     break;
  215.                 }
  216.             }
  217.         }
  218.         ans[x] = val;
  219.         printf("%d\n", ans[x]);
  220.     }
  221.  
  222. #ifdef Fcdkbear
  223.     double end = clock();
  224.     fprintf(stderr, "*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
  225. #endif
  226.     return 0;
  227. }
RAW Paste Data