[yukicoder] No.7 プライムナンバーゲーム [レベル: 2]
Groudy数
問題
解説記事を読むとこのような問題はGroudy数というようです。
考え方
以下の素数の配列
を昇順にならべて用意します。
から
まで順番に先手が勝つか後手が勝つかを記録していきます。
この勝敗の配列を とし0勝ち、1を負けとします。この配列の初期値は1としておきます。例えば、
、
、
となっています。
次に、 を計算し、
となる
が存在すれば先手が勝ちとなります。つまり、
です。
上記以外の場合、 となる
が存在すれば先手が勝ちになります。これは、
を調べる時点で、
以下の数の勝敗が分かっているので、
ということは、先後が入れ替わり、後手が
からゲームをやるということです。つまり、後手が負けることを意味します。
上記以外の場合は、後手が勝ちます。
正直、解説があっているどうか自信がないですが、コードは正解となりました。レベル2ということもあり、難しかったです。
