题目描述
http://codeforces.com/problemset/problem/1537/D
简要题解：开始有一个正整数 $n$，每次操作可以减掉 $n$ 的一个不是 $1$ 和 $n$ 的因子，不能操作的人输，求是否先手必胜
$n\le 10^9$
Solution
我们分三种情况讨论：
- $n$ 是奇数
- $n$ 是偶数但不是 $2$ 的幂
- $n$ 是 $2$ 的幂
第一种情况，$n$ 是奇数，所以 $n$ 的因子 $d$ 也一定是奇数，因为我们一定有 $d|(n-d)$，所以 $n-d$ 一定不是 $2$ 的幂，所以第一种情况只能转化到第二种情况
第二种情况，由于 $n$ 是偶数且不是 $2$ 的幂，所以一定存在一个奇因子，所以一定能转化到第一种情况，由于第一种情况最终是必败态，所以第二种情况一定是必胜态
第三种情况，当 $n$ 是 $2$ 的幂时，我们要么减掉 $\frac n 2$ 维持第三种情况，要么转换到第二种情况，但是第二种情况是必胜态，所以我们只能维持第三种情况，容易得到当 $n$ 是 $2$ 的偶数幂时必胜，奇数幂必败
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define maxn 200010
#define ll long long
#define INF 1000000000
using namespace std;
int n;
void work() {
cin >> n;
if (n & 1) return cout << "Bob" << "\n", void();
if (n % 2 == 0) {
ll t = 2;
while (t < n) t *= 4;
if (t == n) return cout << "Bob" << "\n", void();
} cout << "Alice" << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|