题解：P6028 算术
yangzichen1203
·
·
题解
妙妙题。
f(n)
=\prod_{i=1}^k{\frac{p_i^{\alpha_i+1}-1}{p_i^{\alpha_i+1}-p_i^{\alpha_i}}}
=\frac{1}{n}\prod_{i=1}^{k}\dfrac{p_i^{\alpha_i+1}-1}{p_i-1}
=\frac{1}{n}\prod_{i=1}^{k}\sum_{j=0}^{\alpha_i}p_i^j
=\frac{1}{n}\sum_{i|n}i
\sum_{i=1}^{n}f(i)
=\sum_{i=1}^{n}\frac{1}{i}\sum_{j|i}j
=\sum_{i=1}^{n}\sum_{j|i}\frac{1}{j}
=\sum_{j=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{j}\rfloor}\frac{1}{j}
=\sum_{i=1}^{n}\frac{1}{i}\lfloor\frac{n}{i}\rfloor
\boxed{\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\frac{1}{i}\lfloor\frac{n}{i}\rfloor}
显然是整数分块的形式，暴力拆调和级数即可。注意预处理前面一些项的调和级数以提高精度，后面的用渐进公式做即可。
公式（其中 \gamma\approx0.5772156649）：
H_n=\ln{n}+\gamma+O(n^{-1})
时间复杂度：O(\sqrt{n})