TopCoder SRM 628 Div1 Easy DivisorsPower

SRM628に参加。
せっかくMediumを結構な速度で解いたのに、Easyでまたもしょうもないミス。
Medium正解者の多さもありレートがちょっと減った。
http://community.topcoder.com/stat?c=problem_statement&pm=13241

問題

正の整数xの約数の数をd(x)とする。
関数h(x)=x^d(x)を考える。

整数Nに対するhの逆関数適用、すなわちh(P)=P^d(P)=NとなるPを答えよ。

解法

Pの候補を総当たりすればよい。
総当たりには以下の方法がある。

• y=2～63に対しx^y==Nとなるxを求め、d(x)=yとなるかチェック。
• N<=10^18なので、x=1～10^6に対しy>=2、x^y==Nとなるxを求め、d(x)=yとなるかチェック。y==2の場合を考えx=√N周辺も探索する。

Nが大きいので、x^yの計算でオーバーフローしないよう注意。
というか自分はこれでやらかした。

class DivisorsPower {
	public:
	int enumdiv(ll n) {
		int ret=0;
		for(ll i=1;i*i<=n;i++) if(n%i==0) ret+=1+(i*i!=n);
		return ret;
	}

	long long findArgument(long long n) {
		ll mat=1LL<<60;
		double sq=sqrt(n);
		
		for(ll x=sq-3;x<=sq+3;x++) if(x>=2 && x*x==n && enumdiv(x)==2) mat=x;
		
		for(ll x=2;x<=1000000;x++) {
			ll y=x,pp=1;
			while(y*x<=n && y*x/x==y) y*=x,pp++;
			if(y!=n || pp==1) continue;
			if(pp==enumdiv(x)) mat=min(mat,x);
		}
		
		if(mat>=1LL<<60) return -1;
		return mat;
	}
}

まとめ

せっかく早解きしてもこういう凡ミスで落とすのもったいない。