fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. const long long mod=1e9+7;
  6. int m, maxn,p; long long fp,prdt=1,d=1;
  7. vector<long long> cnt(2e5+1); // prime factors less than 2*10^5
  8.  
  9. long long modpow(long long a, long long x){
  10. 	long long e=1;
  11. 	while(x){
  12. 		if(x&1) e=e*a%mod;
  13. 		a=a*a%mod; x>>=1;
  14. 	}
  15. 	return e;
  16. }
  17. int main(){
  18. 	cin>>m;  for(int i=1; i<=m; ++i) cin>>p, ++cnt[p], maxn=max(maxn,p);
  19. 	// Calculate product of divisors of a number from a given list of its prime factors
  20. 	/* EXAMPLE:
  21. 	   (a^x * b^y * c^z * d^t)^(x+1)(y+1)(z+1)(t+1)
  22. 	  =  a^(x(x+1)/2 * (y+1)(z+1)(t+1))
  23. 	   * b^(y(y+1)/2 * (x+1)(z+1)(t+1))
  24. 	   * c^(z(z+1)/2 * (x+1)(y+1)(t+1))
  25. 	   * d^(t(t+1)/2 * (x+1)(y+1)(z+1))
  26. 	*/
  27. 	for(int num=2; num<=maxn; ++num)  if(cnt[num]){
  28.  
  29. 		// For a prime p raised to the pow a, f(p^a) = p^(a(a+1)/2)
  30. 		fp = modpow(num, cnt[num]*(cnt[num]+1)/2) % mod;
  31.  
  32. 		// f(a*b) = f(a^d(b)) * f(b^d(a))
  33. 		// where d(a), d(b) denotes the num of div in a & b
  34. 		prdt = modpow(prdt, cnt[num]+1) * modpow(fp,d) % mod;
  35.  
  36. 		// The num of div d updated using Fermat’s Little Theorem:
  37. 		// a^(m–1) = 1 (mod m), extended to a^x = a^(x % (m–1)) (mod m)
  38. 		d = d * (cnt[num]+1) % (mod-1);
  39. 	}
  40. 	return cout<<prdt, 0;
  41. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
2
2 3
stdout
copy 
36
https://ideone.com/yF0Jnx
language:
C++14 (gcc 8.3)
created:
5 days 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!