题目大意

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

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

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

题解

注意游戏是同时进行。

every sg 的典例。

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

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

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

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

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

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

s g sg sg 函数的时间复杂度约等于 g c d gcd gcd，所以总的时间复杂度为 O ( n log ⁡ n ) O(nlog n) O(nlogn).

代码

#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
");
        else printf("GG
");
    }
    return 0;
}

END