题解归档 - cf1198F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1198F
• 本地来源：problems/cf1198F/idea.md
• 题目链接：https://codeforces.com/contest/1198/problem/F
• 原始标题：cf1198F GCD Groups 2

思路

cf1198F GCD Groups 2

题意

将 $n$ 个正整数分成两个非空组，使每组内所有数的 $\gcd$ 均为 $1$。输出是否存在及一种分组方案。

思路

随机贪心（主解，$n \le 10^5$）

关键观察：每个 $a_i \le 10^9$ 的不同质因子个数 $\le 9$。

随机打乱下标后，固定前两个数分别放入组 $1$、组 $2$。对其余元素贪心：若当前数能被组 $1$ 的 $\gcd$ 整除，则放入组 $2$（并更新组 $2$ 的 $\gcd$），否则放入组 $1$。这样每次加入都会让对应组的 $\gcd$ 变小或不变。

若最终两组 $\gcd$ 均为 $1$，则成功。重复随机打乱若干次（约 $2000$ 次或 $10^7/(20n)$ 取小），失败则输出 NO。

有解时单次随机成功概率极高；无解时（如样例 $6,10,15,1000,75$）始终失败，正确输出 NO。

小数据暴力（对拍用，$n \le 18$）

枚举组 $1$ 的非空真子集（位掩码 $1 \ldots 2^n-2$），检查两组 $\gcd$ 是否均为 $1$，取字典序最小的合法方案。

复杂度

• 随机：期望 $O(n)$ 每次尝试，尝试次数常数级。
• 暴力：$O(2^n \cdot n)$，仅用于 $n \le 18$ 或对拍小数据。

参考

• CF 1198F
• 题解博客

代码

来源：problems/cf1198F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:19:10
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e5+5;
ll n,i,j,k,zc,pd,cur,dq,cnt,ans,g1,g2;
ll a[maxn],c[maxn],pref[maxn],suff[maxn];
vector<ll>pr;
vector<ll>fac[maxn];
map<ll,ll>mp;
void sieve(){
    ll i,j;
    for(i=2;i<=32000;i++){
        if(!pr.size() or pr.back()<i){
            zc=1;
            for(j=0;j<(ll)pr.size() and pr[j]*pr[j]<=i;j++)
                if(i%pr[j]==0){zc=0;break;}
            if(zc) pr.push_back(i);
        }
    }
}
void factor(ll id){
    ll x=a[id],p;
    fac[id].clear();
    for(p=0;p<(ll)pr.size() and pr[p]*pr[p]<=x;p++){
        if(x%pr[p]==0){
            fac[id].push_back(pr[p]);
            mp[pr[p]]++;
            while(x%pr[p]==0) x/=pr[p];
        }
    }
    if(x>1){
        fac[id].push_back(x);
        mp[x]++;
    }
}
ll out(){
    for(i=1;i<=n;i++){
        g1=0;
        g2=0;
        for(j=1;j<=n;j++){
            if(c[j]==1) g1=__gcd(g1,a[j]);
            else g2=__gcd(g2,a[j]);
        }
        if(g1!=1 or g2!=1) return 0;
    }
    cout<<"YES\n";
    for(i=1;i<=n;i++) cout<<c[i]<<" ";
    cout<<"\n";
    return 1;
}
ll brute(){
    ll mask;
    for(mask=1;mask<(1ll<<n)-1;mask++){
        for(i=1;i<=n;i++){
            if(mask&(1ll<<(i-1))) c[i]=1;
            else c[i]=2;
        }
        if(out()) return 1;
    }
    cout<<"NO\n";
    return 0;
}
int main(){
    cin>>n;
    g1=0;
    for(i=1;i<=n;i++){
        cin>>a[i];
        g1=__gcd(g1,a[i]);
    }
    if(g1>1){
        cout<<"NO\n";
        return 0;
    }
    if(n<=18) return brute(),0;
    for(i=1;i<=n;i++){
        if(a[i]!=1) continue;
        dq=0;
        for(j=1;j<=n;j++)
            if(j!=i) dq=__gcd(dq,a[j]);
        if(dq==1){
            for(j=1;j<=n;j++) c[j]=(j==i?1:2);
            if(out()) return 0;
        }
        for(j=1;j<=n;j++){
            if(j==i) continue;
            dq=0;
            for(k=1;k<=n;k++)
                if(k!=i and k!=j) dq=__gcd(dq,a[k]);
            if(dq==1){
                for(k=1;k<=n;k++){
                    if(k==i or k==j) c[k]=1;
                    else c[k]=2;
                }
                if(out()) return 0;
            }
        }
    }
    pref[1]=a[1];
    for(i=2;i<=n;i++) pref[i]=__gcd(pref[i-1],a[i]);
    suff[n]=a[n];
    for(i=n-1;i>=1;i--) suff[i]=__gcd(suff[i+1],a[i]);
    for(i=1;i<n;i++){
        if(pref[i]==1 and suff[i+1]==1){
            for(j=1;j<=n;j++) c[j]=(j<=i?1:2);
            if(out()) return 0;
        }
    }
    sieve();
    for(i=1;i<=n;i++) factor(i);
    for(i=1;i<=n;i++){
        pd=0;
        for(j=0;j<(ll)fac[i].size();j++)
            if(mp[fac[i][j]]==1){pd=1;break;}
        if(!pd) continue;
        for(j=1;j<=n;j++) c[j]=2;
        c[i]=1;
        g1=a[i];
        if(g1!=1){
            zc=0;
            for(j=1;j<=n;j++){
                if(j==i) continue;
                if(__gcd(g1,a[j])==1){
                    c[j]=1;
                    zc=1;
                    break;
                }
            }
            if(!zc) continue;
        }
        if(out()) return 0;
    }
    cout<<"NO\n";
    return 0;
}