Codeforces Round 726 (Div. 2)

本文最后更新于:2022年5月21日 下午

D. Deleting Divisors

题目翻译

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

  • 选出任一 xx ,满足 1<x<N1 < x < NxxNN 的因子。
  • NxN - x 替换数字 NN
    如果玩家无法执行这些操作,就会输掉游戏。

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

  • 如果Alice获胜,输出 Alice
  • 如果Bob获胜,输出 Bob

简要思路

类似于 LeetCode: 1025. 除数博弈

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

  1. NN 是奇数
  2. NN 是偶数,且 NN 包含奇数质因子。
  3. NN 是偶数,且 NN 只有 22 这个质因子。

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

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

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

总结一下:

  • NN 是奇数,Bob获胜
  • NN 是包含奇数因子的偶数,Alice获胜
  • NN 是只包含 22 这个质因子的偶数,如果因子个数是奇数,Bob获胜
  • NN 是只包含 22 这个质因子的偶数,如果因子个数是偶数,Alice获胜

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}

Codeforces Round 726 (Div. 2)
https://dianhsu.top/2022/05/10/cf1537/
作者
Dian Hsu
发布于
2022年5月10日
许可协议