UVA 10622 - Perfect P-th Powers

题意：求n转化为b^p最大的p值

思路：对n分解质因子，然后取全部质因子个数的gcd就是答案，可是这题有个坑啊。就是输入的能够是负数，负数的情况比較特殊，p仅仅能为奇数。这时候是要把答案不断除2除到为奇数就可以。

代码：

#include 
     
      #include 
      
       #include 
       
        long long n;int prime[333333], vis[333333], m = 0;int gcd(int a, int b) {	if (b == 0) return a;	return gcd(b, a % b);}int solve() {	long long nn = n;	if (n < 0) n = -n;	int ans = 0;	for (int i = 0; i < m && prime[i] <= n; i++) {		int count = 0;		while (n % prime[i] == 0) {			count++;			n /= prime[i];  		}  		ans = gcd(ans, count); 	}  	if (ans == 0) ans = 1; 	if (nn < 0) { 		while (ans % 2 == 0) {  			ans /= 2;				}  	} 	return ans;}int main() {	for (int i = 2; i < 333333; i++) {		if (vis[i]) continue;		prime[m++] = i;		for (int j = i; j < 333333; j += i) {			vis[j] = 1;		} 	}	while (~scanf("%lld", &n) && n) {		printf("%d\n",  solve()); 	}	return 0;}