参考自 石家庄二中 贾志豪 IOI2009国家集训队论文 《组合游戏略述—— 浅谈 SG 游戏的若干拓展及变形》
一、定义
游戏规则加上 对于还没有结束的所有单一游戏，游戏者必须对其进行决策
二、结论
对于必胜的单一游戏，游戏者希望玩的越久越好
对于必败的单一游戏，游戏者希望越早结束越好
因为Every-SG 游戏的获胜方取决于坚持到最后的游戏者
所以
对于必胜态，需要知道最慢几步可以结束游戏
对于必败态，需要知道最快几步可以结束游戏
令step表示结束游戏的步数
那么
若状态S是结束状态，那么step(s)=0
若状态S是先手必胜态，那么step(s)=max（step(t)）+1，其中满足t是先手必败态
若状态S是先手必败态，那么step(s)=min（step(s)）+1
定理：
Every-SG 游戏先手必胜当且仅当单一游戏中最大的step为奇数。
三、证明
要证明结论的正确性，需证明以下三点：
1、若S为先手必胜态，则step(s)=奇数，否则step(s)=偶数
因为Every-SG 游戏的获胜方取决于坚持到最后的游戏者，所以游戏的获胜方取决于最大的step。
2、设最大的step为step_max，那么获胜方要保证游戏 在>=step_max 步结束
3、设最大的step为step_max，那么获胜方要保证所有的必败单一游戏在<=step_max步结束
这两点显然
证明1：数学归纳法，终止状态为先手必败态，step=0=偶数，往前推即可
证明2：
设step最大的单一游戏为A，获胜方为W
W总在A处于先手必胜态时移动A的状态，而它又希望游戏持续时间越长越好，所以只会使A的step减少1
对方总是在A处于先手必败态时移动A的状态，而处于先手必败态时，step是后继状态的step取min+1，所以对方至多使step减少1
这里的减少x指转移到step-x的后继状态
所以 游戏在>=step_max 步内结束
证明3：
设获胜方为W，其某一个必败单一游戏为B
W总是在B处于先手必败态时移动B的状态，所以他希望这个游戏越早结束越好，此时的step是后继状态的step取min+1，所以W一定会使step减少1
对方总是在B处于先手必胜态时移动B的状态，此时step是后继状态的step取max+1，所以对方至少使step减少1
所以游戏B在<=step_max 步结束
四、例题
题意：
N组石子，每组有两堆，每次可以从一堆中取走另一堆的倍数个石子，N组石子同时操作
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; #define N 1001 int sg[N][N];
int step[N][N]; int find(int a,int b)
{
if(a>b) swap(a,b);
if(sg[a][b]!=-) return sg[a][b];
int mi=1e9,mx=-;
for(int i=a;i<=b;i+=a)
if(!find(a,b-i))
{
sg[a][b]=sg[b][a]=;
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+;
return true;
}
step[a][b]=step[b][a]=mi+;
return sg[a][b]=sg[b][a]=;
} int main()
{
int n,a,b;
int ans;
memset(sg,-,sizeof(sg));
for(int i=;i<N;++i) sg[][i]=sg[i][]=;
while(scanf("%d",&n)!=EOF)
{
ans=;
for(int i=;i<=n;++i)
{
scanf("%d%d",&a,&b);
find(a,b);
ans=max(ans,step[a][b]);
}
puts(ans& ? "MM" : "GG");
}
}