CF2004E
套用 SG 函数的结论,我们先打单个游戏的表再异或即可得到答案。首先对于一个大小为 \(i\) 的堆有 \(SG[i]=\text{mex}_{j\bot i}\{SG[j]\}\),容易暴力 dp。
int SG[N];
int f(int x) {if(SG[x]!=-1) return SG[x];if(x==0) return SG[0]=0;vector<int> g;up(i,1,x) if(__gcd(i,x)==1) g.pb(f(x-i));sort(g.begin(),g.end());if(g[0]>0) return 0;up(i,0,(int)g.size()-2) if(g[i]+1!=g[i+1]&&g[i]!=g[i+1]) return g[i]+1;return g[g.size()-1]+1;
}
观察到结论,首先 \(SG[0]=0,SG[1]=1\),然后第 \(i\) 个质数的 SG 值是 \(i\) 强相关的,合数的 SG 是最小质因子的 SG,线性筛求出即可。