yukicoder No.2 素因数ゲーム

整数Nを(2の因数の数,3の因数の数,…)という組と見れば、山崩しゲームとなる。
具体的には
「素因数を1つ選ぶ」が「山を1つ選ぶ」と
「好きな回数だけ割る」が「好き個数だけ取る」と対応する

山崩しゲームの必勝法は有名で
全ての山の石の数のbitxorが0なら後手必勝
さもなくば先手必勝である

ということで、素因数分解して各山の石の個数を求めればよい

int main(){
	int s,t,n,i;
	s=0;
	scanf("%d",&n);
	for(i=2;i<=n;i++){
		for(t=0;n%i==0;){
			n/=i;
			t++;
		}
		s^=t;
	}
	puts(s?"Alice":"Bob");
	return 0;
}

これに単純なループ圧縮を行って93B

s,t,i=2;
main(n){
	for(scanf("%d",&n);n%i?s^=t,t=0,n>i++:(t++,n/=i););
	s=!puts(s?"Alice":"Bob");
}

16/04/23追記
山崩しがbitxorで必勝であることの証明をしろと言われた気がしたので証明
（以下簡単のため、単に「山」と言って「山の石の個数」のことも指したりする）

「現在の全ての山に渡るbitxorが0なら、そこから相手がどの山を選んでいくつ石を取り除いても、自分の手番で再び0に戻すことができる」
ということを示せば十分。なぜならこれにより山の石の合計は真に小さくなるため帰納的に示されるからである。
１．相手の手番後は、すべての山に渡るbitxorは必ず非0である
もともとx個の石があった山から相手が石を取り除きy個になった場合、残りの山のbitxorはxであることから
操作後には x bitxor y≠0となる
２．自分の手番でbitxorを0にすることができる
相手の手番後には全ての山に渡るbitxorの結果Aは非0なので、Aの1が立っているbitのうち最上位のものを下からNbit目であるとする
Nbit目が1であるような山を1つ選びその石の数をx、この山以外のbitxorをyとする
このとき x bitxor y == A なので、xとyはNbit目より上に関しては一致し、かつ、Nbit目はxが1でyが0なのでx>yとなる
よってこの山からいくつか石を除くことでy個にでき、すべての山に渡るbitxorが y bitxor yで0となる

メモ

yukicoderでゆるふわgolf

yukicoder No.2 素因数ゲーム