yukicoder : No.2 素因数ゲーム

yukicoderの問題を一通り解いたので、☆３つ以上の問題のみここで記載。
http://yukicoder.me/problems/18

問題

２人で交互にターンが来るゲームを行う。
整数Nに対し、１回のターンで１種類の素因数で任意回数割ることができる。
自分のターンで整数を1にした方が勝ちである。

両者が最適手を取った場合、先手後手どちらが勝つか。

解法

各素因数を１つの石の山、素因数の指数を石の数とみなしたNimである。
よってNを素因数分解したのち、指数のxorを取ればよい。

ll N;

map<ll,int> enumdiv(ll n) {
	map<ll,int> V;
	if(n==1) V[1]=1;
	else {
		for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
		if(n>1) V[n]++;
	}
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<ll,int> M=enumdiv(N);
	x=0;
	ITR(it,M) x^=it->second;
	if(x==0) cout << "Bob" << endl;
	else cout << "Alice" << endl;
	
}

まとめ

ここらへんは典型的なNim問題。