(计蒜客) 取石子游戏 (gcd算法灵活运用)

港控/mmm° 2022-02-21 10:42 233阅读 0赞

蒜头君和花椰妹在玩一个游戏，他们在地上将 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;
    }