NOIP2023模拟10联测31 游戏

本文主要是介绍NOIP2023模拟10联测31 游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

$\text{Alice}$ 和 $\text{Bob}$ 在玩一个游戏：有一个由正整数组成的集合 $S$ ，两人轮流从中选数， $\text{Alice}$ 先手。每次一个人可以从当前集合中选一个数 $x$ ，把 $x$ 以及 $x$ 在集合中所有的因数从集合中删除，注意 $x$ 必须在集合中。当一个人无法选数（也就是集合为空）时这个人就输了。问一开始集合为 $\{x|1\leq x\leq n,\phi(x)\leq m\}$ 时，当双方都采用最优策略时，谁会获胜。

如果 $\text{Alice}$ 会获胜，则输出 $\text{Alice}$ ；否则，输出 $\text{Bob}$ 。

$1\leq n\leq 100,0\leq m\leq n$

题解

如果初始集合为空（即 $m = 0$ ），则后手胜。

如果初始集合非空的话，则 $1$ 一定在集合中。我们考虑先手不选 $1$ 的话能否获胜。

如果先手不选 $1$ 能获胜，则先手必胜
如果先手不选 $1$ 必败，那么先手就选 $1$ ，给后手留下了一个不能选 $1$ 的必败的局面

你也许会觉得，一开始不能选 $1$ 的局面中有 $1$ ，但先手选 $1$ 之后留下的局面没有 $1$ 了，两个局面不一样，所以前一个必败不能说明后一个必败。但是这两个局面的前提都是不能选 $1$ ，而且不管选什么， $1$ 都会被删除，后面同样也不能选 $1$ ，所以两个局面是等价的。

也就是说，如果 $m = 0$ ，则输出 $\text{Bob}$ ；否则，输出 $\text{Alice}$ 。

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);scanf("%d%d",&n,&m);if(m==0) printf("Bob\n");else printf("Alice\n");return 0;
}