D. Recover it!(模拟,数学)

传送啊大哥申请付款回答

\(先把b数组排序,然后从最大的数看起\)

\(一、如果是质数,那么这个数不可能是a数组的,否则必然会生成一个更大的质数。\)

\(因此,找到生成它的那个数,加入答案\)

\(二、如果是和数，那么这个数一定是a数组的,否则比如有一个更大的和数生成它\)

\(因此，把他加入答案\)

\(这样做每次我们都可以把2个数辨别是否是a数组的数，标记起来\)

\(下次循环到这些数,直接跳过,答案是唯一确定的\)

#include <bits/stdc++.h>
using namespace std;
const int inf=2750131;
const int maxn=4e5+10;
int n,top,cnt;
int a[maxn],prime[maxn],ans[maxn];
int vis[inf+10],ok[inf+10],num[inf+10];
void make_prime()
{
    vis[0]=vis[1]=1;
    for(int i=2;i<=inf;i++)
    {
        if(!vis[i]) prime[++top]=i,num[i]=top;
        for(int j=1;j<=top&&i*prime[j]<=inf;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)   break;
        }
    }
}
int ji(int s)
{
    for(int i=2;i<=sqrt(s);i++)
    if(s%i==0)  return s/i;
}
int main()
{
    make_prime();
    cin>>n;
    for(int i=1;i<=2*n;i++)  cin>>a[i],ok[a[i]]++;
    sort(a+1,a+1+2*n);
    for(int i=2*n;i>=1;i--)
    {
        int s=a[i];
        if(ok[s]==0)    continue;//次数用完
        if(vis[s])//和数,生成别人
            ans[++cnt]=s,ok[ji(s)]--;
        else//质数,被生成 
            ans[++cnt]=num[s],ok[num[s]]--;
        ok[s]--;
        if(cnt==n)  break;
    }
    for(int i=1;i<=cnt;i++)  cout<<ans[i]<<" ";
}