题目名称	2546. 巴什博弈
输入输出	`tstones.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	Fmuckss 于2016-11-15加入
开放分组	全部用户
提交状态
分类标签	博弈论
	分享题解

通过：119，提交：220，通过率：54.09%
NVIDIA	100	0.026 s	0.19 MiB	C++
PYD1	100	0.034 s	1.45 MiB	C++
_IOSTREAM_	100	0.046 s	0.42 MiB	C++
Daidly	100	0.067 s	3.44 MiB	C++
woee	100	0.073 s	3.44 MiB	C++
qwq	100	0.082 s	3.44 MiB	C++
Shirry	100	0.092 s	0.32 MiB	C++
AAAAAAAAAA	100	0.095 s	0.32 MiB	C++
终焉折枝	100	0.111 s	2.01 MiB	C++
Apocana-Wisbtsml	100	0.113 s	0.19 MiB	C++

本题关联比赛
20161115

关于巴什博弈的近10条评论(全部评论)
回复 @Margatroid : 居然还有这种操作!？蒟蒻已哭晕在厕所T^T Tbnlkegc 2017-07-03 15:55 13楼
怎样的大神将此题控制在0.026 s。大写的服。 Tbnlkegc 2017-03-12 08:17 12楼
n<=k时，先手必胜，n=k+1时，先手必输，从n=k+2到n=2k+1，先手都能回到n=k+1,此时先手必胜，用数学归纳，易证n%(k+1)=0时先手必败。 fate1 2017-03-10 19:32 11楼
回复 @liu_runda : 我才不会告诉你是我造数据的时候忘记我题目里写的是ull了.... Fmuckss 2016-12-14 20:35 10楼
可以无视unsigned long long,long long就能过.(第一遍我交的int,40分...) liu_runda 2016-11-16 19:25 9楼
这题，水啊，就是传说中的小学奥数题0.0 ZWOI_ヤシニャ 2016-11-15 15:07 8楼
考试时想了快1小时没想出来，中午回宿舍在桌子上A了 svideo 2016-11-15 14:16 7楼
天天天天天天天天 NVIDIA 2016-11-15 13:25 6楼
卡快读啊-- Shirry 2016-11-15 13:10 5楼
当时演草纸上比划了一个多小时(我好菜啊)发现n = k+1是先手必败状态。推广一下A了....... sxysxy 2016-11-15 12:22 4楼

2546. 巴什博弈

★ 输入文件：tstones.in 输出文件：tstones.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目背景】

Bash Game.

【题目描述】

小L和小T进行取石块儿游戏。给定一个整数 $n$ 表示石块儿总数，给定一个整数 $k$ 表示每次最多能拿走的石块儿数量。

小L先手，每次能拿走 $1 \sim k$ 个石块儿。他们中总会有一个人最后拿走剩下所有的石块儿，使得剩余石块儿数量为 $0$，则最后一个拿走剩下石块儿的人获胜，另外一个人失败。

小T非常聪明，小L绝顶聪明，请判断小T是否能取胜。

【输入格式】

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行每行两个整数 $n$，$k$，意义如题目描述所示。

【输出格式】

对于每组数据，输出一行为答案。若小T能够获胜输出 “YES”，否则输出 “NO”（不带引号）。

【样例输入1】

2
2 1
10 4

【样例输出1】

YES
YES

【数据规模与约定】

对于 10% 的数据，$1 \le k \le n \le 5$。

对于另 10% 的数据，$k = 1, 1 \le n \le 10000$。

对于另 20% 的数据，$1 \le k \le n \le 1000, T \le 10$。

对于另 40% 的数据，$1 \le k \le n \le \text{unsigned int}$。

对于全部的测试数据，$1 \le k \le n \le \text{unsigned long long}, 1 \le T \le 1000000$。

大胆骗分出奇迹！