题解：CF2200E Divisive Battle

· · 题解

闲话

模拟赛切了，但是因此没有时间打下一题了。。。

正文

思路

先特判一开始有序的情况。

然后我们想想，对于一个质数，明显是不可能拆成两个数的。

而对于一个合数，可以考虑把它质因数分解。假如拆出来的质数并不是同一个数，也就是说，它至少可以分成两个有大有小的质数，那么只要把大的一个放在前面，\text{Alice} 就赢了，因为你显然不可能把质数再拆了嘛。

那其实还有一种情况，就是说一个数恰好是某一个质数的几次幂，就是只能拆出一种质数，那么显然对于这个数展开后的情况，它的因数在数列中的相对位置，其实和它在原数列中的位置是相等的。那么，如果这些数展开后都是非递减的，就是 \text{Bob} 赢。

怎么实现呢？

我们考虑埃式筛的过程，就是把每个质数的倍数都筛出来。那就维护一个 cnt 数组，表示 i 这个数被 cnt_i 个质数筛过。很明显，只要有一个数列中的数 x 满足 cnt_x > 1，那就说明它可以拆成两种质数，那就是 \text{Alice} 赢。

如果数列中的数都是质数或者是质数的几次幂，就用它们的质因子代替它们，然后看这些质因子是不是非递减的即可。

显然，可以在埃式筛的过程中，维护每个数的最小质因子，这样上述过程就都是 \Theta(n) 的了，仅仅只是预处理埃式筛需要较多时间，但是也就是 \Theta(V\log V) 的，其中 V 表示值域大小。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10,N=1e6+10;
int a[N],is[N],minn[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    memset(minn,0x3f3f,sizeof(minn));
    minn[1]=1;
    FOR(i,2,N-10){
        if(!is[i]){
            minn[i]=i;
            for(int j=2*i;j<=N-10;j+=i) is[j]++,minn[j]=min(minn[j],i);
        }
    }
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        bool flsort=true;
        FOR(i,1,n) cin>>a[i];
        if(n==1){
            cout<<"Bob\n";
            continue;
        }
        FOR(i,2,n) if(a[i]<a[i-1]) flsort=false;
        if(flsort){
            cout<<"Bob\n";
            continue;
        }
        bool fl=true;
        FOR(i,1,n){
            if(is[a[i]]>=2){//Alice win
                fl=false;
                break;
            }
            a[i]=minn[a[i]];
        }
        FOR(i,2,n) if(a[i]<a[i-1]) fl=false;//Alice win
        if(!fl) cout<<"Alice\n";
        else cout<<"Bob\n";
    }
    return 0;
}