Codeforces Round 726 (Div. 2)

D. Deleting Divisors

题目翻译

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，有一个数字 $N$ 。在每个玩家的回合，玩家需要执行以下操作：

• 选出任一 $x$ ，满足 $1 < x < N$ 且 $x$ 是 $N$ 的因子。
• 用 $N - x$ 替换数字 $N$ 。
  如果玩家无法执行这些操作，就会输掉游戏。

假设两个玩家都以最佳状态参与游戏。

• 如果Alice获胜，输出 Alice 。
• 如果Bob获胜，输出 Bob 。

简要思路

类似于 LeetCode: 1025. 除数博弈

将这个游戏分为三种情况：

1. $N$ 是奇数
2. $N$ 是偶数，且 $N$ 包含奇数质因子。
3. $N$ 是偶数，且 $N$ 只有 $2$ 这个质因子。

情况1：因为 $N$ 是奇数，所以 $N$ 所有的因子都是奇数。那么这样就分两种情况讨论，如果 $N$ 是质数，那么Alice必败；如果 $N$ 不是质数，那么Alice可以通过减去一个奇数因子 $x$，使得当前状态转换到状态2。因为 $N-x$ 中一定包含奇数因子，所以没法转换到状态3。

情况2：因为 $N$ 是一个包含奇数因子的偶数。Alice可以通过减去一个奇数，使得转换到状态1。这样一来，Bob就存在无法操作的可能性（质数）；即使Bob可以继续操作，那么也是转换到状态2。那么，Alice又可以减去一个奇数。所以情况2胜利的一定是Alice，同时可以判断的出来，情况1胜利的一定是Bob。这样就不用考虑减去偶数的情况，因为Alice非常聪明😂。

情况3：$N$是只包含 $2$ 这个质因子。那么Alice减去一个偶数之后，可能会出现状态2或者继续状态3。如果出现状态2，那么获胜的就是Bob，于是Alice只会考虑继续状态3，即Alice选择将 $N$ 减半。但是如果 $N=2^{2k-1} (k \in \mathbb{N}^+)$，那么Alice减半，然后Bob也选择减半之后，最终Alice会拿到 $N=2$ 这样的情况，她无法获胜。但是如果 $N = 2 ^ {2k} (k \in \mathbb{N}^+)$，那么Alice是一定获胜的。

总结一下：

• $N$ 是奇数，Bob获胜
• $N$ 是包含奇数因子的偶数，Alice获胜
• $N$ 是只包含 $2$ 这个质因子的偶数，如果因子个数是奇数，Bob获胜
• $N$ 是只包含 $2$ 这个质因子的偶数，如果因子个数是偶数，Alice获胜

示例代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        if(n % 2 == 1){ // 奇数
            cout << "Bob" << endl;
        }else if(((n-1) & n) == 0){ // 只包含质因子2的偶数
            int tmp = __builtin_ctz(n);
            if(tmp & 1){    // 有奇数个质因子
                cout << "Bob" << endl;
            }else{          // 有偶数个质因子
                cout << "Alice" << endl;
            }
        }else{              // 包含奇质因子的偶数
            cout << "Alice" << endl;
        }
    }
    return 0;
}