問題:No.7 プライムナンバーゲーム - yukicoder
解答:#487788 (C++14) No.7 プライムナンバーゲーム - yukicoder
解法:先手番の時、先手で「後手必勝」の局面に遷移する手があれば先手の勝ち、そうでなければ後手の勝ち。
dp[i] : iの時先手必勝なら1, 後手必勝なら0とする。各iについてそこから遷移できるj (j + p = i, p:素数) についてdp[j] = 0のものが1つでもあればdp[i] = 1、そうでなければdp[i] = 0とする。