[中譯] ProjectEuler 325 Stone Game II

[babufong (嗶嗶)]

325. Stone Game II

http://projecteuler.net/index.php?section=problems&id=325


這遊戲的玩法是兩個人與兩堆石頭。

在她的回合，她從較大堆的石頭中移除掉一些石頭。

移除掉的石頭數量必須為較小堆石頭的正整數倍。


舉個例子，(6,14)表示為較小堆的石堆有6顆石頭，較大堆的石堆有14顆石頭

先手可以從較大堆的石堆中拿6或12顆石頭。


從某一堆拿走全部石頭的玩家就勝利。


必勝型指的是先手可以迫使局面成為先手勝利。例如：(1,5) , (2,6) 還有 (3,12)

都是必勝型，因為先手可以馬上移除掉較大堆的石堆中所有的石頭。


必敗型指的是後手可以迫使局面成為後手勝利，無論先手做了什麼動作。

例如：(2,3) 和 (3,4) 都是必敗型，先手任何合法動作皆會留下一個必勝型給後手。


定義 S(N) 為所有必敗型 (xi,yi) 且 0 < xi < yi <= N 中，(xi+yi) 的總和

我們可以知道 S(10) = 211 且 S(10^4) = 230312207313。


請算出 S(10^16) mod 7^10。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.1.79
推 LPH66:....我在家裡的一本數學書上看到這個玩法但已經忘了結論了QQ
推 jurian0101:Nim - 天文數字篇   (開學了，ProEuler掰掰~~~~)
→ jurian0101:<拈及其各種變形遊戲> http://goo.gl/wvGCP
推 utomaya:歐氏對局 http://tinyurl.com/4m4zzdl 裡面有公式
→ utomaya:不過這公式複雜度是O(N) 要算到S(10^16) 還要一點輔助
→ utomaya:我確定沒有別的公式了 這就是ProjectEuler賊的地方
→ utomaya:光靠公式 還不足以解出；；不然的話 20席早滿了
→ utomaya:ProjectEuler那些玩家 搜尋公式可是很厲害的!
→ utomaya:有時候 解個半死 ；進到論壇，才發現別人早就找到公式了
→ utomaya:這公式是沒錯的, 我驗證過, S(10^4)一下就出來了
→ utomaya:如果你不想看那麼多 直接跳到定理7, 那裡有結論
→ utomaya:還有，解題的關鍵 不在這個公式(非常確定)，要靠自己!
推 utomaya:解題的關鍵 應該在費氏數列的特性 Fn=Fn-1+Fn-2
→ utomaya:要用divide and conquer去做 很難寫! 所以第1天只有13人
→ utomaya:應該這樣說吧 利用這公式在計算時 你會發現很多計算是重複
→ utomaya:所以可以把計算的部份重複的部份 用divide and conquer
→ utomaya:去化簡!
發現我有打錯的地方  已修改！
※ 編輯: babufong        來自: 125.224.9.7          (02/20 22:15)
推 utomaya:對了 為了怕誤導大家 我再把話說清楚一點
→ utomaya:解題的關鍵 不在這個公式, 不是說不要利用這個公式
→ utomaya:當然還要利用公式，只是不要嘗試再去化簡公式
→ utomaya:這公式已經是最簡了
推 utomaya:果然跟猜想的一樣 利用fibonacci數列的特性
→ utomaya:S(10^16)mod 7^10 不用一毫秒 答案就出來了 複雜度O(logN)