Advertisement
hkshakib

Untitled

Mar 24th, 2020
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll k = 30;
  5. const ll N = 1e5;
  6. const ll ZERO = 0;
  7. const ll mx =10000025;
  8. ll table[N][k + 1];
  9. vector<ll>Arr(mx+10);
  10. const ll mod = 1000000007;
  11. void build()
  12. {
  13.     ll n = Arr.size();
  14.     for(int i = 0; i < n; i++)
  15.         table[i][0] = Arr[i]%mod;
  16.     for(int j=1;j<=k;j++)
  17.     {
  18.         for(int i=0;i<=n-(1<<j);i++)
  19.             table[i][j]=__gcd(table[i][j - 1],table[i+(1<<(j-1))][j-1])%mod;
  20.     }
  21. }
  22. int main()
  23. {
  24.     ll t;
  25.     cin>>t;
  26.     while(t--)
  27.     {
  28.         ll n,a;
  29.         cin>>n;
  30.         ll div = 1;
  31.         for(ll i=0; i<n; i++)
  32.         {
  33.             cin>>a;
  34.             div=(div*a)%mod;
  35.         }
  36.         Arr.push_back(div%mod);
  37.     }
  38.     build();
  39.     ll L=0,R= Arr.size()-1;
  40.     for(ll i = 0; i < 1; i++)
  41.     {
  42.         ll answer = ZERO;
  43.         for(int j = k; j >= 0; j--)
  44.         {
  45.             if(L + (1 << j) - 1 <= R)
  46.             {
  47.                 answer = __gcd(answer, table[L][j])%mod;
  48.                 L += (1 << j)%mod;
  49.             }
  50.         }
  51.         cout << answer%mod << endl;
  52.     }
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement