描述

深绘里在九份开了一家咖啡店。当然如何调配咖啡成了她每天的头等大事。 我们假设她有 n 种原料，第 i 种原料编号为 i，而调配一杯咖啡则需要选择这里面的若干种来兑在一起。

不过有些原料不能同时调兑在同一杯里。如果两个编号为 i， j 的原料，当且仅当 i 和 j 互质时，它们才能被兑在同一杯里。

现在深绘里想知道，如果她用这 n 种原料来调兑一杯咖啡，那么这杯咖啡所使用的原料编号之和最大能为多少呢？ …

输入

一行，一个正整数 n

输出

一行一个正整数，即最大的编号之和

样例输入

10

样例输出

30

提示

【数据范围和约定】

对于 20% 的数据， 1 ≤ n ≤ 30

对于 50% 的数据， 1 ≤ n ≤ 200

对于 80% 的数据， 1 ≤ n ≤ 800 对于 100% 的数据， 1 ≤ n ≤ 200000

标签

湖南2013省选模拟

---

spfa写错了也很感动。。。

有一个神仙结论：原料最多由两种质因数组成，且一个小于sqrt(n)，一个大于sqrt(n)（本蒟蒻并不会证明）。

知道这个结论之后就可以跑最大费用流了。

代码：

#include
    
     #define N 1000005#define inf 1000000000#define ll long longusing namespace std;int n,pot[N],first[N],d[N],cnt=-1,prime[N],vis[N],in[N],pred[N],tot=0,ans,res;struct edge{
   int c,w,v,next;}e[N<<1];inline void add_edge(int u,int v,int c,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].c=c,e[cnt].next=first[u],first[u]=cnt;}inline void add(int u,int v,int c,int w){add_edge(u,v,c,w),add_edge(v,u,0,-w);}inline void init(){    for(int i=2;i<=n;++i){        if(!vis[i])prime[++tot]=i;        for(int j=1;j<=tot;++j){            if(prime[j]*i>n)break;            vis[prime[j]*i]=1;            if(i%prime[j]==0)break;        }    }}inline void calc(int s,int t){    int pos=t;    while(pos!=s){        e[pred[pos]].c-=1;        e[pred[pos]^1].c+=1;        pos=e[pred[pos]^1].v;    }}inline bool spfa(int s,int t){    queue
     
      q;    memset(d,128,sizeof(d));    ll tmp=d[0];    for(int i=1;i<=t;++i)in[i]=0;    in[s]=1,q.push(s),d[s]=0;    while(!q.empty()){        int x=q.front();        q.pop();        for(int i=first[x];~i;i=e[i].next){            int v=e[i].v;            if(d[v]
      
       n)break;    }    return tmp;}int main(){    memset(first,-1,sizeof(first));    scanf("%d",&n),init();    int pos=0;    ll sum=0;    for(int i=1;i<=tot;++i){        sum+=(ll)solve(prime[i],1);        if(1ll*prime[i]*(1ll*prime[i])>n)add(1,i+1,1,0);        else add(i+1,tot+10,1,0),pos=i;    }    for(int i=pos+1;i<=tot;++i)        for(int j=1;j<=pos;++j){            int tmp=solve(prime[j],prime[i]),ttmp=solve(prime[j],1);            if(tmp>n)continue;            add(i+1,j+1,1,tmp-ttmp-solve(prime[i],1));        }    while(spfa(1,tot+10));    cout<<1ll*(res+sum+1);    return 0;}