bzoj-3308 九月的咖啡店
题目大意：深绘里在九份开了一家咖啡让，如何调配咖啡民了她每天的头等大事我们假设她有N种原料，第i种原料编号为i,调配一杯咖啡则需要在这里若干种兑在一起。不过有些原料不能同时在一杯中，如果两个编号为i,j的原料，当且仅当i与j互质时，才能兑在同一杯中。现在想知道，如果用这N种原料来调同一杯咖啡，使用的原料编号之和最大可为多少。
数据范围：$1\le N \le 2\cdot 10^5$。
想法：
神仙题.....
主要神仙在，两个根本没法证（至少我现在不会2019.6.19）的性质。
1.每个数最多只包含两个质数
2.如果包含两个质数那么一个小于$\sqrt{n}$一个大于$\sqrt{n}$。
这咋证.....
如果考场上猜到了这两个性质，那就容易多了。
我们把所有小于根号$n$与所有大于根号$n$的素数之间建立二分图。
暴力建肯定是不行，发现如果这两个数的答案比原来大，我们再连边。
这样就好了嗷~
最后费用流即可。
代码：
#include <bits/stdc++.h>
#define inf (1<<30)
#define N 1000010
using namespace std;
typedef long long ll;
int S,T,n;
int to[N<<1],nxt[N<<1],val[N<<1],tot=1,cst[N<<1],fr[N],head[N];
int pre[N],dis[N];
bool vis[N];
int prime[N]; bool vis_prime[N];
inline void Add(int x,int y,int z,int c) {to[++tot]=y; fr[tot]=x; val[tot]=z; cst[tot]=c; nxt[tot]=head[x]; head[x]=tot;}
inline void add(int x,int y,int z,int c) {Add(x,y,z,c); Add(y,x,0,-c);}
bool spfa()
{
queue<int>q; while(!q.empty()) q.pop();
for(int i=0;i<=T;i++) dis[i]=inf,vis[i]=false;
memset(pre,0,sizeof pre);
dis[S]=0; vis[S]=true; q.push(S);
while(!q.empty())
{
int x=q.front(); q.pop();
vis[x]=false;
for(int i=head[x];i;i=nxt[i]) if(val[i] && dis[to[i]] > dis[x]+cst[i])
{
pre[to[i]]=i;
dis[to[i]] = dis[x] + cst[i];
if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=true;
}
}
return dis[T] < 0;
}
ll minf()
{
int flow = inf;
for(int i=T;i!=S;i=to[pre[i]^1]) flow=min(flow,val[pre[i]]);
for(int i=T;i!=S;i=to[pre[i]^1]) val[pre[i]]-=flow,val[pre[i]^1]+=flow;
return flow * dis[T];
}
// ll minf()
// {
// ll ans=0;
// int i=pre[T],mdl=inf;
// while(i)
// {
// mdl=min(mdl,val[i]);
// i=pre[fr[i]];
// }
// i=pre[T];
// while(i)
// {
// val[i]-=mdl;
// val[i^1] += mdl;
// ans += (ll)mdl * cst[i];
// i=pre[fr[i]];
// }
// return ans;
// }
int qpow(int x,int y)
{
int ans=1;
while(y)
{
if(y&1) ans=ans*x;
y>>=1;
x=x*x;
}
return ans;
}
int Lmt(int x,int y) {int re; for(re=x;1ll*re*x<=y;re*=x); return re;}
void init_prime(int n)
{
for(int i=2;i<=n;i++)
{
// printf("%d\n",i);
if(!vis_prime[i]) prime[++prime[0]]=i;
for(int j=1;j<=prime[0] && (ll)i*prime[j] <= n;j++)
{
// printf("%d %d %d\n",i,prime[j],prime[j] * i);
vis_prime[i*prime[j]]=true;
// printf("%d %d %d\n",i,prime[j],prime[j]*i);
if(i%prime[j]==0) break;
}
}
}
ll ans=0;
void Build()
{
S=prime[0]+1; T=S+1;
int pos=0;
for(int i=1;i<=prime[0];i++)
{
if(prime[i] >= n/2) {ans += prime[i]; continue;}
if((ll)prime[i] * prime[i] <= n) add(S,i,1,0),ans += Lmt(prime[i],n);
else
{
if(!pos) pos=i;
add(i,T,1,0); ans += prime[i];
}
}
// cout << pos << endl ;
for(int i=1;i<pos;i++)
for(int j=pos;j<=prime[0];j++)
{
if((ll)prime[i] * prime[j] > n) break;
int mdl = Lmt(prime[i],n/prime[j]) * prime[j] - Lmt(prime[i],n) - prime[j];
// cout << mdl << endl ;
if(mdl > 0) add(i,j,1,-mdl);
}
// cout << ans << endl ;
}
ll Calc()
{
while(spfa())
{
ll tmp=minf();
if(tmp<0) ans-=tmp;
}
return ans;
}
int main()
{
// freopen("sum.in","r",stdin);
// freopen("sum.out","w",stdout);
cin >> n ;
// puts("A");
init_prime(n);
Build();
cout << Calc()+1 << endl ;
// fclose(stdin);
// fclose(stdout);
return 0;
}
小结：这种题就要大胆猜结论，如果能小心验证那就证一证，不然的话觉得对就直接拿来用就好了。