Description

Problem E: Perfect Pth Powers

We say that

x is a perfect square if, for some integer

b,

x = b^2. Similarly,

x is a perfect cube if, for some integer

b,

x = b^3. More generally,

x is a perfect p

thpower if, for some integer

b,

x = b^p. Given aninteger

x you are to determine the largest

p such that

xis a perfect p

th power.

Each test case is given by a line of input containing x.The value of x will have magnitude at least 2 and be within therange of a (32-bit) int inC, C++, and Java. A line containing 0 follows the last test case.

For each test case, output a line giving the largest integer p such that x isa perfect pth power.

Sample Input

171073741824250

Output for Sample Input

1302

题意：求x=b^p,的 最大的p

思路：首先将n分解质因数，然后找因数个数的gcd就是了，负数的话，一直除以2。直到答案是奇数的时候

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          typedef long long ll;using namespace std;const int maxn = 333333;ll n;int prime[maxn], vis[maxn], cnt = 0;int gcd(int a, int b) {	return b==0?a:gcd(b, a%b);}int solve() {	ll tmp = n;	if (n < 0)		n = -n;	int ans = 0;	for (int i = 0; i < cnt && 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 (tmp < 0) {		while (ans % 2 == 0)			ans /= 2;	}	return ans;}int main() {	for (int i = 2; i < maxn; i++) {		if (vis[i])			continue;		prime[cnt++] = i;		for (int j = i; j < maxn; j += i)			vis[j] = 1;	}	while (scanf("%lld", &n) != EOF && n) {		printf("%d\n", solve());	}	return 0;}