[中譯] ProjectEuler 509 Divisor Nim

作者: tml (流刑人形)   2015-04-16 06:00:00
509. Divisor Nim
https://projecteuler.net/problem=509
Anton和Bertrand很喜歡玩三堆的Nim遊戲(註)。
然而,玩了太多場後,他們終究是感到厭煩了。所以,他們改變了一下規則。
在決定從一堆石頭中取走多少顆時,他們只能取該堆石頭總數的因數,但不能全取。
例如:如果有一堆石頭在某一時刻有24顆時,玩家只能取1,2,3,4,6,8或12顆石頭。
不難得知,當一堆石頭被拿到只剩一顆時,是無法再被取走的。
當有玩家無法進行任何行動時,他就輸了。
當然,Anton和Bertrand都會採取最佳策略來進行遊戲。
令(a,b,c)代表這三堆石頭的個數。
令S(n)表示在所有1≦a,b,c≦n的情況中,先手必勝的配置數。
S(10) = 692以及S(100) = 735494。
請求出S(123456787654321)對1234567890的餘數。
註:Nim遊戲是一種兩個人玩的回合制數學戰略遊戲。遊戲者輪流從一堆棋子
(或者任何道具)中取走一個或者多個,最後不能再取的就是輸家。當指
定相應數量時,一堆這樣的棋子稱作一個Nim堆。(by wiki)
http://zh.wikipedia.org/zh-tw/%E5%B0%BC%E5%A7%86%E6%B8%B8%E6%88%8F

Links booklink

Contact Us: admin [ a t ] ucptt.com