HDU 1517「乘法遊戲」是一道經典的博弈論問題，兩位玩家輪流將當前數值乘以 2 到 9 之間的整數，先使結果 ≥ n 者獲勝。本文深入分析必勝/必敗態的數學規律，並給出 O(log n) 的高效判斷算法。
遊戲規則與建模
- 初始值 p = 1，斯坦先手。
- 每回合玩家選擇 k ∈ [2, 9]，更新 p ← p × k。
- 先使 p ≥ n 者獲雙方均採取最優策略。
態空間分析：從小到大推導
我們定義區間 [L, R] 為「先手必勝」或「先手必敗」。
- 基礎區間：n ∈ [2, 9] → 先手直接乘以 n 獲勝，先手必勝。
- n ∈ [10, 18]：先手無論乘以何值（2~9），結果落在 [2, 9] × 2 = [4, 18]，但關鍵在於後手面對的值 ∈ [2, 9]（若先手乘 2 得 2，後手乘 9 得 18 ≥ n？需細分）。實際分析：先手乘 k 後 p = k ∈ [2, 9]，後手可乘 9 使 p ≥ 18。若 n ≤ 18，後手必勝。故 [10, 18] 為先手必敗。
- 擴展規律：先手欲獲勝，需將遊戲推向「後手面對必敗態」。若先手能乘某數使 p 進入 [10, 18]，則後手必敗。因此先手必勝區間為 [2, 9] × 18 = [36, 162]？不，需反向思考：
關鍵洞察：18 的倍數邊界
觀察發現：
- 先手必勝區間：[2, 9], [18×2+2, 18×9] = [38, 162]？實際更簡單：
- 定義「安全區間」：先手希望遊戲進入的區間，使後手必敗。
- 從基礎 [2, 9]（先手勝）出發，後手必敗區間為 [10, 18]。
- 先手要進入 [10, 18]，需在上一輪使 p ∈ [2, 9]（因 2×5=10, 9×2=18）。但 [2, 9] 是先手勝，矛盾？
正確遞歸定義：
- 設 W 為先手必勝區間，L 為先手必敗區間。
- W₀ = [2, 9]
- L₀ = [10, 18]（先手移動後進入 W₀，後手勝）
- W₁ = [19, 162]？不，先手欲使後手面對 L₀，需移動後 p ∈ L₀。因 p ← p×k，k∈[2,9]，故上一輪 p ∈ [ceil(10/9), floor(18/2)] = [2, 9] = W₀。這說明從 W₀ 只能移到 L₀？
標準解法：反向縮放
經典做法是反向模擬：從 n 開始不斷除以 18，觀察最終落在哪個基礎區間。
- 若 n ∈ [2, 9] → 先手勝
- 若 n ∈ [10, 18] → 先手敗
- 若 n > 18，雙方最優策略下，遊戲等價於 n ← ceil(n / 18) 後的狀態？實際上：
- 先手希望儘快達標，後手希望拖延。最優策略下，先手總選 9，後手總選 2？否，雙方都會選擇對自己最有利的乘數。
核心定理：反覆執行 n = ceil(n / 18) 直到 n ≤ 18，若最終 n ≤ 9 則先手勝，否則先手敗。等價於：
while (n > 18) n = (n + 17) / 18; // 向上取整除以 18
// 或用浮點：while (n > 18) n /= 18.0;
if (n <= 9) Stan wins; else Ollie wins;
代碼實現（C）
#include <stdio.h>
int main() {
double n;
while (scanf("%lf", &n) == 1) {
while (n > 18) n /= 18.0;
printf(n <= 9 ? "Stan wins.\n" : "Ollie wins.\n");
}
return 0;
}
為什麼用 double？
n 可達 4,294,967,295 (2³²-1)，64 位整數除法會截斷，導致邊界判斷錯誤。用 double 保留小數部分，/= 18 相當於向上取整邏輯，精度足夠。
總結
本題展示了博弈論中「周期性必勝/必敗態」的典型特徵。關鍵在於識別 18 為關鍵乘數（9×2），將大數問題縮減為小區間判斷。這類「乘法/除法遊戲」通用解法：找到關鍵乘積週期，反向縮放目標值。
