题解：P12551 [UOI 2025] Simple Task

· · 题解

序列其实是假的，就是集合。接下来称最少的和为质数的子序列数为答案。

题意等价于一次操作可以删掉两个数 x,y 加入 x+y，求恰好操作 n-k 次使得集合中质数尽可能少的方案数。称这个操作为合并。

跟着子任务分析。子任务三和正解关系不大，略。下面默认后面的子任务已经判掉了前面的子任务。

子任务一 k=1

全部加起来判和是否为质数即可。

子任务六 2k\ge n+1

你发现每次合并至多减少两个质数，所以答案的下界是 n-2(n-k)=2k-n 和 0 取 \max。当然在这个子任务下界直接就是 2k-n。

你发现我们每次合并要么取两个 2 要么取两个奇质数就可以做到每次质数个数 -2 了。由于 2k\ge n+1 我们可以一直这样合并，所以可以取到下界。

子任务二 n\le 4

判掉子任务一、六，只需要考虑 n=4,k=2。枚举两个分一组的 3 种情况，取答案最小的划分方式即可。

由于 4 个元素中一定存在两个奇偶性相同，把这两个合并剩下两个合并答案至多为 1。而一组 3 个一组 1 个答案至少为 1，所以不需要考虑一组三个一组一个。

子任务四 2|n,a_i>2

下面认为 1<k\le\lfloor\dfrac n 2\rfloor,n\ge 5。由于 n 是偶数可以加强成 n\ge 6。

由于现在全部都是奇数，可以直接先把奇数两两合并，没有奇数了随意合并，答案可以取到 0。

子任务七 2|n

现在多了 2 怎么办？

我们对 2 个数的奇偶性分类。

若 2 有偶数个，由于 2|n，因此奇质数也有偶数个。把奇质数两两合并，2 两两合并，剩下的随意合并可以让答案取到 0。

若 2 有奇数个，我们尝试找到一个奇质数 x，使得 x+2 为合数。

如果我们找到了这样的 x，则合并 2,x，剩下的奇质数两两合并，2 两两合并。此时只有一个元素是奇合数，其他都是偶数。因为 k>1，最后至少可以剩下两个元素。把偶数随意合并，答案可以取到下界 0。

如果我们找不到这样的 x，那么我们继续分类。

若 k=\dfrac n 2，你把一个 2 和随便一个奇质数合并，剩下的和上面一样做，得到答案为 1。不难发现答案无法等于 0。

否则，至少可以合并 \dfrac{n+2}2 次。我们先进行 \dfrac{n+2}2 次合并，有如下四种情况：

现在我们手上只会有 1 个奇合数和 n-1 个偶数。多出来的合并次数拿来随意合并偶数即可，答案为 0。

子任务五 2\nmid n,a_i>2

首先 1<k\le \dfrac{n-1}2,n\ge 5。

直接在前 5 个数中找到和为合数的三个数，剩下的数两两合并，多出来的合并次数同子任务七。答案为 0。

子任务八 2\nmid n

仿照子任务七进行分类讨论。

若 2 的个数为奇数，则奇质数个数为偶数。先丢掉一个 2，剩下的奇质数两两合并，2 两两合并，再将丢掉的 2 和合并后的随意一个元素合并。多出来的合并次数同上。答案为 0。

若 2 的个数为偶数，则奇质数个数为奇数。我们尝试找到一个奇质数的三元组，使得这三个奇质数之和为合数。

如果能找到，那么把这三个合并，剩下同理。多余的合并次数同上。答案为 0。

否则奇质数最多 3 个，那么 2 至少 2 个。还有以下两种情况：

综上，我们只要实现子任务一、二、六、七、八即可。输入的 a 已经给你排好序，所以时间复杂度 O(\sum n)，根据实现可能还会带一个筛质数的 O(V) 或 O(V\log\log V)（线性筛或埃氏筛） 以及判断质数的 O(\sqrt V\sum n) 或 O(T\log V)（暴力判或 Miller-Rabin），可能还需要并查集之类的维护带个 \log n 或 \alpha(n)。

