Codeforces #426 Div1 A. The Meaningless Game

突出した出来ではなかったつもりだけど、罠が多かったのかABCをのんびり解いたらだいぶレートが上がった。
http://codeforces.com/contest/833/problem/A

問題

以下のクエリにQ個答えよ。

2人であるゲームを行う。
このゲームは何ラウンドかで構成され、毎回2以上の整数kを定め勝者はk^2、敗者はkのスコアを得る。
総スコアA,Bが与えられたとき、その総スコアが実現することはありうるか判定せよ。

解法

クエリ数が多いため、A,Bをそれぞれ素因数分解すると間に合わない。
いくつか方法があるようだが、自分は以下のように解いた。

• 1回のラウンドで両者のスコアの積はk^3倍になる。よって総スコアの積が立方数になることを確認する。
• ある素数pに対しAはp^a、Bはp^bを約数に持つなら、aとbは互いに互いの倍以下の値になるはずである。
  • よって、A^2はBの倍数であり、B^2はAの倍数となることを確認すればよい。

int N;
int A,B;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%d%d",&A,&B);
		
		ll X=A,Y=B;
		
		if(X*X%Y!=0 || Y*Y%X!=0) {
			_P("NO\n");
			continue;
		}
		X*=Y;
		
		ll a=0;
		for(j=20;j>=0;j--) {
			ll b=a+(1LL<<j);
			if(b*b*b<=X) a=b;
		}
		if(a*a*a==X) {
			_P("YES\n");
		}
		else {
			_P("NO\n");
		}

	}
}

まとめ

自分以外にも素因数分解しまくって1WA食らった人多そうね。