广西大学第一届程序设计大赛

题目描述

小西买了一堆肥宅快乐水和肥宅快乐茶，准备和室友比谁更肥宅。

快乐水有A瓶，快乐茶B瓶。

小西和室友的规则是这样的：

1. 小西先手，轮流到每个人的回合，每个回合只能喝剩余数量较多的饮料

2. 满足规则1的同时，每次只能喝另一种饮料剩余数量的正整数倍

3. 满足1、2的同时，不能超额喝饮料，也就是说剩下2瓶的时候不能喝大于2瓶的数量。

4. 每个人在自己的回合如果能喝完剩下的其中一种饮料，那么就获得胜利。

   例如A=10，B=2。

   小西只能喝快乐水，且只能喝2/4/6/8/10瓶快乐水。小西可以喝10瓶快乐水直接获得胜利。

   小西和室友都是肥宅，所以他们都会才采取为了胜利最优的行动。

   现在请你判断小西是否能赢得胜利。

输入描述:

第一行输入一个整数T，表示有T组数据

接下来T行，每行为一组数据，每行有两个正整数表示A和B的初始数量

1 ≤ T ≤ 500 , 1 ≤ A,B ≤ 10^12

输出描述:

对于每组数据，若小西可以获得胜利则输出一行“wula”，否则输出一行“mmp”，不需要输出引号

你真的会GCD吗

这道题其实就和求GCD的过程有关。

求GCD的过程就是GCD( a , b ) = GCD( b , a % b )，其过程就是把 a 减去 b 的正整数倍，然后依次递归求解。

那么对于这个题，最后的状态一定是一个数量为 0 ，一个数量为正整数。而逆推就可以得到题目给出的 A , B 值。

1. 假设 A < 2 * B,那么接下来的操作之后一定是（ A - B , B），接下来也一直持续这个过程，而且这个过程是可以一直递推求出来唯一解的。

2. 假如 A > 2 * B , 那么因为两人足够聪明，接下来的状态可以变为（ A , A%B）或者（ A , A % B + A ）。

可以看到，第二个状态只能有一种操作：（ A , A % B + A ）- >（ A , A%B）,因此这个时候可操作的人就能够随意挑选这两种状态之一来掌握自己的胜负。

3. 假设A % B=0 那就不多说了，直接就赢了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

using namespace std;

# define ll long long

int ()
{
	ll t,a,b;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld %lld",&a,&b);
		ll flag=1;
		while(true){//遇到可以判断赢家的条件时，循环就结束了 
			if(a>b) swap(a,b);
			if(b%a==0) break;
			else if(a*2<b) break;
			else{
				flag*=-1;
				b=b-a;
			}
		}
		if(flag==1){
			printf("wulan");
		}
		else{
			printf("mmpn");
		}
	}
	return 0;
}