C. Adidas vs Adivon：撕紙遊戲博弈論解法

C. Adidas vs Adivon 題解

遊戲規則

初始有一張 L × H 的長方形紙片（L, H 為正整數）。雙方輪流操作，Adidas 先手。每回合可將紙片沿長邊或寬邊平行方向撕成兩半，丟棄一半，剩下的半片長寬仍須為正整數。無法操作者輸。

核心觀察

每次操作將某維度除以 2（要求該維度為偶數）。遊戲相當於：兩堆石子遊戲，每堆大小為該維度包含的因子 2 的個數。每回合從某堆取走至少 1 個「因子 2」。

設 k = count_factor_2(L) + count_factor_2(H)。若 k 為奇數，先手必勝；偶數則後手必勝。

證明大綱

• 每次操作恰好減少總因子 2 個數 1（撕長邊減少 L 的因子 2，撕寬邊減少 H 的）
• 遊戲在 k 步後必然結束（雙方皆為奇數時無法操作）
• 屬於標準 Nim 遊戲的退化形式，勝負僅取決於總步數奇偶性

程式碼實作

#include <cstdio>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long L, H;
        scanf("%lld%lld", &L, &H);
        int k = 0;
        while (L % 2 == 0) { k++; L /= 2; }
        while (H % 2 == 0) { k++; H /= 2; }
        if (k % 2 == 0)
            puts("Adivon prevails");
        else
            puts("Adidas loses");
    }
    return 0;
}

範例

Input:
2
1 2
2 2

Output:
Adidas loses
Adivon prevails

解析：
1×2：因子2總數=1（奇）→ 先手勝
2×2：因子2總數=2（偶）→ 後手勝

複雜度

• 時間：O(log L + log H) 每測試案例
• 空間：O(1)