题解：CF2200E Divisive Battle

fafdddb · 2026-03-06 18:00:10 · 题解

分析一下，发现两人的最优策略均为每次操作把某个数分成一个质数和另一个数字的乘积。

那么我们对每个数字分解质因数，如果这个数字是质数就无法分解，否则如果有两个质因数或以上就一定是 Alice 赢。为什么呢？因为 Alice 可以把这个数字分解出最大的那个质因数放到前面，然后剩下的那个数字无论如何都要分解，一定会变成递减序列。

然后我们把每个数字换成这个数字的质因数来判断是否递增即可。因为最终分解的形式肯定是形如 k 个该质因数排在一起。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],vis[N],prime[N],cnt=0,p[N];
void work(int n){
    for(int i=2;i<=n;i++) {
        if(!vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt;j++) {
            if(i*prime[j]>n)break;
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
inline bool solve(int n){//true就是Alice赢 
    bool f=true;
    for(int i=1;i<=n-1;i++){
        if(a[i]>a[i+1]){
            f=false;
            break;
        }
    }
    if(f)return false;
    for(int i=1;i<=n;i++){
        int num=a[i],c=0,d;
        if(num==1||p[num])continue;
        for(int j=1;j<=cnt;j++){
            if(num<prime[j])break;
            if(num%prime[j]==0){
                while(num%prime[j]==0)num=num/prime[j];
                c++;d=prime[j];
            }
            if(c==2)return true;
        }
        a[i]=d;
    }
    f=false;
    for(int i=1;i<=n-1;i++){
        if(a[i]>a[i+1]){
            f=true;break;
        }
    }
    return f;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    work(N-10);
    for(int i=1;i<=cnt;i++)p[prime[i]]=1;
    while(T--){
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        if(solve(n))cout<<"Alice\n";
        else cout<<"Bob\n";
    }
    return 0;

}