fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4.  
  5. #define first ff
  6. #define second ss
  7. #define make_pair mp
  8.  
  9. using namespace std;
  10.  
  11. const int maxN = 20005;
  12. const long long mod = 1000000007;
  13. int n, k, a[maxN], b[maxN], x[10011],prime[10011]; vector<vector<int> > v; vector<int> w, p;
  14.  
  15. void primes(){
  16.   int i,max = 10010,j;
  17.   for(i=0;i<max;i++){
  18.     x[i] = 1;
  19.   }
  20.   k=0;
  21.   for(i=2;i<max;i++){
  22.     if(x[i]){
  23.       prime[k] = i;
  24.       for(j=i;j<max;j+=i){
  25. 	x[j] = 0;
  26.       }
  27.       k++;
  28.     }
  29.   }
  30. }
  31.  
  32. long long modpow(int a, int b){
  33.   if(b==0){
  34.     return 1;
  35.   }
  36.   if(b==1){
  37.     return a;
  38.   }
  39.   long long ans = modpow(a,b/2);
  40.   ans = (ans *ans)%mod;
  41.   if(b%2){
  42.     ans = (ans*a)%mod;
  43.   }
  44.   return ans;
  45. }
  46.  
  47. int main(){
  48.   ios_base::sync_with_stdio(false);
  49.   int tt,i;
  50.   primes();
  51.   cin>>tt;
  52.   while(tt--){
  53.     v.clear(); p.clear();
  54.     int mx = -1;
  55.     cin>>n;
  56.     for(i=0;i<n;i++){
  57.       cin>>a[i]; b[i] = a[i]; mx = max(mx,a[i]);
  58.     }
  59.     int t,j=0, ct =0; long long temp, ans=1;
  60.     while(prime[j]*prime[j] <= mx){
  61.       w.clear();
  62.       mx = -1;
  63.       for(i=0;i<n;i++){
  64. 	t=0;
  65. 	if(b[i]%prime[j] == 0){
  66. 	  while(b[i]%prime[j] == 0){
  67. 	    t++; b[i]/=prime[j];
  68. 	  }
  69. 	  w.push_back(t);
  70. 	}
  71. 	mx = max(mx,b[i]);
  72.       }
  73.       if(!w.empty()){
  74. 	p.push_back(prime[j]);
  75. 	v.push_back(w);
  76. 	ct++;
  77.       }
  78.       j++;
  79.     }
  80.     t = 0;
  81.     for(i=0;i<ct;i++){
  82.       sort(v[i].begin(),v[i].end());
  83.       t = 0;
  84.       for(j=0;j<v[i].size()-1;j++){
  85. 	t+=v[i][j];
  86.       }
  87.       if(t >= v[i][j]){
  88. 	t+=v[i][j];
  89. 	if(t%2 == 1){
  90. 	  ans = (ans * p[i])%mod;
  91. 	}
  92.       }
  93.       else{
  94. 	t = v[i][j] - t;
  95. 	ans = (ans * modpow(p[i],t))%mod;
  96.       }
  97.  
  98.     }
  99.     sort(b,b+n); b[n] = -1;
  100.     for(i=0;i<n;i++){
  101.       t = 1;
  102.       if(b[i]!=1){
  103. 	j = b[i];
  104. 	if(b[i] == b[i+1]){
  105. 	  while(b[i] == b[i+1]){
  106. 	    t++; i++;
  107. 	  }
  108. 	}
  109. 	if(t%2 == 1){
  110. 	  ans = (ans * j)%mod;
  111. 	}
  112.       }
  113.     }
  114.     cout<<ans<<"\n";
  115.   }
  116.   return 0;
  117. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
	
5 3
2 3 4 5 4
3 4 2 3 2
compilation info 
prog.c:1:19: fatal error: iostream: No such file or directory
 #include<iostream>
                   ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/DBWvbk
language:
C (gcc 8.3)
created:
6 years ago
visibility:
public

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!