题目连接：uva 10622 - Perfect P-th Powers

题目大意：对于x，如果存在最大的p，使得有整数满足x=bp,则称x为perfect pth power。现在给出x，求p。

解题思路：将x分解质因子，所有置因子的个数的最大公约数即为所求p，需要注意的是x为负数的时候，p必须为奇数。特别注意x=-1。

#include 
   
     #include 
    
      #include 
     
       const int maxp = 333333; int cp, v[maxp], prime[maxp]; int gcd (int a, int b) { return b == 0 ? a : gcd(b, a%b); } void primeTable (int n) { memset(v, 0, sizeof(v)); cp = 0; for (int i = 2; i < n; i++) { if (!v[i]) { prime[cp++] = i; for (int j = 2 * i; j < n; j += i) v[j] = 1; } } } int divFactor (long long n) { int ans = 0; for (int i = 0; i < cp && prime[i] <= n; i++) { if (n % prime[i] == 0) { int cnt = 0; while (n % prime[i] == 0) { n /= prime[i]; cnt++; } ans = gcd(ans, cnt); } } if (n > 1 || ans == 0) ans = 1; return ans; } int main () { primeTable(maxp); long long n; while (scanf("%lld", &n) == 1 && n) { int ans = divFactor(n < 0 ? -n : n); if (n < 0) { while (ans%2 == 0) ans /= 2; } printf("%d\n", ans); } return 0; }