【蓝桥杯】取石子游戏

题目

蒜头君和花椰妹在玩一个游戏，他们在地上将 $颗石子排成一排，编号为到。开始时，蒜头君随机取出了颗石子扔掉，假设蒜头君取出的颗石子的编号为, 。$

游戏规则如下，蒜头君和花椰妹 $人轮流取石子，每次取石子，假设某人取出的石子编号为，那么必须要找到一对, 满足$

蒜头君比较绅士，让花椰妹先手。

输入格式

第一行输入一个整数 $\le t \le 500) </annotation> </semantics> </math>$

对于每局游戏，输入 $<math> <semantics> <mrow> <mn> 3 </mn> </mrow> <annotation encoding="application/x-tex"> 3 </annotation> </semantics> </math> 个整数 <math> <semantics> <mrow> <mi> n </mi> <mo> ( </mo> <mn> 2 </mn> <mo> ≤ </mo> <mi> n </mi> <mo> ≤ </mo> <mn> 20000 </mn> <mo> ) </mo> <mo separator="true"> , </mo> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo> ( </mo> <mn> 1 </mn> <mo> ≤ </mo> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo> ≤ </mo> <mi> n </mi> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> n(2\le n \le 20000),a,b(1 \le a,b \le n) </annotation> </semantics> </math>$

输出格式

如果蒜头君赢了游戏，输出一行 “suantou” ，如果花椰妹赢了，输入一行 “huaye”。

样例输入

5

8 6 8

9 6 8

10 6 8

11 6 8

12 6 8

样例输出

suantou

suantou

huaye

huaye

suantou

题解

刚开始 1…n 个石子，a b 两颗石子被取出，之后取出的石子 i 必须符合：i = j - k or i = j+k。
分情况讨论：

当取出的石子为 i = j - k 时，i 是 j 和 k 用碾除法求余数的中间一环，此时的 i,j,k 肯定是 j 和 k 最大公约数的倍数
当取出的石子为 i = j + k 时，变形为 j = i - k ，j 是 i 和 k 用碾除法求余数的中间一环，此时的 i,j,k 也肯定是 j 和 k 最大公约数的倍数

所以最终得出结论：
能取出的石子编号肯定是 a b 的最大公约数的倍数

#include<iostream>
using namespace std;
// 最大公约数 
int gcd(int a,int b){
	return (!b)?a:gcd(b,a%b);
}
int main(){
	int t;
	int n,a,b;
	cin>>t;
	while(t--){
		cin>>n>>a>>b;
		int num = 0;
		int times = gcd(a,b);
		for(int i=1;i<=n;i++)
			if(i%times == 0)
				num++;
		if(num%2 == 0)
			cout<<"suantou"<<endl;
		else
			cout<<"huaye"<<endl;
	} 
	return 0;
}

返回目录，查看更多