UVa 10622 - Perfect P-th Powers

// UVa 10622 - Perfect P-th Powers

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <math.h>
#include <cmath>
using namespace std;

#define integer signed long long
#define max_prime 100000

bool isprime[max_prime];
vector<int> prime;

int gcd(int a, int b) {
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}

int main() {
	// sieve
	memset(isprime, true, sizeof(isprime));
	for (int i = 4; i < max_prime; i += 2)
		isprime[i] = false;
	prime.push_back(2);
	for (integer i = 3; i < max_prime; i += 2) {
		if (isprime[i]) {
			prime.push_back(i);
			for (integer j = i * i; j < max_prime; j += (i << 1))
				isprime[j] = false;
		}
	}

	// problem
	while (true) {
		integer n;
		cin >> n;
		if (n == 0)
			break;
		integer m = abs(n), sol = 1;
		bool first = true;
		for (int i = 0; i < prime.size(); i++) {
			int e = 0;
			while (m % prime[i] == 0) {
				m /= prime[i];
				e++;
			}
			if (e > 0) {
				if (first) {
					sol = e;
					first = false;
				} else
					sol = gcd(sol, e);
				if (sol == 1 || m == 1)
					break;
			}
		}
		if (m != 1)
			sol = 1;
		if (n < 0) {
			while ((sol & 1) == 0)
				sol >>= 1;
		}
		cout << sol << endl;
	}
	return 0;
}