Mas's Blog
Masellum 的生活日志
[AHOI2005] 约数研究

题目

题目链接

题目描述

科学家们在Samuel星球上的探险得到了丰富的能源储备,这使得空间站中大型计算机“Samuel II”的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩,小联被允许用“Samuel II”进行数学研究。

小联最近在研究和约数有关的问题,他统计每个正数 NN 的约数的个数,并以 f(N)f(N) 来表示。例如 1212 的约数有 11223344661212。因此 f(12)=6f(12)=6。下表给出了一些 f(N)f(N) 的取值:

img
img

f(n)f(n) 表示 nn 的约数个数,现在给出 nn,要求求出 f(1)f(1)f(n)f(n) 的总和。

输入输出格式

输入格式:

输入一行,一个整数 nn

输出格式:

输出一个整数,表示总和。

说明

对于 20%20\% 的数据,N5000N \le 5000

对于 100%100\%N1000000N \le 1000000

题解

对于一个 nnf(n)=i=1nni. f(n) = \sum_{i = 1}^{n} \lfloor \frac{n}{i} \rfloor. 打表可以发现 ni\lfloor\frac{n}{i}\rfloor 的值呈现块状分布,对于某一个区间内的 iini\lfloor\frac{n}{i}\rfloor 的值相同,这个区间的右端点为 nn/i\frac{n}{n/i}

这样的区间最多有 2n2\sqrt{n} 个。于是我们进行整除分块,总复杂度 O(nn)O(n\sqrt{n})

代码

Finita la comedia.