【bzoj3308】九月的咖啡店

2015年6月2日3,0936

Description

深绘里在九份开了一家咖啡让,如何调配咖啡民了她每天的头等大事
我们假设她有N种原料,第i种原料编号为i,调配一杯咖啡则需要在这
里若干种兑在一起。不过有些原料不能同时在一杯中,如果两个编号
为i,j的原料,当且仅当i与j互质时,才能兑在同一杯中。
现在想知道,如果用这N种原料来调同一杯咖啡,使用的原料编号之和
最大可为多少。

Input

一个数字N

Output

如题

Sample Input

10

Sample Output

30

HINT

1<=N<=200000

题解

直观感受是,所有质因数分别单独存在于一个数中

但是还要考虑到,俩个质因数一起存在于一个数中可以更优

如3,5,n=20

9+5<3*5

听说,至多俩个质因数存在于一个数中0.0

且一个大于根号n,一个小于根号n

于是就能费用流最大费用匹配了(不断增广至费用<0)

一个优化是,先假设所有质因数单独存在,把这部分收益加入答案

若a,b能配对

a,b连边 权值\(V_{ab}-V_a-V_b\)

这样费用流就跑的飞起了


 

 

  • 233332015年6月5日 下午2:06 回复

    求证明“至多俩个质因数存在于一个数中,且一个大于根号n,一个小于根号n”
    PE上并没有人给出证明

    #1  
  • zzq2015年6月12日 下午5:14 回复

    神牛试试加这个优化看看如何http://wenzhang.baidu.com/page/view?key=49163da31247db6f-1428110857 看能不能跑到100ms之内

    #2  
  • zzq2015年6月12日 下午6:15 回复

    怎么又看不到了。。。。。
    对于大于sqrt(n)的质数:
    对于在n/2+1到n中很明显都要取
    对于在n/3+1到n/2中,这些数只有可能与2组合起来成为解之一,设x1<x2,那么x1*2+x2<x2*2+x1,所以在此区间内,只有一个数是有可能与其他质数组合成为解的(最大的那个),于是其他的数可以提前加到解里面(因为其与其他质数组合的解必定更差)
    。。。。。。
    对于在n/p+1到n/p中,设x1<x2,那么x1*p+x2<x2*p+x1,以此类推。
    那么图的规模就只有sqrt(n),就可以过了。

    #3  
  • zjkmxy2015年7月19日 上午12:41 回复

    51nod最新的比赛的最后一题貌似也是这个问题。标程给的是状压,但是实际上至多两个质因数存在于一个数中……不知道为什么。

    #4  
  • 启动2016年9月19日 上午12:14 回复

    黄学长你好,我认为“至多俩个质因数存在于一个数中,且一个大于根号n,一个小于根号n”不能成立。
    考察n=624时 对于5和11 显然5<11<sqrt(n) 但是5^3+11^2=125+121<605=5*11*11
    需要证明的应该是“当两个小于sqrt(n)的质数放在一起时,肯定不比让他们分别和大质数匹配更优”,而无法证明“两个小于sqrt(n)的质数分开放,比放在一起时更优”的错误结论
    (ps.其实上述结论来自数学迷

    #5