a和b一起玩游戲，他們輪流行動。a先手開局。
最初，給定一個數(shù)字 N 。在每個玩家的回合，玩家需要執(zhí)行以下操作：
選出任一 x，滿足 0 < x < N 且 N % x == 0 。
用 N - x 替換黑板上的數(shù)字 N 。
如果玩家無法執(zhí)行這些操作，就會輸?shù)粲螒颉?/p>
只有在a在游戲中取得勝利時才返回 True，否則返回 false。
假設兩個玩家都以最佳狀態(tài)參與游戲。
例如：
N = 2 返回: true 因為 0 < x < 2, a選擇 1，b無法進行操作。
N = 3 返回: true 因為 0 < x < 3, a選擇 1，0 < x < 2接著 b選擇1, a無法進行操作。
解題思路:
這道題的算法并不難, 準確說很簡潔很簡單, 它的難點在于思路
這里有個規(guī)則需要留意一下
選出任一 x，滿足 0 < x < N 且 N % x == 0
是的, 要求 N除以x余數(shù)為0
接下來, 我們先看下有沒有規(guī)律
N = 1, 0 < x < 1 a 敗
N = 2, 0 < x < 2 a 勝 a拿1, b無法執(zhí)行
N = 3, 0 < x < 3 a 敗 a只能拿1, b拿1, a無法執(zhí)行
N = 4, 0 < x < 4 a 敗 a能拿1, 2, 這里a拿1, 重復N=3時, b無法執(zhí)行
N = 5, 0 < x < 5 a 敗 a只拿1, 重復N=4時, a無法執(zhí)行
...
我們可以發(fā)現(xiàn)
N為奇數(shù)時, a先手, a敗
N為偶數(shù)時, a先手, a勝
接下來我們證明一下 是否成立
N = 1, N = 2 時結論成立
N > 2 時, 假設法, 假設 N <= k 時結論成立, 則 N = k + 1 時
① 如果k是偶數(shù), 則 k + 1 是奇數(shù), 此時 x 為 k + 1 的因數(shù), x只能為奇數(shù)(因為 奇數(shù)*奇數(shù) 才能為奇數(shù)),
奇數(shù) - 奇數(shù) = 偶數(shù), 且 k + 1 - x <= k, 輪到b時都是偶數(shù), 因為我們已經假設 N <= k (k是偶數(shù))
結論成立, 即先手必勝, 則 k + 1 為奇數(shù) a敗
② 如果k是奇數(shù), k + 1 為偶數(shù), x 奇偶都可以,
當 x 為奇數(shù)時 k + 1 - x <= k, 且 k + 1 - x 為奇數(shù), N <= k (k是奇數(shù)) 成立, b占有奇數(shù), 則b敗 a勝
當 x 為偶數(shù)時 k + 1 - x < k, 且 k + 1 - x 為偶數(shù), N <= k (k是奇數(shù)) 成立, 此時b占有偶數(shù)，處于必勝態(tài)，則 a處于必敗態(tài)。由于題目中說“兩玩家都以最佳狀態(tài)參與游戲”，故此時a應減去一個奇數(shù)，a必勝。
其實我們也可以這樣想
N如果是奇數(shù)，它的約數(shù)必然都是奇數(shù)；若為偶數(shù)，則約數(shù)可奇可偶。
無論N 初始為多大的值，游戲最終只會進行到N=2時結束，那么誰輪到 N = 2, 誰就會贏, 因為 N = 1 沒發(fā)再繼續(xù)選。
因為是a先手，那么
N若為偶數(shù)，a則只需一直選1，使b一直面臨N為奇數(shù)的情況，這樣a穩(wěn)贏；
N若為奇數(shù)，那么a第一次選完之后N必為偶數(shù)(奇數(shù)約數(shù)必然都是奇數(shù))，那么b只需一直選1就會穩(wěn)贏。
綜述，判斷N是奇數(shù)還是偶數(shù)，即可得出最終結果！
func divisorGame(_ N: Int) -> Bool {
return N % 2 == 0
}
題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
