fork download 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. #define w(t) ll t;cin>>t;while(t--)
  4. #define f(i,a,b) for(ll i=a;i<b;i++)
  5. #define scana(arr) for(ll i=0,i<n;i++) cin>>arr[i];
  6. #define vl vector<ll>
  7. #define vpl vector< pair<ll,ll> >
  8. #define pb push_back
  9. #define mod 1000000007
  10. using namespace std;
  11. bitset<10000000> b;
  12. vl primes,factors;
  13.  
  14. void sieve(){
  15. 	b[0]=b[1]=1;
  16. 	b.set(); //sets all the bits as 1	
  17. 	for(long long int i=2;i<=10000000;i++){
  18. 		if(b[i]){
  19. 			primes.push_back(i);
  20. 			for(long long int j=i*i;j<=10000000;j+=i){
  21. 				b[j]=0;	
  22. 			}
  23. 		}
  24. 	}
  25. }
  26.  
  27. void prime_factors_sieve_approach(ll n){
  28.     ll count=0;
  29.     for(ll i=0;i<primes.size();i++){
  30.         ll x=primes[i];
  31.         if(x*x>n) break;
  32.         if(n%x==0){
  33.             if((n/x)==x) factors.pb(x);
  34.             else{
  35.                 factors.pb(x);
  36.                 factors.pb(n/x);
  37.             }
  38.         }
  39.     }
  40.     factors.pb(n);
  41. }
  42.  
  43. ll prime_factors_util(ll n){
  44.     ll count=0,divisors=1;
  45.     for(ll i=0;i<primes.size();i++){
  46.         ll x=primes[i];
  47.         if(x*x>n) break;
  48.         if(n%x==0){
  49.             count=0;
  50.             while(n%x==0){
  51.                 n/=x;
  52.                 count++;
  53.             }
  54.             divisors*=((count+1)%mod);
  55.         }
  56.     }
  57.  
  58.     if(n!=1) divisors=((divisors)%mod*(2)%mod)%mod;
  59.     divisors%=mod;
  60.     return divisors%mod;
  61. }
  62.  
  63. ll fast_modulo_exponentation(ll a,ll b){
  64.     ll ans=1;
  65.     while(b){
  66.         if(b&1){
  67.             ans=((ans%mod)*(a%mod))%mod;
  68.         }
  69.         a=((a%mod)*(a%mod))%mod;
  70.         b>>=1;
  71.     }
  72.     ans%=mod;
  73.     return ans%mod;
  74. }
  75.  
  76. int main(){
  77.     sieve();
  78.     ll n;
  79.     cin>>n;
  80.     ll arr[n];
  81.     ll N=1,divisors=1;
  82.     f(i,0,n){
  83.         cin>>arr[i];
  84.         N=((N%mod)*(fast_modulo_exponentation(primes[i],arr[i])%mod))%mod;
  85.         divisors*=(arr[i]+1);
  86.     }
  87.  
  88.     ll P=fast_modulo_exponentation(N,divisors/2);
  89.     ll ans=prime_factors_util(P);
  90.     cout<<ans%mod<<endl;    
  91.  
  92.     return 0;
  93. }
Runtime error #stdin #stdout 0.07s 13680KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/TlQ0xb
language:
C++ (gcc 8.3)
created:
4 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!