这是一道很神奇的题，神奇的地方在于全网这个模型只有这题
什么是Every SG？
不同于普通的ICG，它由多个游戏同时进行，且必须同时进行
比如这道题，要求先手一次对所有石头堆都要操作
显然对于单独的每种情况，我们都可以求出这是必败态还是必胜态
现在摆在我们眼前的就有一堆游戏，对于每个游戏，你其实是提前知道了哪些会输，哪些会赢...
那还要玩吗，要的！
因为有很多游戏，所以对于自己能赢的，当然要努力坚持到最后，也就是尽可能拖时间
那对于自己能输的，就是对方能赢的，对方想尽力拖时间，自己就想速战速决
哪怕已经提前知道了输赢，也不是不能翻盘的——
启发了我们可以在求SG函数的时候一起求出从该状态走到某状态的游戏次数，称为step(有点概率dp里，设dp[s]为状态s到末态还要走多少步的感觉)
根据SG函数的定义:
如果能走到必败态，则当前态是必胜态，则转移方程为:
为什么要求SG[a][b-i]?当然是希望置对方于必败态啦，只能从必败态的step更新过来
同样的,如果只能走到必胜态，则当前态是必败态:
求出step以后，感性感觉一下，最重要的是其中step最大的。
显然的，如果(max)Step==奇数，则先手必胜，否则先手必败。
至于为什么"最重要的是其中step最大的"呢？其实严谨证明俺也不是特别特别明白
#include<bits/stdc++.h> using namespace std; const int N=1005; int vis[N][N],step[N][N],sg[N][N]; int dfs(int a,int b){ if(a>b) swap(a,b); //cout<<a<<" : "<<b<<endl; if(vis[a][b]) return sg[a][b]; vis[a][b]=1; if(!a||!b){ //cout<<a<<" "<<b<<" "<<step[a][b]<<endl; sg[a][b]=sg[b][a]=0; step[a][b]=step[b][a]=0; return 0; } int mx=-1,mi=INT_MAX; for(int i=a;i<=b;i+=a){ if(!dfs(a,b-i)){ sg[a][b]=1; mx=max(mx,step[a][b-i]); } else mi=min(mi,step[a][b-i]); } if(sg[a][b]){ step[a][b]=step[b][a]=mx+1; } else step[a][b]=step[b][a]=mi+1; //cout<<a<<" "<<b<<" "<<step[a][b]<<endl; return sg[a][b]; } int main(){ //freopen("lys.in","r",stdin); int t; while(scanf("%d",&t)!=EOF){ int mx=-1; for(int i=1;i<=t;i++){ int l,r;cin>>l>>r; dfs(l,r); mx=max(mx,step[l][r]); } //cout<<mx<<endl; if(mx%2) cout<<"MM"<<endl; else cout<<"GG"<<endl; } }