Perfect Pth Powers（唯一分解定理）

UVA10622

由唯一分解定理，将$n$分解后求每个素数项对应的指数的最小公约数即可。
虽然$n$在int范围内，但仍要long long，因为int的负数的绝对值比整数大1。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;


int gcd(int a, int b) {
	while (b) {
		int temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}

int Compute(long long n) {

	bool IsNegetive = false;
	if (n < 0) {
		n = -n;
		IsNegetive = true;
	}

	int Ans = 0;

	const int MAX = ceil(sqrt(static_cast<double>(n)));
	for (int i = 2; i <= MAX; ++i) {
		if (n % i == 0) {
			int Temp = 0;
			while (n % i == 0) {
				n /= i;
				++Temp;
			}
			Ans = gcd(Temp, Ans);
		}
	}

	if (Ans == 0) {
		return 1;
	}

	if (IsNegetive) {
		while ((Ans & 1) == 0) {
			Ans >>= 1;
		}
	}
	return Ans;
}

int main() {
	long long n;
	while (~scanf("%lld", &n) && n) {
		printf("%d\n", Compute(n));
	}

	return 0;

}