GG and MM
结论
题意：
每组给n个游戏，每个游戏有两堆石头，GG和MM轮流操作，操作规则：
从两堆里面选出一堆，假设这堆石头有x个，然后在另一堆里取k*x个石头(k是正整数)
谁不能取石头谁输，MM先手。
思路：
这是一个every——sg游戏。
决定总游戏胜负的是最后一局游戏的胜负。因为不能取石头的情况就已经是最后一局了，所以之前的游戏胜负情况没有意义。
那么为了自己能赢，对于自己会赢的游戏，我肯定想尽可能地延长时间，对于自己会输的游戏，我肯定想尽可能地结束。
那么可以找出每一局所走的时间，最后进行判断即可。
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define endl '\n'
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef pair
<int, int> pii
;
const double pi
= acos(-1.0);
const double eps
= 1e-7;
const int inf
= 0x3f3f3f3f;
inline ll
read() {
ll f
= 1, x
= 0;
char c
= getchar();
while(c
< '0' || c
> '9') {
if(c
== '-') f
= -1;
c
= getchar();
}
while(c
>= '0' && c
<= '9') {
x
= (x
<< 1) + (x
<< 3) + (c
^ 48);
c
= getchar();
}
return f
* x
;
}
const int N
= 1e3 + 10;
int a
[N
], b
[N
], sg
[N
][N
], step
[N
][N
];
int get_sg(int x
, int y
) {
if(x
> y
) swap(x
, y
);
if(sg
[x
][y
] != -1) return sg
[x
][y
];
if(!x
|| !y
) return sg
[x
][y
] = step
[x
][y
] = 0;
int tempx
= y
% x
, tempy
= x
;
int k
= y
/ x
;
if(k
== 1) {
sg
[x
][y
] = get_sg(tempx
, tempy
) ^ 1;
step
[x
][y
] = step
[tempx
][tempy
] + 1;
return sg
[x
][y
];
}
else {
step
[x
][y
] = get_sg(tempx
, tempy
) + step
[tempx
][tempy
] + 1;
return sg
[x
][y
] = 1;
}
}
int main() {
memset(sg
, -1, sizeof sg
);
int n
;
while(scanf("%d", &n
) != EOF) {
int maxn
= 0;
for(int i
= 1; i
<= n
; i
++) {
int x
, y
;
scanf("%d %d", &x
, &y
);
if(x
> y
) swap(x
, y
);
get_sg(x
, y
);
maxn
= max(maxn
, step
[x
][y
]);
}
puts(maxn
& 1 ? "MM" : "GG");
}
return 0;
}
