链接:Link 耗时:2.232s
分析
粗看题目,不过就是要求这样一个式子:$\sum_{i=1}^n{[\frac{n}{i}]}$的值。但注意到:题目给的数据范围极大,有$2^{31}-1$之多,若遍历计算,则时间复杂度为$O(n)$,将严重超时,不可取。
而事实上,通过尝试我们可以发现:$\sum_{i=1}^{n}{[\frac{n}{i}]}=2*\sum_{i=1}^{\sqrt n}{[\frac{n}{i}]}-{[\sqrt n]}^2$,这是一个重要的结论。因为这条式子一旦成立,时间复杂度即可从$O(n)$降为$O(\sqrt n)$,这是一个极为可观的改善。下面我们来证明一下这个结论:
事实上,
$$ \begin{aligned} \sum_{i=[{\sqrt n}]+1}^{n}{[\frac{n}{i}]} &=1\times(n-[\frac{n}{2}])+2\times([\frac{n}{2}]-[\frac{n}{3}])+\ldots+[\sqrt{n}]\times([\frac{n}{\sqrt{n}}]-{[\frac{n}{\sqrt n}+1]}) \\ &=n+[\frac{n}{2}]+[\frac{n}{3}]+\ldots+[\frac{n}{\sqrt n}]-[\sqrt n]\times[\frac{n}{[\sqrt n]+1}] \\ &=\sum_{i=1}^{[\sqrt n]}{[\frac{n}{i}]}-{[\sqrt n]}^2 \end{aligned}$$从而,命题得证。
Code
var |
OOPS!
A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.