题解：CF2034H Rayan vs. Rayaneh

· · 题解

CF2034H

令 m=100000，即值域大小。

一个集合能且仅能表示集合内所有数 \gcd 的倍数。

考虑对于每个质数，取 \gcd 看成指数取 \min 的形式，一个集合是线性独立的，当且仅当每个元素都至少在一个质数的指数上取到了集合内的唯一最小值。

考虑每个元素取最小值的质数位置，多个位置只保留一个，写成 p_1^{q_1},p_2^{q_2},\dots p_k^{q_k} 的形式，那么其他位置暂且忽略。对于一组 p_1^{q_1},p_2^{q_2},\dots p_k^{q_k}，则这一组合法的充要条件就是对于每个 i\in[1,k]，都存在至少一个 a_x 满足其是 \prod_{j\not=i}{p_j^{q_j+1}} 的倍数，但是不是 \prod {p_j^{q_j+1}} 的倍数。含义就是只对 p_i 这个质数产生贡献。判断有没有这个数可以 O(m\log m) 预处理。

接下来需要求出的就是 k 最大的一组合法的 p_1^{q_1},p_2^{q_2},\dots p_k^{q_k}。

如果枚举的话，\prod{p_i^{q_i+1}} 可能很大，但是发现，其除掉一个 p_i^{q_i+1} 必定小于等于 m，所以 (\min{p_i^{q_i+1}})^{k-1}\le m，当 k>2 的时候，考虑枚举最小的那个质数幂，再枚举 [1,m] 作为其他幂的乘积，check 的时候 O(k) 枚举每个质数幂即可。

这里有个性质，就是答案不会超过 6，因为考虑最小的 7 个质数的乘积，除掉 2 后仍然超过了 m。

分析一下上面的复杂度，有上界 O(TmK\frac{\sqrt{m}}{\log m})，此处 k=6。

剩余的情况是 k=1 和 k=2。k=1 是简单的，k=2 时，如果两个数 x 和 y 能成为答案，则 x\nmid y 且 y\nmid x。因为 a 不重，所以答案为 1 的序列长度不超过 \log m，于是在前 20 个数里枚举配对即可。

代码： 

#include<bits/stdc++.h>
using namespace std;
int T,n,a[100003],ans1,ans2,ans3;
int pri[100003],isp[100003],totp,pm[100003],mnv[100003],k1,k2,k3,k4,k5,k6,k7,k8,k9,flg;
int plst[100003][11],plst2[100003][11];
int stk[11][100003];
int tot[11];
vector<int>ys[100003];
int num[100003];
int getcnt(int X){
    if(X<=100000)return num[X];
    return 0;
}
int pwr(int X,int Y){
    if(Y==1)return X;
    return X*pwr(X,Y-1);
}
void sol(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=100000;i++)num[i]=0;
    for(int i=1;i<=n;i++){
        for(auto j:ys[a[i]])num[j]++;
    }
    ans1=ans2=ans3=-1;
    for(int oo=3;oo<=6;oo++){
        for(int i=2;;i++){
            if(pm[i]>1)continue;
            if(pwr(i,oo-1)>100000)break;
            if(ans1==oo)break;
            for(int jj=1;jj<=tot[oo-1];jj++){
                int j=stk[oo-1][jj];
                if(j%i==0)continue;
                if(i>mnv[j])continue;
                if((i*j/mnv[j])>100000)continue;
                k1=getcnt(i*j);
                flg=(getcnt(j)!=k1);
                for(int u=1;u<=pm[j]&&flg;u++)flg&=(num[i*j/plst2[j][u]]!=k1);
                if(flg){
                    ans2=i;
                    ans3=j;
                    ans1=oo;
                    break;
                }
            }
        }
    }
    if(ans1>2){
        cout<<ans1<<'\n';
        for(int i=1;i<=n;i++){
            if(a[i]%(ans2*ans3)==0)continue;
            if(a[i]%ans3==0){
                cout<<a[i]<<' ';
                break;
            }
        }
        for(int u=1;u<=pm[ans3];u++){
            for(int i=1;i<=n;i++){
                if(a[i]%(ans2*ans3)==0)continue;
                if(a[i]%(ans2*ans3/plst[ans3][u])==0){
                    cout<<a[i]<<' ';
                    break;
                }
            }
        }
        cout<<'\n';
        return;
    }
    for(int i=1;i<=min(n,25);i++){
        for(int j=i+1;j<=min(n,25);j++){
            if(a[i]%a[j]==0||a[j]%a[i]==0)continue;
            cout<<2<<'\n'<<a[i]<<' '<<a[j]<<'\n';
            return;
        }
    }
    cout<<1<<'\n'<<a[1]<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    for(int i=2;i<=100000;i++){
        if(!isp[i]){
            pri[++totp]=i;
            for(int j=1;j*i<=100000;j++){
                pm[j*i]++;
                plst[j*i][pm[j*i]]=i;
            }
        }
        for(int j=1;j<=totp;j++){
            if(pri[j]*i>100000)break;
            isp[pri[j]*i]=1;
            if(i%pri[j]==0)break;
        }
    }
    for(int i=1;i<=100000;i++){
        stk[pm[i]][++tot[pm[i]]]=i;
        mnv[i]=i;
        for(int j=1;j<=pm[i];j++){
            int u=i;
            while(u%plst[i][j]==0)u/=plst[i][j];
            mnv[i]=min(mnv[i],(i/u));
            plst2[i][j]=i/u;
        }
        for(int j=1;j*i<=100000;j++)ys[j*i].emplace_back(i);
    }
    cin>>T;
    while(T--)sol();
    return 0;
}