POJ 1730 Perfect Pth Powers

問題

整数Xが与えられる。X=b^pを満たすような整数bおよび自然数pが存在するとき、Xをp-th perfect numberという。pの最大値を求めよ。
制約:

やりかた

例えばなのでmax(p)=4となるように、Xを素因数分解して、各素因数の指数の最大公約数が答えになる。答えはせいぜい31以下なので、31以下の自然数pを大きい方から試して、素因数の指数が全部pで割り切れるような初めてのpを出力すればいい。
入力が負の数をとりうるので要注意。

以下ソース。

map<ll, int> pf(ll n){
  map<ll, int> p;
  for(ll i = 2; i * i <= n; i++){
    while(n % i == 0){
      p[i]++;
      n /= i;
    }
  }
  if(n != 1) p[n]++;
  return p;
}
int main(int argc, char **argv){
  ll n;
  while(cin >> n, n){
    map<ll, int> pr = pf(n < 0 ? -n : n);
    for(int p = 32; p >= 1; p--){
      bool check = true;
      map<ll, int>::iterator it = pr.begin();
      for(; it != pr.end(); it++){
	ll power = it->second;
        //pでべき乗数を割り切れないか、割り切れるけど正負が合わない場合は失敗とする
	if(power % p != 0 || (n < 0 && p % 2 == 0)) check = false;
      }
      if(check){
	cout << p << endl;
	break;
      }
    }
  }
  return 0;
}

負数の入力があることにしばらく気づかなかった。