前言
比赛的时候没学过SG函数的蒟蒻以为是道结论题，但是不是QwQ
和dummyummy巨佬一起推了*个小时的规律
最后去问了真正的巨佬__stdcall
__stdcall面带微笑的告诉我们，这是SG函数的板子题
QwQ
被卡科技了
体验极差
正文
题目
链接：https://www.nowcoder.com/acm/contest/161/B
来源：牛客网
题目描述
小N和小O在玩游戏。他们面前放了n堆石子，第i堆石子一开始有ci颗石头。他们轮流从某堆石子中取石子，不能不取。最后无法操作的人就输了这个游戏。但他们觉得这样玩太无聊了，更新了一下规则。具体是这样的：对于一堆有恰好m颗石子的石头堆，假如一个人要从这堆石子中取石子，设他要取石子数为d，那么d必须是m的约数。最后还是无法操作者输。
现在小N先手。他想知道他第一步有多少种不同的必胜策略。一个策略指的是，从哪堆石子中，取走多少颗石子。只要取的那一堆不同，或取的数目不同，都算不同的策略。
现在小N先手。他想知道他第一步有多少种不同的必胜策略。一个策略指的是，从哪堆石子中，取走多少颗石子。只要取的那一堆不同，或取的数目不同，都算不同的策略。
输入描述:
第一行一个整数n。
接下来一行n个整数，分别代表每堆石子的石子数目。
数据保证输入的所有数字都不超过\( 10^{5} \)，均大于等于1，且为整数。
输出描述:
一行一个整数代表小$N$第一步必胜策略的数量。
输入
10
47 18 9 36 10 1 13 19 29 1
输出
7
题解
题目让求第一步必胜策略的数量
那就是求第一步走后有多少个状态是必败态
组合的Nim游戏模型
求出SG函数，然后枚举每个数和它的约数
累加一下ans
完毕
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
vector<int> g[];
int qz[],hz[],n,a[],SG[]={},f[];
int ans=,maxa;
void sg(void){
for(int i=;i<=n;i++)
for(int j=;j<=sqrt(a[i]);j++)
if(a[i]%j==){
if(a[i]/j==j)
g[i].push_back(j);
else{
g[i].push_back(j);
g[i].push_back(a[i]/j);
}
}
return;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]),maxa=max(a[i],maxa);
SG[]=;
for(int i=;i<=maxa;i++) {
int tt;
for(int k=,j=;;j*=,k+=) {
if(i%j==*(j/)||i%j==*(j/)) tt=k-;
if(i%j==*(j/)) tt=k;
if(i%j!=) break;
}
SG[i]=tt;
}
sg();
// for(int i=0;i<=maxa;i++)
// printf("SG[%d]=%d\n",i,SG[i]);
for(int i=;i<=n;i++)
qz[i]=qz[i-]^SG[a[i]];
for(int j=n;j>=;j--)
hz[j]=hz[j+]^SG[a[j]];
for(int i=;i<=n;i++){
for(int j=;j<g[i].size();j++)
if(!((qz[i-]^hz[i+])^SG[a[i]-g[i][j]]))
ans++;
}
printf("%d",ans);
return ;
}