題目描述 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

?

轉載于:https://www.cnblogs.com/Randolph87/p/3599938.html

總結

以上是生活随笔為你收集整理的1874 素数和最大 - Wikioi的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。