题目链接：
LightOJ 1220 Mysterious Bacteria
题意：
给一个三十二位有符号整数n求满足a^p = n的最大p。
分析：
一开始没注意到 within the range of a 32 bit signed integer.中的signed无限WA。。。
也就是可以有负数情况的。对于正数n只要对n进行质因子分解，然后在所有质因子的幂中找gcd即可。
对于负整数n需要考虑质因子的幂为偶数的情况，因为得到的质因子实际上是它的相反数，如果是偶数次幂的话得到的是正数，所以需要将偶数次幂除以2找到把幂变为奇数。例如对于-16，分解质因子得到2和幂次4.需要将4/2得2，再除以2得1，所以答案就是1.然而对于n = -32来说，就不用了，因为得到2的幂次是5是个奇数，答案就是5.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 100010;int T, cases = 0;
int factor_num[MAX_N], total, prime_cnt;
ll n, prime[MAX_N], factor[MAX_N];
bitset<MAX_N> bs;void GetPrime()
{bs.set();prime_cnt = 0;for(int i = 2; i < MAX_N; i++){if(bs[i] == 1) prime[prime_cnt++] = i;for(int j = 0; j < prime_cnt && i * prime[j] < MAX_N; j++){bs[i * prime[j]] = 0;if(i % prime[j] == 0) break;}}
}void Factor(ll x)
{total = 0;for(int i = 0; i < prime_cnt && prime[i] * prime[i] <= x; i++){if(x % prime[i] == 0){int tmp = 0;while(x % prime[i] == 0){tmp++;x /= prime[i];}factor[total] = prime[i];factor_num[total++] = tmp;}}if(x > 1){factor[total] = x;factor_num[total++] = 1;}
}int gcd(int a, int b)
{return b == 0 ? a : gcd(b, a % b);
}int main()
{GetPrime();scanf("%d", &T);while(T--){scanf("%lld", &n);Factor(labs(n));if(n < 0){for(int i = 0; i < total; i++){while(factor_num[i] % 2 == 0) factor_num[i] /= 2;}}int ans = factor_num[0];for(int i = 1; i < total; i++){ans = gcd(ans, factor_num[i]);}printf("Case %d: %d\n", ++cases, ans);}return 0;
}