显然这种题我们可以打个表来帮助我们思考问题。
枚举 \(i\) 的每一个非 \(1\) 和 \(i\) 的因数 \(j\),判断 \(i-j\) 是否为必败态,若是,则 \(i\) 为必胜态;反之 \(i\) 为必败态。
可以采用复杂度为 \(\Theta(n\sqrt{n})\) 的代码进行打表:
/*
I will never forget it.
*/
// 392699
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3;
bool f[N + 10];
// f[i] 为 1 表示先手必胜
// f[i] 为 0 表示先手必败
struct OI {
int RP, score;
} CSPS2021, NOIP2021;
signed main() {
CSPS2021.RP++, CSPS2021.score++, NOIP2021.RP++, NOIP2021.score++, 392699;
f[1] = 0, f[2] = 0, f[3] = 0, f[4] = 1;
for (int i = 5; i <= N; i++) {
for (int j = 2; j * j <= i; j++)
if (i % j == 0 && (f[i - j] == 0 || f[i - i / j] == 0)) {
f[i] = 1;
break;
}
for (int i = 1; i <= N; i++)
printf("f[%d] = %d\n", i, f[i]);
return 0;
}
观察程序的输出可以发现当 \(i\) 为奇数时先手必败,但是也有若干个偶数是先手必败的,为了使分析更加方便,我们修改代码使其只输出先手必败的偶数:
/*
I will never forget it.
*/
// 392699
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3;
bool f[N + 10];
// f[i] 为 1 表示先手必胜
// f[i] 为 0 表示先手必败
struct OI {
int RP, score;
} CSPS2021, NOIP2021;
signed main() {
CSPS2021.RP++, CSPS2021.score++, NOIP2021.RP++, NOIP2021.score++, 392699;
f[1] = 0, f[2] = 0, f[3] = 0, f[4] = 1;
for (int i = 5; i <= N; i++) {
for (int j = 2; j * j <= i; j++)
if (i % j == 0 && (f[i - j] == 0 || f[i - i / j] == 0)) {
f[i] = 1;
break;
}
for (int i = 1; i <= N; i++)
if (f[i] == 0 && i % 2 == 0) printf("f[%d] = %d\n", i, f[i]);
return 0;
}
观察输出发现,当 \(i\) 为偶数时只有 \(i \in \{2^{2k+1}, k \in \mathbb{N}\}\) 的时候是先手必败。
按照发现的规律进行判断即可,代码在这里。