SRM575 Div1 Easy - TheNumberGameDivOne

わかりませんでした😠
ゲーム系のeasyにしてはむずくない？

問題

自然数nがある
2人が交互にnから「1とn以外のnの約数」を引き、操作を行えなくなった方が負ける
どちらが勝つか判定せよ

1 <= n <= 10^18

解法

nが奇数 or 2の奇数乗なら後手、それ以外は先手が勝つ
このゲームは素数を渡されたら負けってことになる
素数は2以外は全部奇数なことに注目する

○nが奇数のとき
そもそもnが素数の場合は先手が即負け
そうじゃない場合、nはどんな操作をしても「2の累乗ではないような偶数」になる
(何かしらの操作によってnを2の累乗にできると仮定するとnは2の累乗の倍数 → 偶数になるから矛盾)
そういう数字は必ず奇数の約数が存在するため、返しのターンで後手が奇数にして返せる
よって何度繰り返しても先手には奇数が返ってきて、いつかはそれが素数になる

○nが2のp乗のとき
このnに操作を行うと「2の累乗」or「2の累乗でない偶数」のどちらかを作れる
↑の通り後者を相手に渡すと負けるから前者を選び続けるしかない
前者にするってのはnをn/2に変えるってことで、そうするとターン数はpターンになる
よってpが奇数なら負け、偶数なら勝ち

class TheNumberGameDivOne {
public:
	string find(ll n) {
		if (n%2) return "Brus";
		rep(i,60) if (i%2 && n==(1ll<<i)) return "Brus";
		return "John";
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12496&rd=15495