SHARE
TWEET

Untitled

a guest May 21st, 2017 511 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top