POJ 1730 Perfect Pth Powers (分解素因子)

题目链接：http://poj.org/problem?id=1730 题目大意：给定a，要求a = b ^ p，求可能的最大的p. 思路： 思路很好想，分解素因子并且统计每个素因子的个数，再求所有个数的最大公约数即可. 但还是很恶心的错了很多次……主要是没注意一下几点： ①.题目数据有负数(= =……)，负数的话按正数处理，但需注意负数的p一定是奇数，所以如果求出来的p不是奇数，需一直减半直到为奇数。比如(-64) != 6，而是(-64) = 3. ②.数据中有1<<31，因为int最大能表示1<<31-1，所以需要特判一下，或者用long long. ③.在分解质因数时如果直接for (int i = 2; i * i <=n; i ++)这样枚举会超时，需要预处理打出1<<16的素数表优化一下. ④.C++默认的整数数据类型是int,所以直接 1<<31 的结果不是2147483648，注意用1LL << 31 (LL表示long long类型).  

#include 
#include 
using namespace std;
vector  > p;
vector  prime;
bool vis[70000];
void Prime(){
    for (int i = 2; i <= 66000; i ++){
        if (!vis[i]){
            prime.push_back(i);
            int p = i + i;
            while(p <= 66000){
                vis[p] = 1;
                p += i;
            }
        }
    }
}
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
int solve(int n){
    if (n == 1)
        return 1;
    p.clear();
    for (size_t w = 0; w < prime.size(); w ++){
        int i = prime[w];
        if (i > n)
            break;
        int num = 0;
        while(n % i == 0){
            num ++;
            n /= i;
        }
        if (num != 0){
            p.push_back(make_pair(i, num));
        }
        if (n == 1)
            break;
    }
    if (n > 1){
        p.push_back(make_pair(n, 1));
    }
    int t = p[0].second;
    for (size_t i = 1; i < p.size(); i ++){
        t = gcd(t, p[i].second);
    }
    return t;
}
int main(){
    Prime();
    long long n;
    while(cin >> n){
        if (n == 0){
            return 0;
        }
        if (n > 0){
            if(n == (1LL << 31)){
                cout << 31 <