UVa - 10622 - Perfect P-th Powers

10622.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define endl '\n'
#define PB push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int oo = ~(1<<31);

const int MAX = 1e7;
bool sieve[MAX];

vi primes;

void build() {

    for(ll i = 2; i < MAX; i++) {
        if(sieve[i]) continue;

        for(ll j=i*i; j<MAX; j+=i)
            sieve[j] = true;

        primes.PB((int)i);
    }
}

map<int, int> factor(ll n) {
    map<int, int> A;
    int idx = 0;

    while(n > 1 && idx < primes.size()) {
        while(n % primes[idx] == 0) {
            A[primes[idx]]++;
            n /= primes[idx];
        }
        idx++;
    }

    if(n > 1) A[n]++;

    return A;
}

int sol(map<int, int> &F) {
    int gcd = 0;

    for(auto ol : F)
        gcd = __gcd(gcd, ol.S);

    return gcd;
}

int main() {
    #ifndef CBDAVIDES
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    #endif

    build();

    ll n;
    while(cin >> n && n) {

        map<int, int> F = factor(n < 0 ? -n : n);

        int s = sol(F);
        if(n < 0 && s & 1) cout << s << endl;
        else if(n < 0 && s > 1){
            while(s > 1 && s % 2 == 0) s /= 2;
            cout << s << endl;
        }
        else if(n > 0) cout << s << endl;
        else cout << 1 << endl;

    }

    return 0;
}