1874 素数和最大

题目描述 Description

    有一天萌萌哒Sevenkplus在跟素数们玩>_<。。。他玩着玩着突然想到一个问题!就是这样的：
    从1到n这n个自然数中，选出一些数使得它们之间两两互质并且它们的和最大。
    当然Sevenkplus几分钟就秒杀了>_<。。。你也来试试吧~~~
    比如说n=10，那么选择{1,5,7,8,9}就行了，答案是30。

输入描述 Input Description

    一行一个整数n

输出描述 Output Description

    一行一个整数表示答案

样例输入 Sample Input

    3

样例输出 Sample Output

    6

数据范围及提示 Data Size & Hint

    【数据范围】

    测试点
    1..2:n<=100
    3..5:n<=1000
    6..10:n<=200000



    【卖萌向】

    素数可是很可爱的哦^_^



    【来源】

    我们都爱GYZ摸你赛 Problem C Hard

好题

一开始眼瞎+脑残，以为肯定是每一个素数都单独选它的最大次幂，全WA

好吧，看题解，果真是网络流+数论

先筛素数，把素数分成两类，一类是小于等于根号n的，这些可以自己乘多次，大于根号n的只能有一次幂

我们考虑这两类凑成一对一对的，如果凑成一对会更优，就连一条权值为增益的边（不过为什么不能小素数凑对呢？）

然后做二分图最大匹配

代码就别看了，因为建图，我的变量名已经乱了

  1 var
  2     flag:array[0..200010]of boolean;
  3     zhi,best:array[0..100000]of longint;
  4     first,next,last,val,cost,vis,db,link:array[0..200010]of longint;
  5     n,tot,jie,num,time:longint;
  6     ans:int64;
  7 
  8 procedure shai;
  9 var
 10     i,j:longint;
 11 begin
 12     for i:=2 to n do
 13       begin
 14         if flag[i]=false then
 15         begin
 16           inc(tot);
 17           zhi[tot]:=i;
 18         end;
 19         for j:=1 to tot do
 20           begin
 21             if i*zhi[j]<=n then flag[i*zhi[j]]:=true
 22             else break;
 23             if i mod zhi[j]=0 then break;
 24           end;
 25       end;
 26 end;
 27 
 28 procedure insert(x,y,z:longint);
 29 begin
 30     inc(num);
 31     last[num]:=y;
 32     next[num]:=first[x];
 33     first[x]:=num;
 34     val[num]:=z;
 35     if db[x]<z then db[x]:=z;
 36 end;
 37 
 38 procedure init;
 39 var
 40     i,j,k,s:longint;
 41 begin
 42     read(n);
 43     shai;
 44     ans:=1;
 45     for i:=1 to tot do
 46       begin
 47         k:=zhi[i];
 48         while k*zhi[i]<=n do
 49           k:=k*zhi[i];
 50         if k>zhi[i] then jie:=i;
 51         best[i]:=k;
 52         ans:=ans+k;
 53       end;
 54     for i:=1 to jie do
 55       for j:=jie+1 to tot do
 56         begin
 57           s:=zhi[j];
 58           while s*zhi[i]<=n do
 59             s:=s*zhi[i];
 60           if s>best[i]+best[j] then insert(i,j,s-best[i]-best[j]);
 61         end;
 62     for i:=1 to jie do
 63       insert(i,tot+i,0);
 64 end;
 65 
 66 function find(x:longint):boolean;
 67 var
 68     i:longint;
 69 begin
 70     vis[x]:=time;
 71     i:=first[x];
 72     while i<>0 do
 73       begin
 74         if (vis[last[i]]<>time)and(val[i]=db[x]+db[last[i]]) then
 75         begin
 76           vis[last[i]]:=time;
 77           if (link[last[i]]=0)or(find(link[last[i]])) then
 78           begin
 79             link[last[i]]:=x;
 80             cost[last[i]]:=val[i];
 81             exit(true);
 82           end;
 83         end;
 84         i:=next[i];
 85       end;
 86     exit(false);
 87 end;
 88 
 89 function km:int64;
 90 var
 91     i,j,k,d:longint;
 92 begin
 93     for i:=1 to jie do
 94       begin
 95         while true do
 96           begin
 97             inc(time);
 98             if find(i) then break;
 99             d:=maxlongint;
100             for k:=1 to jie do
101               if vis[k]=time then
102               begin
103                 j:=first[k];
104                 while j<>0 do
105                   begin
106                     if vis[last[j]]<>time then
107                     if d>db[k]+db[last[j]]-val[j] then d:=db[k]+db[last[j]]-val[j];
108                     j:=next[j];
109                   end;
110               end;
111             if d=maxlongint then break;
112             for j:=1 to jie do
113               if vis[j]=time then dec(db[j],d);
114             for j:=jie+1 to tot do
115               if vis[j]=time then inc(db[j],d);
116           end;
117       end;
118     km:=0;
119     for i:=jie+1 to tot do
120       inc(km,cost[i]);
121 end;
122 
123 begin
124     init;
125     write(km+ans);
126 end.

View Code