ProjectEuler 325 Stone Game II - 拼圖

Hardy avatar
By Hardy
at 2011-02-20T20:01

Table of Contents

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。

--
Tags: 拼圖

All Comments

Puput avatar
By Puput
at 2011-02-23T22:23
....我在家裡的一本數學書上看到這個玩法但已經忘了結論了QQ
Liam avatar
By Liam
at 2011-02-28T14:14
Nim - 天文數字篇 (開學了，ProEuler掰掰~~~~)
Daph Bay avatar
By Daph Bay
at 2011-03-02T17:58
<拈及其各種變形遊戲> http://goo.gl/wvGCP
Eartha avatar
By Eartha
at 2011-03-06T03:31
歐氏對局 http://tinyurl.com/4m4zzdl 裡面有公式
Olga avatar
By Olga
at 2011-03-07T17:44
不過這公式複雜度是O(N) 要算到S(10^16) 還要一點輔助
Skylar Davis avatar
By Skylar Davis
at 2011-03-11T05:10
我確定沒有別的公式了 這就是ProjectEuler賊的地方
John avatar
By John
at 2011-03-11T09:57
光靠公式 還不足以解出；；不然的話 20席早滿了
Jessica avatar
By Jessica
at 2011-03-12T08:49
ProjectEuler那些玩家 搜尋公式可是很厲害的!
Lily avatar
By Lily
at 2011-03-14T09:31
有時候 解個半死 ；進到論壇，才發現別人早就找到公式了
Valerie avatar
By Valerie
at 2011-03-17T04:28
這公式是沒錯的, 我驗證過, S(10^4)一下就出來了
Thomas avatar
By Thomas
at 2011-03-19T23:15
如果你不想看那麼多 直接跳到定理7, 那裡有結論
Kristin avatar
By Kristin
at 2011-03-24T00:16
還有，解題的關鍵 不在這個公式(非常確定)，要靠自己!
Skylar DavisLinda avatar
By Skylar DavisLinda
at 2011-03-25T12:37
解題的關鍵 應該在費氏數列的特性 Fn=Fn-1+Fn-2
Agatha avatar
By Agatha
at 2011-03-27T08:10
要用divide and conquer去做 很難寫! 所以第1天只有13人
Adele avatar
By Adele
at 2011-03-31T14:44
應該這樣說吧 利用這公式在計算時 你會發現很多計算是重複
Bethany avatar
By Bethany
at 2011-04-01T20:38
所以可以把計算的部份重複的部份 用divide and conquer
去化簡!
Ina avatar
By Ina
at 2011-04-04T02:58
對了 為了怕誤導大家 我再把話說清楚一點
解題的關鍵 不在這個公式, 不是說不要利用這個公式
Catherine avatar
By Catherine
at 2011-04-07T17:11
當然還要利用公式，只是不要嘗試再去化簡公式
這公式已經是最簡了
Kyle avatar
By Kyle
at 2011-04-09T03:23
果然跟猜想的一樣 利用fibonacci數列的特性
Zanna avatar
By Zanna
at 2011-04-13T18:57
S(10^16)mod 7^10 不用一毫秒 答案就出來了 複雜度O(logN)

關於益智的書

William avatar
By William
at 2011-02-20T10:59
如果是買不到的，我就不PO心酸了。 ※次序為隨機排列，無優劣喜好之分。 ●數學相關 數字的異想世界 商周出版 380元 俗又大碗，很多有趣的題目和遊戲以及知識。 跳出思路的陷阱 天下文化 150元 葛老爹的書都很有趣。 IQ大作戰 小知堂文化 也同樣俗又大碗。很多經典的邏輯題目 ...

哈姆太郎將棋新連結

Rebecca avatar
By Rebecca
at 2011-02-20T09:35
剛剛在將棋板看到的， 覺得有必要更新。 之前的哈姆太郎將棋之連結已失效了， 不過好險，其他地方還是可以找得到： http://www.flashgame.com.hk/shogi-game.html 最後，我絕對沒有說可以把它下載到自己的電腦裡面哦！ 想知道將棋規則的人，可參考連結右方說明， 以及在 ...

SudokuCup5(12)

Mia avatar
By Mia
at 2011-02-20T08:38
應該是這樣...吧 ※ 引述《chyrliin (企鵝靈)》之銘言： : 　　　┌───┬───┐ : 　　　│　　7　9　　│ : 　　　│　9　　　3　│ : 　　　│5　　6　　1│ : 　　　├　　9　2　　┤ : 　　　│7　　　　　3│ : 　　　│　1　9　8　│ : 　　　│　　4　6　　│ ...

[分享] 益智-互鎖(Interlocked)

Kelly avatar
By Kelly
at 2011-02-19T18:30
※ [本文轉錄自 Little-Games 看板 #1DNqnhNp ] 作者: OrangeShadow (橘之影) 看板: Little-Games 標題: [分享] 益智-互鎖(Interlocked) 時間: Sat Feb 19 12:51:52 2011 遊戲名稱: ...

關於益智的書

Sierra Rose avatar
By Sierra Rose
at 2011-02-19T11:05
不管是益智遊戲,益智玩具,或是益智數學... 市面上琳瑯滿目看的目不暇給... 不曉得有沒有網友可以推薦一下這方面比較好的書籍? 謝謝! - ...