投稿 资料上传 搜索
您现在的位置是: 首页 > 文章 > 正文

“科大讯飞杯”高校网络友谊赛A:张老师和菜哭武的游戏

链接:https://ac.nowcoder.com/acm/contest/5477/A
来源:牛客网

题目描述

天才程序员菜哭武和张老师有一天到一个城市旅游,旅途中菜哭武觉得无聊就想和张老师玩一个游戏。菜哭武有n个石子,每个石子都标有1到n之间到数,且各不相同,一开始他们会随机从这堆石子选一个石子放置到一个集合中,张老师选的数是a,菜哭武选的是b(a和b不相同)。接下来菜哭武和张老师轮流按照如下规则拿走一个石子:当石子x能被拿走时,当且仅当集合存在y和z,满足x等于y+z或者y-z,当x被拿走时,把它放到集合中。谁完成最后一轮操作时,谁获胜。张老师总是先手,于是张老师就好奇当决定好a和b时,他是否总是能获胜,你能帮助一下张老师吗?

输入描述:

第一行一个整数T(1≤T≤500),表示共有T组测试数据。
对于每组测试数据,第一行三个整数n(2≤n≤20000)、a和b(1≤a,b≤n, a≠b)。

输出描述:

若张老师能获胜输出Yes,反之No。

示例1

输入

复制
16
2 1 2
3 1 3
67 1 2
100 1 2
8 6 8
9 6 8
10 6 8
11 6 8
12 6 8
13 6 8
14 6 8
15 6 8
16 6 8
1314 6 8
1994 1 13
1994 7 12

输出

复制
No
Yes
Yes
No
No
No
Yes
Yes
No
No
Yes
Yes
No
Yes
No
No

解题思路:
两个人轮流取数,那么看的就是数有多少个,求出有多少数,判断奇偶即可得知谁最后会赢。
两个数相减其实和辗转相减法类似,如果两个数互质,那么最后一定会减到1,n个数都符合条件,
如果两个数不互质,那么就看1到n之间有多少gcd(a,b)的倍数,所以数的个数就是n/gcd(a, b);

AC代码:
#include <stdio.h>

int gcd(int a,int b)
{
int t;
if(a<b)
{
t=b;
b=a;
a=t;
}

while(a)
{
t=b%a;
b=a;
a=t;
}
return b;
}
int main()
{
int t, n, a, b;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &a, &b);
if((n/gcd(a, b))%2)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}



转载于:

文章标签:
阿里云服务器采购季
给作者打赏,鼓励TA抓紧创作!
评论