题解：CF2004E Not a Nim Problem

Defy_HeavenS · 2024-08-26 14:21:59 · 题解

题意

Alice 和 Bob 玩游戏，一开始有 n 堆石子，其中第 i 堆有 a_i 颗石子。两个玩家轮流取石子，在一个玩家的回合里，它可以取走任意一堆的任意正数个石子，并满足取石子的数量不能与当前堆的石子数量为互质。

无法再取石子的人输。假设两人都足够聪明，Alice 先取谁会赢？

思路

博弈论，构建 SG 函数。

考虑单堆情况，当个数 x 为偶数时没有先手必胜策略，而 x 为奇数时仅需一步取走 x-2 个石子即可。

暴力转移肯定超时，因为要满足取石子的数量不能与当前堆的石子数量为互质，所以考虑质数。我们打一下表发现现象：

对于所有偶数，SG=0。
对于所有奇数质数 x，满足 \forall 1\le i<x,\gcd(x,i)=1，则 SG(x)=\mathrm{mex}(1,2,\dots,x-1)=SG(x')+1，其中 x' 为上一个质数（特殊地，SG(3)=2），也可以理解为 x 在质数中的排名。
对于所有奇数 x，设其最小质因子为 x'，那么 SG(x)=SG(x')。

仅需通过线性筛，对于每个数求得其最小质因子，即可求得所有 SG 函数，则仅需判断 SG⁡(a_1)\oplus SG(a_2) \oplus \dots \oplus SG⁡(a_n)\ne0 是否成立即可。

证明

采用数学归纳法证明。

首先对于 x\le 2 成立，考虑 x+1。

对于 x+1 是质数，并且其是第 i 个质数，那么 [1,x] 就是其后继状态，然后 [1,i-1] 一定在之前出现过，所以 SG(x+1)=i。
对于 x+1 是偶数，对于一个数 y，若 \gcd(x,y)=1 那么 y 一定是奇数，x+1-y 一定是奇数，[1,x] 中奇数都不为 0，所以 SG(x+1)=0。
对于 x+1 是奇数，其某个质因子 p，那么 p 的倍数一定不能减去，并且 [1,x] 中的 y 满足 SG(y)=SG(p) 的一定有 p\mid y，所以 SG(x+1)<SG(p)，然后 SG(p) 最小的那个就是最小质因子的 SG。

Q.E.D.

代码

赛时代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
const int N=3e5+5,M=1e7+5;
LL n,a[N],cnt,prim[M],mifac[M],sg[M];    //mifac[i] 表示 i 的最小质因子 
bool vis[M];
void get_prime(int n){
    for(int i=2;i<=n;++i){
        if(!vis[i]) prim[++cnt]=i,mifac[i]=i;
        for(int j=1;j<=cnt;++j){
            if(i*prim[j]>n) break;
            vis[i*prim[j]]=1;
            mifac[i*prim[j]]=prim[j];
            if(i%prim[j]==0){
                break;
            }
        }
    }
}
void solve(){
    cin>>n;
    LL sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum^=sg[a[i]];
    }
    if(sum){
        cout<<"Alice";
    }else{
        cout<<"Bob";
    }
    cout<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    get_prime(10000005);
    sg[1]=1,sg[2]=0;
    for(int i=3,cnt=1;i<=10000001;i++){
        if(!vis[i]) cnt++;
        sg[i]=sg[mifac[i]];
        if(!vis[i]){
            sg[i]=cnt;
        }
    }
    int t=1;cin>>t;
    while(t--) solve();
    return 0;
}
/*

*/