注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

除数函数的渐近上界?  

2013-05-19 23:35:01|  分类: 知识点 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
除数函数的渐进上界? - vfleaking - vfleaking的博客
 

大约一年半以前做了一道题目:BZOJ 1053 反素数 http://www.lydsy.com/JudgeOnline/problem.php?id=1053
其实那东西的官方名称是Highly composite number。一般简称HCN。中文名貌似是高合成数。
OEIS上列出了前几个高合成数:http://oeis.org/A002182
还有个前1000个高合成数的表:http://oeis.org/A002182/b002182.txt

然后最近看到了一道神题:BZOJ 3085: 反质数加强版SAPGAP http://www.lydsy.com/JudgeOnline/problem.php?id=3085
orz @shuxk
顿时吓哭了。

但是我不很满意的地方在于,求高合成数仍然是靠搜索 + 剪枝来解决的 >_<....
好像也就只能这么着了?因为这个问题取对数之后能变成类似背包问题的形式……
而背包问题众所周知是NPC的……= =……

而另一个故事是:
某年某月某日,某vfk做SCOI某题在DP时对于每个i枚举约数,AC。
某年某月某日,某vfk做Balkan某题枚举了约数,AC。
某年某月某日,某vfk做POI某题枚举了约数,光荣TLE。
某年某月某日,某vfk做某JZP某KIL枚举了约数,光荣TLE。

除数函数的渐进上界? - vfleaking - vfleaking的博客

我们来尝试估计一下除数函数tau(n)。

除数函数的渐进上界? - vfleaking - vfleaking的博客
如果是sqrt(n)那我某些题是怎么A的……如果是ln n那我某些题是怎么TLE的……

感觉没有一个乖巧的软件能帮我画出如此畸形的函数的图像,于是自己用程序画了个:
除数函数的渐进上界? - vfleaking - vfleaking的博客
横轴被压缩到了1/20。x的范围是[1, 19850]。
红色的那一大团就是tau(x)。
红色中间有个极为不明显的黄线,那个是ln x。注意哦……真的有根黄线哦……
绿色的那个是max{tau(y), 1 <= y <= x}。中间断掉的那几个地方就是高合成数导致的。
蓝色的那个是sqrt(x)。
可见蓝线和绿线在小数据时拟合得很好,但是大数据就不行了。
而黄线真是不能多说。

我想了很久也不知道如果估计tau(n)的渐近上界。
APIO 2013时陈许旻也表示:“这个问题困扰了我多年。”

但是最近居然在维基上发现了上界的估计!
不能直视:

如果玩一下这个式子貌似就可以得到这个?
除数函数的渐进上界? - vfleaking - vfleaking的博客
可是玩一下图像……
除数函数的渐进上界? - vfleaking - vfleaking的博客
…………………………除数函数的渐进上界? - vfleaking - vfleaking的博客
有丝毫准确度么…………………

紧接着在wiki的talk里面发现了个公式:
除数函数的渐进上界? - vfleaking - vfleaking的博客
好像很科学?
也就是说:
除数函数的渐进上界? - vfleaking - vfleaking的博客
 
于是果断又画了个图,感觉非常不错。
除数函数的渐进上界? - vfleaking - vfleaking的博客
所以大概就是这样了?
(1.066是咩啊!!!)
(求证明啊!!!)
(求论文啊!!!)

其实复杂度什么的都是浮云?咱还是关心实际数字吧 >_<
10^9以内最大的Highly composite number是735134400,约数个数为1344个。(1000)
int32以内最大的Highly composite number是2095133040,约数个数为1600个。(1000)
10^18以内最大的Highly composite number是897612484786617600,约数个数为103680个。(10^5)
int64以内最大的Highly composite number是9200527969062830400,约数个数为161280个。(10^5)

反正约数什么的真是坑爹……>_<……除数函数的渐进上界? - vfleaking - vfleaking的博客
  评论这张
 
阅读(3343)| 评论(9)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017