【題目大意】
　　猴子和Kruskal玩一個取石子游戲，給定n堆石子，n不大于200，每堆石子的個數大于2小于2 ^ 32，雙方輪流取子，每次可以從一堆中取最多k個，當一方取完石子后某堆石子的個數是素數的話那么當前玩家獲勝。問猴子是否有必勝策略。

【題目分析】
　　這是一道BT題，中間設置了許多trick。開始對題意沒有完全理解，錯了很多次，后來找來了數據，才發現了問題。
　　題目中描述的獲勝策略是："A player wins if after his move the size of some heap is a prime number."這句話乍一看以為是取完石子后剩下的石子個數是素數的時候就獲勝，其實還隱藏著另一種可能：如果多堆石子個數是素數，當前玩家無論怎樣取都能獲勝，因為在他取完之后，其他堆的石子個數是素數，也滿足獲勝條件。
　　接下來考慮一般情況。這個題目是限制中間狀態的Nim游戲，也就是說，對于一堆個數為n的石子而言，它的SG值取決于小于n的最大素數。注意這里題設又有了一個小trick，題目說明了需要取1到k個，如果當前石子個數本身是素數，當然是沒用的，因此是小于n的最大素數。設小于n的最大素數是p(題目中說明了石子個數大于2，因此p一定存在)，那么可以在k步以內到達p的一定是必勝態，而且是直接獲勝，需要在輸入的時候特判(這一點需要注意，在解決限制中間狀態的Nim游戲時一般都需要特判)。然后就是p + k + 1這個狀態，因為它可達的狀態全是必勝態，因此它是必敗態，SG值為0。現在考慮大于p + k + 1的狀態，問題出來了。以p + k + 2這個狀態為例，因為它可以到達p + 2 ... p + k + 1這些狀態，因為p + 2 ... p + k都是直接獲勝狀態，如何判定他們的SG值呢？如果假設它們的SG值是1，那么p + k + 2這個狀態的SG值應該是2。但是思考一下SG值的定義，它是定義在一個DAG上的，所有的狀態最后都是可以在有限步內轉移到終止態(必敗態)。但是p + 1 ... p + k這些狀態都轉移到了p這個狀態上，我們肯定不能認定p狀態是終止態，因此僅僅憑借p + 1 ... p + k這些狀態是必勝態就簡單的把它們的SG值設為1是不恰當的；這些限制狀態和以前的題目還不同，這些限制狀態都不能轉移到終止態上，但是由于題目的要求，它們又都是必勝態，因此把它們的SG值設為無窮大更合適些。
　　仔細思考一下帶限制狀態的SG游戲，可以發現，它們和一般的SG游戲的區別在于，在分析一般的SG游戲的時候，對于一個狀態圖而言，轉移到終止態的時候并不意味著游戲結束，因為玩家可以通過走其他的狀態圖來保證是否達到必勝態；但是帶限制狀態的SG游戲，限制的狀態雙方都是不敢走的，因為一旦一方走入限制狀態，另一方立刻獲勝，游戲就終止了。可以認為，只要走入限制態就相當于認輸，對于雙方玩家而言肯定都不會這樣做，因此這些限制狀態就成了“死狀態”，完全可以忽視這些狀態（也就是說不存在到這些狀態的轉移）。通過上述分析，我們可以認定p + k + 2這個狀態的SG值應該是1而不是2。
　　現在這個問題的做法就比較明朗了，對于每堆石子，去掉限制態的討論后，就變成了在集合{1...k}中選擇元素的一個Subtraction Game，它的SG值是模(k + 1)循環的。
　　然后就是求最近素數的問題了，這個沒有好辦法，只能暴力枚舉。對于一個數n，在sqrt(n)到n之間存在素數（感覺應該是，但是不會證），因此最多枚舉sqrt(n)次就能找到解。但是每次枚舉判素的復雜度還是sqrt(n)，總復雜度還是比較高，我在本地跑數據跑了3秒，交上去超時了（SPOJ的時限10秒，這居然也超時，數據夠變態）。想了很久也沒有什么新的算法，無奈只能在判素上下點功夫，直接把Miller-Rabin搞出來了，速度提高到了2秒，仍然超時。后來又加了一些常數上的優化，終于過了。

【總結】
　　這個題目做了很長時間，一方面是審題不清，錯了幾次；另一方面是對于SG的理論理解的不夠透徹，想了很久終于想明白了；再有就是優化算法也花了很長時間。不過通過這個題目對于SG理論的理解又進了一步，感覺不錯，呵呵。

注：本文作于2009年8月6日 9點27分