SRM575 Div1 Easy - TheNumberGameDivOne
わかりませんでした😠
ゲーム系のeasyにしてはむずくない?
解法
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