萌萌的糖果博弈

题目描述:

用糖果来引诱小朋友学习是最常用的手法，绵羊爸爸就是用糖果来引诱萌萌学习博弈的。他把糖果分成了两堆，一堆有A粒，另一堆有B粒。他让萌萌和他一起按照下面的规则取糖果：每次可以任意拿走其中一堆糖果；如果这时候另一堆糖果数目多于1粒，就把它任意分成两堆，否则就把剩下的一粒糖果取走并获得这次博弈的胜利。胜利者将获得所有的糖果。萌萌想要得到所有的糖果，而绵羊爸爸想把糖果留下以便下一次利用。现在由萌萌先取糖果，旁观的小朋友们想知道萌萌是否有必胜策略。

输入格式:

本题有多组测试数据（不超过100组）。每组数据包括两行，第一行为A，第二行为B。1 ≤ A,B ≤ 2^127。输入数据以一个 -1 结束。

输出格式:

每组数据对应一行输出。如果萌萌获胜则输出”MengMeng”，否则输出”SheepDaddy”（不包括引号）。

样例输入:

样例输出:

MengMeng

SheepDaddy

时间限制:1000ms
空间限制:256MByte

哇，这题感觉是做过的题目中最难的了（博弈论），看了题解的结论之后想了好久才想出来证明方法。。。QAQ。。。我还是太弱了！！！

解法是很简单的（博弈论好像都这样），但是证明真的难死人啊！！！

解法就是两个数都满足%5==3 或者 == 2 就是后手SheepDaddy赢；其他情况是另一个赢/。。。

下面来证明一下解法：

首先证明一个结论：当两个数其中一个是1或者4或者5的时候，先手必胜。这个还是比较好证明的，有两个数A和B，A满足前面的条件，那么你把B拿走，把A分掉就了；注意，如果PERSON1拿完一堆之后剩下一堆的糖果数是1那么PERSON1赢（之前理解错了QAQ）接下来假设有两个人PER1，PER2，这时候有两堆石子，PER1拿完一堆之后另一堆的VAL%5==2或者3；那么PER2有必胜策略！

证明如下：将VAL分了之后肯定有一堆%5！=3或者2。这时候，PER2把这一堆留下，必然可以分成两堆（VAL1,VAL2）并且满足VAL1/2 %5 == 2 或者3；

（自己按着%5为0，1，4分别讨论一下就好了）

那么迟早会有一次在PER2回合VAL==1或者2或者5，就必胜了！

知道了这个还没有用，还要把这个用起来。。。我们考虑第二个人如何有必胜策略，那么就简单了，满足解法的条件就好了呀，不管PER1取那一堆，剩下一堆总会%5==2或者3，就必胜了。然后PER2没有必胜策略的情况就是PER1的必胜情况了。

累死！上代码，超级短。。。

#include<iostream>

using namespace std;

string a,b;

int as,bs;

int main(){

    while(cin >> a)

    {

        if(a == "-1") return ;

        cin >> b;

        as = a[a.length() - ] - '';

        bs = b[b.length() - ] - '';

        if((as %  ==  || as %  == ) && (bs %  ==  || bs %  == )) cout << "SheepDaddy" << endl;

        else cout << "MengMeng" << endl;

    }

}

写的累死人了，不写了。。。