HDU 2149 Public Sale：巴什博弈模型直接應用

題目大意

兩人輪流加價，每次加 1~N，價格 ≥ M 者得。Lele 先加。問 Lele 第一次加價多少能必勝，輸出所有必勝初始加價（遞增），無則輸出 none。

巴什博弈結論

經典取石子遊戲：堆有 M 石子，每次取 1~N，取走最後者勝。
先手必勝 ⟺ M % (N+1) != 0。
必勝第一步：取 `M % (N+1)` 個 (若非 0)。

映射到本題

「加價」等價於「取石子」，目標價 M 等價於石子總數。
Lele 先手，第一次加價 `x` 後剩餘 `M-x`，輪到對手。
Lele 必勝條件：`M % (N+1) != 0`。
若 `M <= N`：Lele 可直接加到 ≥ M 獲勝，所有 `x ∈ [M, N]` 均為必勝。
若 `M > N`：唯一必勝第一步為 `M % (N+1)` (若為 0 則無必勝策略)。

代碼實現 (C++)

#include 
int main() {
    int M, N;
    while (~scanf("%d%d", &M, &N)) {
        if (M % (N + 1) == 0) {
            puts("none");
        } else {
            if (M <= N) {
                for (int i = M; i <= N; i++) {
                    printf("%d%c", i, i == N ? '\n' : ' ');
                }
            } else {
                printf("%d\n", M % (N + 1));
            }
        }
    }
    return 0;
}

樣例驗證

4 2 -> M=4, N=2, 4%(2+1)=1 -> 輸出 1
3 2 -> 3%3=0 -> none
3 5 -> M<=N -> 輸出 3 4 5

記憶體優化說明

代碼極簡，無額外數組，僅幾個整數變量。編譯優化 `-Os` 可進一步減小可執行文件。內存佔用主要來自 C++ 運行時庫和標準輸入輸出緩衝區，非算法本身。若極致優化可用 C 語言 `stdio.h` 並去除異常處理支持。