GG and MM测试Kotsg的博客-

原题
GG and MM like playing a game since they are children. At the beginning of game, there are two piles of stones. MM chooses a pile of stones first, which has x stones, and then she can choose a positive number k and remove kx stones out from the other pile of stones, which has y stones (I think all of you know that y>=kx – -!). Then it comes the turn of GG, followed the rules above-mentioned as well. When someone can’t remove any stone, then he/she loses the game, and this game is finished.
Many years later, GG and MM find this game is too simple, so they decided to play N games at one time for fun. MM plays first, as the same, and the one on his/her turn must play every unfinished game. Rules to remove are as same as above, and if someone cannot remove any stone (i.e., loses the last ending game), then he/she loses. Of course we can assume GG and MM are clever enough, and GG will not lose intentionally, O(∩_∩)O~
Input
The input file contains multiply test cases (no more than 100).
The first line of each test case is an integer N, N<=1000, which represents there are N games, then N lines following, each line has two numbers: p and q, standing for the number of the two piles of stones of each game, p, q<=1000(it seems that they are so leisure = =!), which represent the numbers of two piles of stones of every game.
The input will end with EOF.
Output
For each test case, output the name of the winner.
Sample Input
3
1 1
1 1
1 1
1
3 2
Sample Output
MM
GG

Translate:
GG和MM从小就喜欢玩游戏。游戏开始时，有两堆石头。MM首先选择一堆石头，其中有x个石头，然后她可以选择一个正数k，从另一堆石头中取出kx个石头，其中有y个石头（我想你们都知道y>=kx–！）。接下来是GG的轮换，也遵循了上述规则。当有人不能移除任何石头时，他/她将输掉游戏，游戏结束。

很多年后，GG和MM发现这个游戏太简单了，所以他们决定一次玩N个游戏。MM先玩，同样，轮到他/她玩的必须是每一个未完成的游戏。移除规则与上述相同，如果有人无法移除任何石头（即，输掉最后一场比赛），则他/她将输掉。当然我们可以假设GG和MM足够聪明，GG不会故意输，O（∩∩∩）~
输入
输入文件包含多个测试用例（不超过100个）。
每个测试用例的第一行是一个整数N，N<=1000，表示有N个游戏，接下来的N行，每行有两个数字：p和q，代表每个游戏的两堆石头的数量，p，q<=1000（看起来他们是如此的休闲=！），表示每场比赛的两堆石头的数量。
输入将以EOF结束。
输出
对于每个测试用例，输出获胜者的名称。
Sample Input
3
1 1
1 1
1 1
1
3 2
Sample Output
MM
GG

大体思路：
这个就像下棋一样，最后一步是制胜的关键，所以我们看谁能走到最后一步，走的多的人自然赢的几率大。写一个函数，求步数，谁的最大步数最多，谁就赢了（具体细节请看代码）
代码：

#include <bits/stdc++.h> using namespace std; int sum; int f(int p,int q){  if(p<q)   swap(p,q);//确保p比q大  if(!q) return 0; //说明正在搬石头的人已经输了  if(!f(q,p%q)){ //如果下一个人没法办了，说明这个人赢了（g或m）   sum++;   return 1;  }  if(p/q>1){ //不留或留q个，使局面对我更有利   sum+=2;   return 1;  }   sum++;  return 0; } int main() {  int n;  while(scanf("%d",&n)!=EOF){   int g=0,m=0;   for(int i=0;i<n;i++){    int p,q;    scanf("%d%d",&p,&q);    sum=0;    if(f(p,q))     g=max(g,sum);    else m=max(m,sum);   }   if(g>m) printf("MMn");   else printf("GGn");  }  return 0; }