Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj1968: [Ahoi2005]COMMON 约数研究 解题报告

题目链接

传送门

想说的话

有的时候麻烦跟简单
没差在复杂度
就差在想法上面了

题解I

我先说最慢但是最好想的吧
欧拉筛
筛一遍
筛的过程中维护素数 不用我多说
跑了300多ms有点慢(相对于另外两种方法)
相对来说代码长度也长

代码I

题解II

考虑到我们要找约数一定要筛 不好写
我们换个思路
对于一个数n 我们要找到从1-n所有数约数的个数和
那么我们是不是可以找一下从1-n每个数的倍数出现了多少个
每出现一个证明这个数作为了一次其他数的约数
我们统计这个值相对来讲更简单
代码长度巨短 时间也快了好多

代码II

题解III

看了上面的题解 你们一定在想剩下0ms那个做法是何方神圣
其实没有什么特别特别高大上的东西
就是把我们的算法II进行了一步优化
时间复杂度从O(n)变成O(sqrt(n))
这个优化是什么样的呢
其实我是看了zyf学姐的博客才知道这种方法
当时我想了很长时间为什么可以采用这种优化
这个优化的方式是这样的
如果把所有的⌊n/i⌋都列出来形成一个数列,你会发现有一些区间内的数都是一样的,而如果你把所有的⌊n/n/i⌋求出来的话,就得到了一个与上一个序列“相反”的序列(其实求这个序列的目的只是为了方便代码实现)。
然后每一次只需要求一下区间和就可以了,时间复杂度降低
其实这个很难想到
我觉得第二种方法已经是考场的极限了

代码III

写在最后

数论这个东西真的奇妙
有的时候就是出发点不同
看题的想法方向不同
代码长度到时间整个脱胎换骨

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