fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define LL long long int
  4. #define mod 1000000007
  5. vector<LL>prime,b;
  6. LL a[109],seive[1000009]={0};
  7. LL power(LL a, LL b)
  8. {
  9.     if(b==0)return 1;
  10.     LL c=power(a,b/2);
  11.     c=(c*c)%mod;
  12.     if(b%2==1)
  13.         c=(c*a)%mod;
  14.     return c;
  15. }
  16. LL gcd(LL a,LL b)
  17. {
  18.     if(a==0)return b;
  19.     else return gcd(b%a,a);
  20. }
  21. void pre()
  22. {
  23.     //function to compute seive
  24.     LL i,j;
  25.     seive[0]=seive[1]=1;
  26.     for(i=2;i*i<=1000000;i++)
  27.     {
  28.        if(!seive[i])
  29.        {
  30.            for(j=i*2;j<=1000000;j+=i)
  31.             seive[j]=1;
  32.        }
  33.     }
  34.     for(i=2;i<=1000000;i++)
  35.         if(!seive[i])prime.push_back(i);
  36. }
  37. int main()
  38. {
  39.     int t;
  40.     pre();
  41.     cin>>t;
  42.     while(t--)
  43.     {
  44.         LL n,i,j;
  45.         cin>>n;
  46.         b.clear();
  47.         b.resize(prime.size(),0);
  48.         for(i=0;i<n;i++)
  49.             cin>>a[i];
  50.         for(i=0;i<=n;i++)
  51.         {
  52.             LL curr=a[i];
  53.             for(j=0;prime[j]<=curr && j<prime.size();j++)
  54.             {
  55.                 while(a[i]%prime[j]==0)
  56.                 {
  57.                     b[j]++;
  58.                     a[i]=a[i]/prime[j];
  59.                 }
  60.             }
  61.         }
  62.         vector<LL> prime2;
  63.  
  64.         for(i=0;i<n;i++)
  65.             for(j=0;j<n;j++)
  66.             {
  67.                 if(i==j)
  68.                 {
  69.                     if(a[i]>1)
  70.                     {
  71.                         LL xyz=(LL)sqrt(a[i]);
  72.                         if(xyz*xyz==a[i])prime2.push_back(xyz);
  73.                     }
  74.                     continue;
  75.                 }
  76.                 LL x=gcd(a[i],a[j]);
  77.                 if(x>1)prime2.push_back(x);
  78.             }
  79.         sort(prime2.begin(),prime2.end());
  80.         int ns=unique(prime2.begin(),prime2.end())-prime2.begin();
  81.         prime2.resize(ns);
  82.         vector<LL> b2;
  83.         b2.resize(prime2.size(),0);
  84.  
  85.         for(i=0;i<=n;i++)
  86.         {
  87.             LL curr=a[i];
  88.             for(j=0;j<prime2.size()  && j<prime2.size();j++)
  89.             {
  90.                 cout<<prime2[j]<<endl;
  91.                 while(a[i]%prime2[j]==0)
  92.                 {
  93.                     b2[j]++;
  94.                     a[i]=a[i]/prime2[j];
  95.                 }
  96.             }
  97.         }
  98.         LL ans=1;
  99.         for(i=0;i<prime.size();i++)
  100.         {
  101.             LL x=b[i];
  102.             if(x%3==1)
  103.             {
  104.                 x+=2;
  105.             }
  106.             else
  107.             if(x%3==2)
  108.             {
  109.                 x+=1;
  110.             }
  111.             ans=(ans*power(prime[i],x))%mod;
  112.         }
  113.         for(i=0;i<prime2.size();i++)
  114.         {
  115.             LL x=b2[i];
  116.             if(x%3==1)
  117.             {
  118.                 x+=2;
  119.             }
  120.             else
  121.             if(x==2)
  122.             {
  123.                 x+=1;
  124.             }
  125.             ans=(ans*power(prime2[i],x))%mod;
  126.         }
  127.  
  128.         for(i=0;i<n;i++)
  129.         {
  130.             if(a[i]>1)ans=(ans*power(a[i],3))%mod;
  131.         }
  132.         cout<<ans<<endl;
  133.     }
  134. }
  135.  
Success #stdin #stdout 0.04s 11056KB
comments (?)
stdin
copy 
2
2
2 2
2
2 3
stdout
copy 
8
216
https://ideone.com/niPoP8
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!