代码

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=3e5+1;
int n,k,ans;
bitset<MAXN>isp;
vector<int>seq[MAXN];
namespace Sub1{
inline void main(){
    ll sum=0;seq[1].resize(n);ans=1; 
    F(i,1,n){int a;cin>>a;sum+=a;seq[1][i-1]=a;}
    for(ll i=2;i*i<=sum;++i) if(sum%i==0) return ans=0,void();
}
}
namespace Sub6{
int c2;
vector<int>odd;
inline void main(){
    c2=0;vector<int>().swap(odd);ans=2*k-n;
    F(i,1,n){int a;cin>>a;if(a==2) ++c2;else odd.push_back(a);}
    F(i,1,n-k){
        if(c2>=2) seq[i].push_back(2),seq[i].push_back(2),c2-=2;
        else seq[i].push_back(odd.back()),odd.pop_back(),seq[i].push_back(odd.back()),odd.pop_back(); 
    }
    F(i,n-k+1,k){
        if(c2) seq[i].push_back(2),--c2;
        else seq[i].push_back(odd.back()),odd.pop_back();
    }
}
}
int a[MAXN],dsu[MAXN],id[MAXN];
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
inline void merge(int cnt,queue<int>&q){
    for(int i=cnt,x,y;i;--i){
        x=q.front();q.pop();y=q.front();q.pop();
        x=find(x),y=find(y);
        dsu[x]=y;q.push(y);
    }
    memset(id,0,sizeof(int)*(n+1));
    int qwq=0;
    F(i,1,n) if(dsu[i]==i) id[i]=++qwq;
    F(i,1,n) seq[id[find(i)]].push_back(a[i]);
}
namespace Sub2{
inline void main(){
    ll sum=0;ans=2;
    F(i,1,n) cin>>a[i],sum+=a[i];
    F(i,2,4){
        if(!isp[a[1]+a[i]]&&isp[sum-a[1]-a[i]]<ans){
            ans=isp[sum-a[1]-a[i]];seq[1].clear(),seq[2].clear();
            seq[1]={a[1],a[i]};
            F(j,2,4) if(j!=i) seq[2].push_back(a[j]); 
        }
        if(!isp[sum-a[1]-a[i]]&&isp[a[1]+a[i]]<ans){
            ans=isp[a[1]+a[i]];seq[1].clear(),seq[2].clear();
            seq[1]={a[1],a[i]};
            F(j,2,4) if(j!=i) seq[2].push_back(a[j]); 
        }
    }
}
}
namespace Sub7{
int c2;
inline void main(){
    c2=0;iota(dsu+1,dsu+n+1,1);ans=0;
    F(i,1,n) cin>>a[i],c2+=(a[i]==2);
    if(c2&1){
        int x=-1;
        F(i,1,n) if((a[i]&1)&&!isp[a[i]+2]){x=i,dsu[i]=c2;break;}
        if(x!=-1){
            queue<int>q;
            F(i,1,c2-1) q.push(i);
            F(i,c2+1,n) if(x!=i) q.push(i);
            return merge(n-k-1,q);
        }
        if(k==n/2){
            queue<int>q;ans=1;
            F(i,1,n) q.push(i);
            return merge(n-k,q);
        }
        if(c2>=3&&a[c2+1]==3){
            dsu[c2]=dsu[c2-1]=dsu[c2-2]=c2+1;
            queue<int>q;
            F(i,1,c2-3) q.push(i);
            F(i,c2+2,n) q.push(i);
            return merge(n-k-3,q);
        }
        if(c2>=5){
            dsu[c2]=dsu[c2-1]=c2+1;
            dsu[c2-3]=dsu[c2-4]=c2-2;
            queue<int>q;
            F(i,1,c2-5) q.push(i);
            F(i,c2+2,n) q.push(i);
            q.push(c2-2);
            return merge(n-k-4,q);
        }
        if(c2==3){
            dsu[c2-1]=dsu[c2-2]=c2;
            dsu[c2+1]=dsu[c2+2]=c2+3;
            queue<int>q;
            F(i,c2+4,n) q.push(i);
            q.push(c2);
            return merge(n-k-4,q);
        }
        if(c2==1){
            int x=0,y=0,z=0;
            F(i,2,6) F(j,i+1,6) F(t,j+1,6) if(!isp[a[i]+a[j]+a[t]]){x=i,y=j,z=t;break;}
            dsu[x]=dsu[y]=z;
            F(i,2,6) if(i!=x&&i!=y&&i!=z) dsu[i]=1;
            queue<int>q;
            F(i,7,n) q.push(i);
            q.push(1);
            return merge(n-k-4,q);
        }
        return;
    }
    queue<int>q;
    F(i,1,n) q.push(i);
    merge(n-k,q);
}
}
namespace Sub8{
int c2;
inline void main(){
    c2=0;iota(dsu+1,dsu+n+1,1);ans=0;
    F(i,1,n) cin>>a[i],c2+=(a[i]==2);
    if(c2&1){
        queue<int>q;dsu[1]=3;
        for(int i=2;i<=n;i+=2) dsu[i]=i+1,q.push(i+1);
        return merge((n-1)/2-k,q);
    }
    int x=-1,y,z,lim=min(c2+5,n);
    F(i,c2+1,lim) F(j,i+1,lim) F(t,j+1,lim) if(!isp[a[i]+a[j]+a[t]]){x=i,y=j,z=t;break;}
    if(x!=-1){
        dsu[x]=dsu[y]=z;
        queue<int>q;
        F(i,1,n) if(i!=x&&i!=y&&i!=z) q.push(i);
        return merge(n-k-2,q);
    }
    F(i,c2+1,n) if(a[i]!=3){x=i;break;}
    queue<int>q;
    if(x==-1){
        if(k==(n-1)/2){
            F(i,1,n) q.push(i);ans=1;
            return merge(n-k,q); 
        }
        dsu[c2]=dsu[c2-1]=dsu[c2-2]=c2+1;
        dsu[c2-4]=dsu[c2-5]=c2-3;
        F(i,1,c2-6) q.push(i);
        q.push(c2-3);
        return merge(n-k-5,q);
    }
    if(a[x]%3==1){
        dsu[1]=x;
        F(i,3,n) if(i!=x) q.push(i);
        q.push(2);
        merge(n-k-1,q);
    }else{
        dsu[1]=dsu[2]=x;
        F(i,3,n) if(i!=x) q.push(i);
        merge(n-k-2,q);
    }
}
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int T;
    isp[1]=1;
    for(int i=2;i*i<MAXN;++i) if(!isp[i]) for(int j=i*i;j<MAXN;j+=i) isp[j]=1;
    isp.flip();
    for(cin>>T;T;--T){
        F(i,1,k) vector<int>().swap(seq[i]);
        cin>>n>>k;
        if(k==1) Sub1::main();
        else if(2*k>=n+1) Sub6::main();
        else if(n<=4) Sub2::main();
        else if(n&1) Sub8::main();
        else Sub7::main();
        cout<<ans<<"\n";
        F(i,1,k){
            cout<<seq[i].size()<<" ";
            for(int j:seq[i]) cout<<j<<" ";
            cout<<"\n";
        }
    }
    return 0;
}