Cogs 2546. 取石块儿(博弈)

取石块儿

★ 输入文件：tstones.in 输出文件：tstones.out 简单对比

时间限制：1 s 内存限制：256 MB

问题描述

小L和小T进行取石块儿游戏，给定一个整数n表示石块儿总数，给定一个整数k表示每次最多能拿走的石块儿数量，小L先手，每次能拿走1~k个石块儿，他们中总会有一个人最后拿走s块儿石块儿，使得剩余石块儿数量为0，则最后一个拿走剩下石块儿的人获胜，另外一个人失败。小T非常聪明，小L绝顶(秃子(逃))聪明，请判断小T是否能取胜。

输入格式

第一行一个整数T表示数据组数，接下来T行每行两个整数n，k意义为描述所给。

输出格式

对于每组数据，输出”YES”或者”NO”(不带引号)，代表小T是否能够获胜。

输入样例

2

2 1

10 4

输出样例

YES

YES

数据范围

大胆骗分出奇迹！

对于10%的数据，1≤k≤n≤5

对于另外10%的数据，k=1,1≤n≤10000

对于另外20%的数据，1≤k≤n≤1000,T≤10

对于另外40%的数据，1≤k≤n≤unsigned int

对于全部的测试数据，1≤k≤n≤unsigned long long,1≤T≤1000000

/*

博弈.

当n<=k时,显然先手必胜.

否则n=k+1时先手必败.

n属于[k+2,2k+1]时,总能回到n=k+1的状态,所以先手必胜.

同理 n=2(k+1),3(k+1)时先手必败......

所以 k+1|n时先手必败

否则先手必胜.

*/

#include<cstdio>

#define LL unsigned long long

using namespace std;

LL t,n,k;

inline LL read()

{

    LL x=0;char ch=getchar();

    while(ch<'0'||ch>'9') ch=getchar();

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x;

}

int main()

{

    freopen("tstones.in","r",stdin);

    freopen("tstones.out","w",stdout);

    t=read();

    while(t--)

    {

        n=read(),k=read();

        if(n%(k+1)==0) printf("YES\n");

        else printf("NO\n");

    }

    return 0;

}

巴特西

Cogs 2546. 取石块儿(博弈)

最新文章

热门文章