传送门：https://ac.nowcoder.com/acm/contest/283/D
题目描述
小西买了一堆肥宅快乐水和肥宅快乐茶，准备和室友比谁更肥宅。
快乐水有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的初始数量
输出描述:
对于每组数据，若小西可以获得胜利则输出一行“wula”，否则输出一行“mmp”，不需要输出引号
题意概括：如题
解题思路：
模拟一遍，博弈的规律很清晰。
处理一下保证 A > B,并且两者除掉GCD缩小范围，最后得出结果是等价的（两者除以相同倍数，和每次做减法是减少相同的数，对最后能否整除没有影响）。
递归判断 cheak（A， B，cnt）是先手赢或是后手赢，cnt用于记录奇偶性（由当前结果回溯到最初的结果）
①如果当前 A%B == 0 先手赢
②如果当前 A/B >= 2 先手赢 （因为我存在至少两种选择，里面必有一种是失败的，而另外一种肯定是胜利的）
为什么呢？
如果A/B == 2 ，我们至少拥有减 2 个 B的权利，如果我减一个B最后导致我失败了对手胜利了，那我肯定减两个B，就相当于我通过多减一个B跳过了一步，而我成为了成功的那个对手。
如果减一个B成功了，那就成功啦
如果 A/B > 2, 我们其实还是回到上面的结论，减一个或减两个，其余的都是附加在这一个或者两个上的，保证奇偶性即可。
③以上两种情况不满足说明当前状态无法判断谁会获胜，需要做一次减法 A-B，递归 cheak（ A-B，B，++cnt）或者check（B，A-B，++cnt）判断接下来那个会获胜，因为记录了奇偶性，最后可以回溯到最初状态。
AC code：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #define LL long long 6 using namespace std; 7 LL a, b; 8 9 LL GCD(LL a, LL b) 10 { 11 if(b == 0) return a; 12 return GCD(b, a%b); 13 } 14 15 bool check(LL A, LL B, LL cnt) 16 { 17 LL gg = GCD(A, B); 18 A = A/gg; 19 B = B/gg; 20 LL t = A/B; 21 if(A%B == 0) { 22 if(cnt%2LL) return true; 23 else return false; 24 } 25 else if(t >= 2){ 26 27 if(cnt%2LL) return true; 28 else return false; 29 30 } 31 else{ 32 if(B%(A-B) == 0) { 33 if(cnt%2LL)return false; 34 else return true; 35 } 36 else{ 37 if(B > (A-B)) return check(B, (A-B), ++cnt); 38 else return check((A-B), B, ++cnt); 39 } 40 } 41 return true; 42 } 43 44 int main() 45 { 46 int T_case; 47 LL tt, cnt = 1LL; 48 LL G; 49 scanf("%d", &T_case); 50 while(T_case--){ 51 cnt = 1LL; 52 scanf("%lld %lld", &a, &b); 53 if(a < b) swap(a, b); 54 if(a%b == 0) puts("wula"); 55 else{ 56 G = GCD(a, b); 57 a = a/G; 58 b = b/G; 59 if(check(a, b, 1LL)) puts("wula"); 60 else puts("mmp"); 61 } 62 } 63 return 0; 64 }