哎，被卡科技了，想了三個小時，最後還是大佬給我說是\(SG\)函數。
\(SG\)函數，用起來很簡單，證明呢？（不可能的，這輩子都是不可能的）
\(SG\)定理
遊戲的\(SG\)函數就是各個子遊戲的\(SG\)函數的\(Nim-sum\)（就是異或和），比如多堆石子的\(SG\)函數就是所有單堆石子\(SG\)函數的異或和。
\(SG\)函數
首先定義\(mex(T)\)為\(T\)中未出現的自然數中最小的數，其中\(T \subset N\)，如\(mex(0,2,3)=1\)，\(mex(4,7)=0\)。那麼\(SG(x)=mex(S)\)，\(S\)為\(x\)的後繼狀态的\(SG\)函數值集合。
然後，對于某一個狀态\(x\)，若\(SG(x)=0\)，則先手必敗，否則先手必勝。
對于這一道題，因為隻能拿約數個，也就是至少拿一個，是以我們可以先從小到大預處理一下\(SG\)函數。然後因為我們是先手，要給對手制造一個必敗狀态，是以隻要枚舉一下第一步的所有政策，然後判斷一下剩下的那些石子的\(SG(x)\)函數的異或和是否為\(0\)就行了。
期望複雜度\(O(n^{\frac{3}{2}})\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int n, a[N+5], sum, p, ans, SG[N+5], vis[N+5];
void calc_SG() { //預處理SG函數
SG[0] = 0, SG[1] = 1; //初始化
for(int i = 2; i <= N+1; i++) {
int cnt = 0, t = 0x3f3f3f3f;
for(int j = 1; j*j <= i; j++)
if(i%j == 0) {
vis[++cnt] = SG[i-j];
if(j*j != i) vis[++cnt] = SG[i-i/j];
}
sort(vis+1, vis+cnt+1);
if(vis[1] >= 1) { //計算mex(T)
SG[i] = 0;
continue;
}
for(int j = 1; j <= cnt-1; j++)
if(vis[j+1]-vis[j] > 1) t = min(t, vis[j]+1);
t = min(t, vis[cnt]+1);
SG[i] = t;
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); //讀入輸出加速
cin >> n;
calc_SG(); //預處理SG函數
for(int i = 1; i <= n; i++) cin >> a[i], sum ^= SG[a[i]];
for(int i = 1; i <= n; i++) {
p = sum^SG[a[i]];
for(int j = 1; j*j <= a[i]; j++) {
if(a[i]%j) continue;
if((p^SG[a[i]-j]) == 0) ans++; //判斷剩下的Nim-sum是否為0
if(j*j != a[i] && (p^SG[a[i]-a[i]/j]) == 0) ans++;
}
}
cout << ans << endl;
return 0;
} 轉載于:https://www.cnblogs.com/dummyummy/p/9570163.html