Guest User

Untitled

a guest
May 21st, 2017
655
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. #define pb push_back
  6. #define MOD 1000000007
  7.  
  8.  
  9. // Fast-Exponentiation
  10. ll power(ll a, ll b){
  11. if (b == 0) return 1;
  12. if (b == 1) return a;
  13. if (b%2 == 1) return (a*power(a,b-1))%MOD;
  14. ll x = power(a,b/2)%MOD;
  15. return (x*x)%MOD;
  16. }
  17.  
  18. int main() {
  19.  
  20. ios::sync_with_stdio(false);
  21.  
  22. // Storing all primes
  23. vector<ll> primes;
  24. primes.pb(2);
  25. for (int i = 3; i < 31625; i += 2){
  26. for (int j = 0; j < primes.size(); j++){
  27. if (i%primes[j] == 0) break;
  28. if (primes[j]*primes[j] > i){
  29. primes.pb(i);
  30. break;
  31. }
  32. }
  33. }
  34.  
  35. // Calculating Prime-Factors
  36. int n;
  37. cin >> n;
  38. ll x;
  39. map<ll,ll> mp;
  40. for (int i = 0; i < n; i++){
  41. cin >> x;
  42. for (int j = 0; j < primes.size(); j++){
  43. while (x % primes[j] == 0){
  44. x /= primes[j];
  45. mp[primes[j]] ++;
  46. }
  47. if (x == 1) break;
  48. }
  49. if (x > 1) mp[x] ++;
  50. }
  51.  
  52. // Calculating the answer
  53. bool justdoit = true;
  54. ll ans = 1;
  55. for (auto it = mp.begin(); it != mp.end(); it++){
  56. ll a = it->first;
  57. ll b = it->second;
  58. if (b%n != 0){
  59. justdoit = false;
  60. }
  61. if (b%(n+1) != 0){
  62. ans *= power(a,n+1-(b%(n+1)));
  63. ans %= MOD;
  64. }
  65. }
  66. if (justdoit) cout << "justdoit\n";
  67. else cout << ans << endl;
  68. }
RAW Paste Data