主題
題目連結(jié)：
題目大意：
輸入有多列，每列給定一正整數(shù) n（1 < n < 2 ^ 32 - 1）。現(xiàn)在 Stan 和 Ollie 在玩一個遊戲。一開始有一個數(shù)字，其值為 1，每次操作是將該值乘上一個 2（含）～ 9（含）的數(shù)字。由 Stan 作為先手，接著兩人便輪流執(zhí)行操作。第一個使數(shù)字 ≧ n 的人即是贏家。
在 Stan 和 Ollie 都是按照最佳策略遊玩以及給定的 n 值之情況下，誰必贏？
範(fàn)例輸入：
3
38
168
162
17
34012226
範(fàn)例輸出：
Stan wins.
Stan wins.
Ollie wins.
Stan wins.
Ollie wins.
Stan wins.
解題思維：
可以看到
n = 2 ～ 9 時，Stan 必贏；
n = 10 ～ 18 時，Ollie 必贏；
n = 19 ～ 162 時，換 Stan 必贏；
n = 163 ～ 324 時，換 Ollie 必贏；
n = 325 ～ 2916 時，又換 Stan 必贏；
n = 2917 ～ 5832 時，再換 Ollie 必贏；
……
以此類推。
更正式地說，當(dāng) n 位於開區(qū)間 (18 ^ x, 9 × 18 ^ x] 內(nèi)時即是 Stan 必贏；而 n 位於開區(qū)間 (9 × 18 ^ x, 18 ^ (x + 1)] 中時，Ollie 必贏。其中 x 為一個非負(fù)整數(shù)。
因此我們只需要判斷 n 位於哪個區(qū)間（可以窮舉 x 去判斷即可）便可以得到誰必贏。
而證明如下：
當(dāng) n 位於 (1, 9] 時，Stan 乘上 n 即可以到達(dá) n（也可以通通乘以 9）；而當(dāng) n 位於 (9, 18] 時，因為 Stan 至少需乘上 2，且這邊的 n 值 ÷ 2 ≦ 9。所以 Ollie 此時便可以無腦地乘以 9 來超過或到達(dá) n。
也就是當(dāng) x = 0 時，(18 ^ 0, 9 × 18 ^ 0] 確實屬於 Stan 之必贏區(qū)間，而 (9 × 18 ^ 0, 18 ^ 1] 為 Ollie 之必贏區(qū)間。因此此時命題成立。
假設(shè) x = k 時命題成立。而當(dāng) x = k + 1 時：
我們可以看到先手 Stan 將原先的數(shù)字 1 乘上 [2, 9] 中的任一數(shù)字 p 後，且此時因為回合輪替，因此現(xiàn)在變成 Stan 為「後手」。所以會使得原先的區(qū)間
(18 ^ (k + 1), 9 × 18 ^ (k + 1)]
等價於開區(qū)間
(18 ^ (k + 1) ÷ p, 9 × 18 ^ (k + 1) ÷ p]
而因為 Stan 和 Ollie 按照最佳策略遊玩。則我們可以看到此時 Stan 可以藉由選定特定 p 值（例如左端點 18 ^ (k + 1) 為 p = 2、右端點 9 × 18 ^ (k + 1) 為 p = 9 等等），使得這個等價區(qū)間變?yōu)?/div>
(9 × 18 ^ k, 18 ^ (k + 1)]
而這恰好是 x = k 時原先的後手 Ollie 必贏的區(qū)間——但是現(xiàn)在的「後手」為 Stan，因此變成了 Stan 必贏。
類似地，原先的區(qū)間
(9 × 18 ^ (k + 1), 18 ^ (k + 2)]
將會等價於
(9 × 18 ^ (k + 1) ÷ p, 18 ^ (k + 2) ÷ p]
此時我們便會發(fā)現(xiàn)不管 Stan 的 p 值為多少，這個區(qū)間將落在
(18 ^ (k + 1), 9 × 18 ^ (k + 1)]
而這就是上面剛剛推出來的原先之先手 Stan 必贏的區(qū)間——但是現(xiàn)在的「先手」為 Ollie，因此變成了 Ollie 必贏。
因此可以看到 x = k + 1 時命題也成立。因此根據(jù)數(shù)學(xué)歸納法，對於任意非負(fù)整數(shù) x 值命題皆成立。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達(dá)人
