蒜头君和花椰妹在玩一个游戏,他们在地上将 n 颗石子排成一排,编号为 1 到 n。开始时,蒜头君随机取出了 2 颗石子扔掉,假设蒜头君取出的 2 颗石子的编号为 a, b。游戏规则如下,蒜头君和花椰妹 2 人轮流取石子,每次取石子,假设某人取出的石子编号为 i,那么必须要找到一对 j, k 满足 i=j−k 或者 i=j+k ,并且编号为 j,k 的石子已经被取出了,如果谁先不能取石子了,则视为输了。蒜头君比较绅士,让花椰妹先手。
输入格式
第一行输入一个整数 t(1≤t≤500),表示蒜头君和花椰妹进行了 t 局游戏。
对于每局游戏,输入 3 个整数 n(2≤n≤20000),a,b(1≤a,b≤n),保证 a,b 不相等。
输出格式
如果蒜头君赢了游戏,输出一行suantou,如果花椰妹赢了,输入一行huaye。
样例输入
5
8 6 8
9 6 8
10 6 8
11 6 8
12 6 8
样例输出
suantou
suantou
huaye
huaye
suantou
解题思路:
根据i=j-k,或 i=j+k,则一定会取到 编号为j 和 k 的最大公约数的石子,并且所拿的所有石头的编号都是最大公约数的倍数
假设玩家每次取的石头编号为a和b最大公因数的倍数,那么当一个玩家没法再取石头时(所有符合条件的石头被取完了,那么该玩家就输了)
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int N;
bool isappr[20010];
int sgcd(int a, int b){
if (b == 0) return a;
else return sgcd(b, a%b);
}
int main() {
scanf("%d", &N);
int n,x,y;
while (N--) {
memset(isappr, true, sizeof(isappr));
scanf("%d %d %d",&n, &x, &y); //返回x,y
int gcNum = sgcd(x, y); //先求得公因数
isappr[x] = false, isappr[y] = false;
int stpot = gcNum;
bool huaStart = false; //花椰菜为false,蒜头为true
while (stpot <= n){
if (isappr[stpot] == true) {
huaStart = !huaStart;
}
stpot += gcNum;
}
if (huaStart) {
printf("huaye\n");
}
else {
printf("suantou\n");
}
}
system("PAUSE");
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)