题解：CF2004E Not a Nim Problem

· · 题解

憋，没有发现 1 可以操作一步变成 0 虚空思考 10min 样例怎么会对的。

游戏扔上 dag 考虑，建边，容易发现对于 u<v 不存在边 (u,v) 当且仅当 u|v 且 u\ne 1 或者 u=0 且 v\ne 1。

然后手推一下发现 \text{SG}(1)=1,\text{SG}(2)=0，后面的我们发现每个奇数都可以到 2 故不为 0，每个偶数都不能到偶数故都是 0。

然后发现对于质数，每个小于它的正整数都可以取到，合数则不能取到它的质因子。

小的奇质因子打表后发现恰等于其质数排名，然后合数又不会超过前面的数，故归纳可得奇质因子的 \text{SG} 值恰等于其质数排名。

于是埃筛一下就好了。

时间 O(n\log \log n)。

#include<bits/stdc++.h>
#define int long long
#define N 10000000
using namespace std;
int sg[N+5],tp;
signed main(){
    for(int i=2;i<=N;i++)
    if(!sg[i]){
        sg[i]=++tp;
        for(int j=i*i;j<=N;j+=i)
        if(!sg[j])sg[j]=tp;
    }
    sg[1]=1;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int ans=0;
        while(n--){
            int x;
            cin>>x;
            if(x%2)
            ans^=sg[x];
        }
        if(ans)puts("Alice");
        else puts("Bob");
    }
    return 0;
}
// 接著他就说，既然你能喜欢这个游戏到变得这么厉害的程度，教你玩也就值得了。
// 当然他自己也有骨气，并不打算就这样一直输下去。
// 他会变得更强，然后立刻还以颜色，所以记著吧──

// ──结果，他是个骗人的堕鬼。

// 在那之后，他根本一次也没有还以颜色。