ACM-ICPC-OJ训练营

问题 3126 --巴什博弈

3126: 巴什博弈

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 46
[提交][状态][讨论版][命题人:]

题目描述

有n个棋子，两人轮流取，一次最少取一个，最多取m个，假设两人都以最优的方式取棋子，谁先取完最后一个则胜利，试问先手是否必胜?先手必胜输出yes，先手必败输出no。

输入描述

第一行输入T，表示有T组测试数据。（1<=T<=1000）
接下来的T行，每行输入n、m如题意（2<=m<n<=1e9）

输出描述

输出T行，yes或no表示每组测试样例的结果是先手必胜或是先手必败

样例输入

2
4 3
5 3

样例输出

no
yes

提示

第一组测试数据，有4个棋子，一次最少取1个，最多取3个，有三种情况

1、先手取1个，后手取剩下的3个，先手败（由后手取完最后一个）

2、先手取2个，后手取剩下的2个，先手败

3、先手取3个，后手取剩下的1个，先手败

故先手必败，输出no。

第二组测试数据，有5个棋子，一次最少取1个，最多取3个

此时先手如果只取1个，那么剩下4个棋子，变为第一组数据的情况：由后手选择取1或2或3个，先手再取走剩下的3或2或1个，先手必胜

来源

22计三欧阳齐

[提交][状态]