作者babufong (嗶嗶)
看板puzzle
標題[中譯] ProjectEuler 325 Stone Game II
時間Sun Feb 20 20:01:05 2011
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
1F：推 LPH66:....我在家裡的一本數學書上看到這個玩法但已經忘了結論了QQ 02/20 20:07
2F：推 jurian0101:Nim - 天文數字篇 (開學了，ProEuler掰掰~~~~) 02/20 20:54
5F：→ utomaya:不過這公式複雜度是O(N) 要算到S(10^16) 還要一點輔助 02/20 21:40
6F：→ utomaya:我確定沒有別的公式了 這就是ProjectEuler賊的地方 02/20 21:41
7F：→ utomaya:光靠公式 還不足以解出；；不然的話 20席早滿了 02/20 21:42
8F：→ utomaya:ProjectEuler那些玩家 搜尋公式可是很厲害的! 02/20 21:43
9F：→ utomaya:有時候 解個半死 ；進到論壇，才發現別人早就找到公式了 02/20 21:44
10F：→ utomaya:這公式是沒錯的, 我驗證過, S(10^4)一下就出來了 02/20 21:46
11F：→ utomaya:如果你不想看那麼多 直接跳到定理7, 那裡有結論 02/20 21:47
12F：→ utomaya:還有，解題的關鍵 不在這個公式(非常確定)，要靠自己! 02/20 21:49
13F：推 utomaya:解題的關鍵 應該在費氏數列的特性 Fn=Fn-1+Fn-2 02/20 21:52
14F：→ utomaya:要用divide and conquer去做 很難寫! 所以第1天只有13人 02/20 21:53
15F：→ utomaya:應該這樣說吧 利用這公式在計算時 你會發現很多計算是重複 02/20 21:54
16F：→ utomaya:所以可以把計算的部份重複的部份 用divide and conquer 02/20 21:56
17F：→ utomaya:去化簡! 02/20 21:56
發現我有打錯的地方 已修改！
※ 編輯: babufong 來自: 125.224.9.7 (02/20 22:15)
18F：推 utomaya:對了 為了怕誤導大家 我再把話說清楚一點 02/21 00:30
19F：→ utomaya:解題的關鍵 不在這個公式, 不是說不要利用這個公式 02/21 00:30
20F：→ utomaya:當然還要利用公式，只是不要嘗試再去化簡公式 02/21 00:31
21F：→ utomaya:這公式已經是最簡了 02/21 00:31
22F：推 utomaya:果然跟猜想的一樣 利用fibonacci數列的特性 02/23 06:57
23F：→ utomaya:S(10^16)mod 7^10 不用一毫秒 答案就出來了 複雜度O(logN) 02/23 06:59