题目大意：在 [1,n] 区间内选择一些数，使得这些数两两互质，求这些数的和的最大值

容易发现对于一个最优解，每个质数存在且仅存在于一个数中。(废话。
但是有可能一个数中存在多个质数
下面是两个结论：
1.一个数中最多存在两个不同的质数
2.这两个质数一个 ，一个 >n√
我完全不会证明这两个结论，这两个结论都是官方题解里的
然后就好办了，我们对于 的质数和 >n√ 的质数建立二分图，求最大费用最大流即可
但是这样会T掉，因为图太大了
因此我们有两个剪枝：
1.对于 >n2 的质数，一定单独存在于解集中，不用扔进二分图跑了
2.如果某两个质数组合起来不如分别取最大后加起来，就不加这条边
加了之后基本就能过了……20W的点跑了9s+
这个题是PE的355 听说PE的那群人跑的都是模拟退火？
据说巨快……

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define M 10100 #define S 0 #define T (M-1) #define INF 0x3f3f3f3f using namespace std; int n; long long ans; int prime[M<<2],tot; bool not_prime[200200]; namespace Max_Cost_Max_Flow{ struct abcd{ int to,flow,cost,next; }table[100100]; int head[M],tot=1; void Add(int x,int y,int f,int c) { table[++tot].to=y; table[tot].flow=f; table[tot].cost=c; table[tot].next=head[x]; head[x]=tot; } void Link(int x,int y,int f,int c) { Add(x,y,f,c); Add(y,x,0,-c); } bool Edmonds_Karp() { static int q[65540],cost[M],from[M]; static unsigned short r,h; static bool v[M]; int i; memset(cost,0xef,sizeof cost); cost[S]=0;q[++r]=S; while(r!=h) { int x=q[++h];v[x]=false; for(i=head[x];i;i=table[i].next) if(table[i].flow&&cost[table[i].to]
       
        =x) n/=x,re*=x; return re; } int main() { int i,j; cin>>n; Linear_Shaker(); for(i=1;i<=tot&&prime[i]*2<=n;i++) if((long long)prime[i]*prime[i]<=n) { Max_Cost_Max_Flow::Link(S,i,1,0); Max_Cost_Max_Flow::Link(i,T,1,Get_Max(n,prime[i])); } else { Max_Cost_Max_Flow::Link(i,T,1,0); Max_Cost_Max_Flow::Link(S,i,1,prime[i]); } for(;i<=tot;i++) ans+=prime[i]; for(i=1;i<=tot&&(long long)prime[i]*prime[i]<=n;i++); for(;i<=tot&&prime[i]*2<=n;i++) for(j=1;j<=tot&&(long long)prime[j]*prime[j]<=n;j++) { if(prime[i]*prime[j]>n) break; int temp=Get_Max(n/prime[i],prime[j])*prime[i]; if(temp>Get_Max(n,prime[j])+prime[i]) Max_Cost_Max_Flow::Link(j,i,1,temp); } while( Max_Cost_Max_Flow::Edmonds_Karp() ); cout<