Problem 560 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 560 へ行く。
• Problem 560 の差分を削除

#author("2024-01-12T02:46:44+00:00","","")
*[[Problem 560:http://projecteuler.net/problem=560]] 「互いに素なニム」 [#u97c0035]

Coprime Nim はニムゲームであり、「山から取り除く石の個数は、その山の石の個数と互いに素でなければならない」という条件がついている。2人のプレイヤーが交互に石を取り除き、最後の石を取り除いた方が勝ちである。

1 個以上 n-1 個以下の石の山が k 個ある状態のうち、互いに最善手を尽くしたときに先手が負けるものの個数を L(n,k) とする。

例えば L(5,2)=6 である。各山の石の個数が (1,1),(2,2),(2,4),(3,3),(4,2),(4,4) であったときに先手の負けとなる。

L(10,5)=9964, L(10,10)=472400303, L(&tex{10^{3}};, &tex{10^{3}};) mod 1 000 000 007 = 954021836 である。

L(&tex{10^{7}};, &tex{10^{7}};) mod 1 000 000 007 を求めよ。

IP:207.65.235.4 TIME:"2024-01-12 (金) 11:46:44" REFERER:"https://odz.sakura.ne.jp/projecteuler/" USER_AGENT:"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/120.0.0.0 Safari/537.36"