SRM575 Div1 Easy "TheNumberGameDivOne"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12496
訳
Div2 Mediumと同じ
制約
1 <= n <= 10^18
解法
n=100ぐらいまでの結果を出力して眺めて法則を探すと・・・
nが2の累乗の場合、指数が奇数の場合は負け。偶数なら勝ち
nが2の累乗でなければ、奇数なら負け。偶数なら勝ち
っぽいなと分かる。
証明してみる
数字が奇数だった場合、それを素因数分解すると、
2^0 * 3^a * 5^b * 7^c * 11^d *...となる。
よって約数は必ず奇数となり、
約数を引いたときに出来る数字は必ず偶数となる。
また、元の数字をC = 2^x + n (nは奇数)とすると、
この2^xはどんなnでも割り切れない。
そのため、Cはnの約数にはならないので、nを引いて2^xにすることは出来ない。
よって、約数を引いた後の偶数は2の累乗でない偶数であることがわかる。
2の累乗でない偶数には必ず奇数の約数があるため、
その約数を引けば、奇数にすることができる。
だから奇数→2の累乗でない偶数→奇数→2の累乗でない偶数...
となり、奇数は負け、2の累乗でない偶数は勝ちとなる。
数字が2の累乗であった場合、
数字から約数を引いたときにできる数字は
指数を1つ減らした2の累乗か、2の累乗でない偶数となる。
上記の通り、2の累乗でない偶数を渡すと負けてしまうので、
ゲームの流れは2^8→2^7→2^6→2^5→2^4→2^3→2^2→2^1となる。
2^1になれば負けなので、指数が奇数だったら負け、偶数だったら勝ちとなる。
事後
Div1の難しさが予想の斜め上をいってた
ソースコード
class TheNumberGameDivOne { public: string find(long long n){ bool firstWin; if( n % 2 ){ firstWin = false; }else{ long long m = 2; for( int i = 1; ; m *= 2, i++ ){ if( n == m ){ firstWin = i % 2 == 0; break; }else if( n < m ){ firstWin = true; break; } } } return firstWin ? "John" : "Brus"; } };