[中譯] ProjectEuler 366 Stone Game III
366. Stone Game III
http://projecteuler.net/problem=366
有兩個玩家，Anton 和 Bernhard，在玩一場遊戲。
這裡有一堆石頭，共 n 顆。
第一位玩家可以拿掉任何數量的石頭，但不能整堆拿走。
再來，每位玩家拿的石頭數量上限就是「對手最後拿取的數量 X 2」。
誰拿走最後一顆石頭，誰就獲勝。
舉個例子來說，這堆石頭有 5 顆。
如果第一位玩家拿了超過 1 顆石頭(2,3,4)，第二位玩家都能馬上拿走所有石頭並獲勝。
如果第一位玩家拿 1 顆，留下 4 顆，第二位玩家也拿 1 顆，留下 3 顆。
又換第一位玩家，但他至多只能拿 2 顆，所以不論拿 1 或 2 顆，第二位玩家都能獲勝。
所以 n = 5 是第一位玩家的必敗型。
有些必勝型對於第一位玩家有超過一種拿法，比如說 n = 17，可以先拿 1 或 4 顆。
使 M(n) 為必勝型中，第一位玩家第一步可拿取的石頭最大數量，而 M(n) = 0為必敗型。
ΣM(n)，n ≦ 100，答案是 728。
請算出 ΣM(n)，n ≦ 10^18 後再 mod 10^8 給出答案。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.4.237
推
01/08 17:19, , 1F
01/08 17:19, 1F
推
01/08 20:00, , 2F
01/08 20:00, 2F
→
01/08 20:00, , 3F
01/08 20:00, 3F