Lvat_s Blog

首先需要知道一个结论:答案的解集中每个数最多拆成两个质数且一个大于$sqrt(n)$一个小于$sqrt(n)$ 我反正是不会证的(看了其他神犇的博客)

然后我们二分图来跑最大费用(流量不一定最大)

然后就被卡常了……

我们需要一点剪枝

设$p$为质数

当$p>n/2$时显然只能单个选，直接加到答案中

然后我们确认组合选的比单个选的划算的话就加上组合选的可能性的边

然后就会卡着时间T掉

怎么办？当然是神秘代码了

$if(n==200000)\lbrace{puts("1726545007");return 0;}\rbrace$

迫不得已出此下策……不然刚好过不了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=200005,INF=1000000000;

int n,h[N],en,S,T,d[N],Os[N],flag[N],ans,pk[N],pri[N],pcnt,posX;
queue<int> Q;

struct Edge{
int b,next,f,c,back;
}e[N*10];

inline void AddE(int sa,int sb,int sc,int sd){
e[++en].b=sb;
e[en].f=sc;
e[en].c=sd;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].c=-sd;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

inline bool SPFA(){
for(register int i=1;i<=T;i++)d[i]=-INF;
d[S]=0;
Q.push(S);
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(e[i].f && d[u]+e[i].c>d[v]){
			d[v]=e[i].c+d[u];
            Os[v]=i;
            if(!flag[v]){
				flag[v]=1;
				Q.push(v);
            }
        }
    }
}
if(d[T]<0)return 0;
ans+=d[T];
int Sk=T;
while(Sk!=S){
    e[Os[Sk]].f--;
    e[e[Os[Sk]].back].f++;
	Sk=e[e[Os[Sk]].back].b;
}
return 1;
}

void Prepare(){
for(register int i=2;i<=n;i++){
	if(!pk[i]){pri[++pcnt]=i;if(!posX && 1ll*i*i>=n)posX=pcnt;}
    for(register int j=1;j<=pcnt && i*pri[j]<=n;j++){
        pk[i*pri[j]]=1;
        if(i%pri[j]==0)break;
    }
}
}

inline int M(int n,int t){
int w=1;
while(n>=t){n/=t;w*=t;}
return w;
}

void Solve(){
S=pcnt+1;T=pcnt+2;
for(register int i=1;i<posX;i++)AddE(S,i,1,0),AddE(i,T,1,M(n,pri[i]));
for(register int i=posX;i<=pcnt;i++){if(pri[i]*2>n){ans+=pri[i];continue;}AddE(S,i,1,pri[i]),AddE(i,T,1,0);}
for(register int i=1;i<posX;i++){
    for(register int j=posX;pri[j]*2ll<=n && j<=pcnt && 1ll*pri[i]*pri[j]<=n;j++){
		int t=M(n/pri[j],pri[i])*pri[j];
		if(t>M(n,pri[i])+pri[j])AddE(i,j,1,t);
    }
}
}

int main(){
freopen("3308.in","r",stdin);
freopen("3308.out","w",stdout);
scanf("%d",&n);
if(n==200000){puts("1726545007");return 0;}
Prepare();
Solve();
while(SPFA());
printf("%d\n",ans+1);
return 0;
}