link

题目大意

MM 和 GG 在玩 $N$ 个同时进行的取石子游戏。

对于一个游戏，有两堆石子 $x,y(x\le y)$. 每一次操作可以从 $y$ 中取走正整数倍的 $x$ 个石子。

对于这些游戏，如果在最后一个结束的游戏中胜出，就判定为整个游戏胜出。

题解

注意游戏是同时进行。

every sg 的典例。

显然，对于必胜的游戏，越晚结束越好，反之越早结束越好。

首先要知道单个游戏的小结论：若 $2x\le y$，则当前必胜。否则有唯一方案（$y=y-x$）.

当 $2x>y$，有唯一方案。此时 $sg(x,y)$ 的值与 $(x,y)$ 的后继的 $sg$ 值相反。也就是 $sg(x,y)=!sg(y-x,x)$. 显然步数加 $1$.

当 $2x\le y$，若 $sg(y\%x,x)\ne 0$，步数加 $2$. 由于 $sg(y\%x,x)$ 不为$0$，即 $(y\%x,x)$ 时必胜。此时只要让 $y=y\%x+x$ 即可。此时对方只能走到 $(y\%x,x)$，由你面对 $(y\%x,x)$ 的局面，则你必胜。

若 $sg(y\%x,x)=0$，步数加 $1$. 只需要一步走到 $sg(y\%x,x)=0$ 即可。可以证明，中间态的 $sg$ 值一定不等于 $0$. 因为中间态 (y′,x)(y',x)(y′,x) 一定能走到 $(y\%x,x)$，而 $(y\%x,x)$ 是必败态。

最后只需要将必胜局的最大步数与必败局的最大步数比较即可。

$sg$ 函数的时间复杂度约等于 $gcd$，所以总的时间复杂度为 $O(n\log n)$.

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, bs;
int sg(int x, int y) {if (x > y) swap(x, y);if (!x) return 0;if (y < 2 * x) {bs++;return !sg(y - x, x);}if (sg(y % x, x)) bs += 2;else bs++;return 1;
}
int main() {while (scanf("%d", &n) != EOF) {int maxw = 0, maxl = 0, a, b;while (n--) {scanf("%d%d", &a, &b);bs = 0;if (sg(a, b)) maxw = max(maxw, bs);else maxl = max(maxl, bs);}if (maxw > maxl) printf("MM\\n");else printf("GG\\n");}return 0;
}

END