题目链接

传送门

想说的话

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

题解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

写在最后

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