时隔一年半，主播再次回到博弈论。这次是练习时间！！！
如果你没有学过SG定理或者想要复习一下
如果没有看过之前的前置文章的可以先看零基础知识讲解。 Episode 1（Nim基础）：https://blog.csdn.net/2401_84512298/article/details/141559570?spm=1001.2014.3001.5502 Episode 2（SG定理）：https://blog.csdn.net/2401_84512298/article/details/141563982 为了和我一样没有买会员的小伙伴，我把之前的文章设成公开了。
简单复盘
每个状态都有一个 SG 函数值，比如在基本的取石子问题中，一堆有
x
x
x 个石子就是一种状态。没有石子（零个）的 SG 值就是
0
0
0（即必输的局面）。求的方法是通过状态的转移方式建立出一个以状态为节点，转移为单向边的 DAG。比如
5
5
5 个石子就可以取掉两个，转移到
3
3
3 个石子，所以
5
5
5 到
3
3
3 有一条单向边。当石子变成
n
n
n 堆的时候，就取每一堆的初始状态的 SG 函数值，然后把它们
x
o
r
xor
xor 一下，如果是
0
0
0 就必输，否则先手胜。
例题（先自己做做看）
原题：Codeforces 2004E A 和 B 面前有
n
n
n 堆石子，第
i
i
i 堆有
a
i
a_i
ai 个。每次可以从
x
x
x 个石子的一堆里面拿走
y
y
y 个，需满足
g
c
d
(
x
,
y
)
=
1
gcd(x,y)=1
gcd(x,y)=1。 当然你不能把石子取成负数。如果到某个人的时候他没办法取石子了，他就输了。 这里
a
i
≤
10
7
,
n
≤
3
⋅
10
5
a_i\\le 10^7, \\, n\\le 3\\,·10^5
ai≤107,n≤3⋅105。
思路
这里的状态和复盘中的状态一模一样，都是这一堆还有几个石子。但是转移不一样了，这次每次可以取走一些特定数字的石子，但仍然是一张有向无环图。只要算出所有状态的 SG 函数，取一下初始的
n
n
n 堆所对应的函数值的
x
o
r
xor
xor 就搞定了。可是如果暴力算出每种石子数的 SG 值，那就 TLE 了，因为第一层循环枚举当前在求的状态（
10
7
10^7
107），第二层循环枚举所有小于当前石子数的值 （
10
7
10^7
107），也就是要取的数量。但是我们二话不说，直接开干，看看 SG 值长什么样子再说。 （这里建议读者自己写一下程序找找规律）
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define ll long long
#define endl '\\n'
ll sg[205];
bool have[1005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
sg[0]=0;
cout<<0<<':'<<sg[0]<<endl;
for(int i=1;i<=200;i++){
memset(have,0,sizeof(have));
for(int j=1;j<=i;j++)
if(__gcd(j,i)==1)
have[sg[i–j]]=1;
for(int j=0;j<=1000;j++)
if(!have[j]){
sg[i]=j;
break;
}
cout<<i<<':'<<sg[i]<<endl;
}
return 0;
}
然后我们的输出长这样：（冒号左边为石子数，右边为所对应的 SG 函数值）
读者此时发现：我的天哪！为什么石子个数是偶数（蓝色）的都是
0
0
0，然后那些质数（橙红色）感觉就像是编号一样，一个一个往上加？（
1
1
1 不是质数，只是加上之后才是从
1
1
1 开始加，比较好看，它刚好顶替了
2
2
2 的位置，
2
2
2 虽然是质数，但也是偶数，所以变成
0
0
0 了）更惊喜的是，主播并不知道为什么。 剩下的规律实在有点难，所以主播偷偷去看了一下题解，然后发现居然就是它的最小质因子的 SG 值。比如
25
25
25 就取
5
5
5 的数值，
3
3
3；
77
77
77 就取
7
7
7 的值，
4
4
4。那就很简单了，直接筛选一下质数，然后把 SG 值全算出来就好了。
代码
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define ll long long
#define endl '\\n'
int t,n,a[300005],sg[10000005],id,fac[10000005];
bool np[10000005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
memset(fac,0x3f,sizeof(fac));
sg[1]=1;id=1;
for(int j=2*2;j<=10000000;j+=2) np[j]=1,fac[j]=min(fac[j],2);
for(int i=3;i<=10000000;i++){
if(!np[i]){
sg[i]=++id;
for(int j=i*2;j<=10000000;j+=i)
np[j]=1,fac[j]=min(fac[j],i);
}
}
for(int i=3;i<=10000000;i+=2) if(np[i]) sg[i]=sg[fac[i]];
cin>>t;
while(t—){
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum^=sg[a[i]];
}
if(sum==0) cout<<"Bob\\n";
else cout<<"Alice\\n";
}
return 0;
}
习题
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-chessboard-game/problem 英文题解在评论区提供的 USACO Guide 的讲解当中，如果各位想要我写这道题的题解就发评论里，尽量更新。
