自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:16:40，当前版本为作者最后更新于2020-01-31 04:19:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

其实这个题有一个非常 bullshit 的 $\Theta(1)$ 解法，仅供参考。

---

首先题目中给出的式子很迷惑，随便推一下发现就是 $\sigma_1(n)/n$。
然后就能得出一个除法分块式子

$$\sum_{i=1}^n\sum_{j=1}^{\lfloor n/i \rfloor} \frac 1j $$

考虑每个 $1/j$ 出现了多少次，式子化为

$$\sum_{i=1}^n\frac{\lfloor n/i \rfloor}{i}$$

接下来就是最玄学的地方，直接把向下取整扔掉，式子变成

$$n\sum_{i=1}^n \frac{1}{i^2}$$

（当然这样是有误差的，最后调整一下即可）
对于身经百战见得多的同学，容易发现在 $n$ 很大的时候就可以近似为 $\zeta(2)$，即 $\pi^2/6$。

然后就能得到这么一份看起来非常扯淡，但就是能过的代码

#include<cstdio>
#include<iostream>
#include<cmath>
#define ll long long
#define reg register
#define pi 3.141592653589793
using namespace std;

int main(){
    ll n;
    long double ans = 0;
    scanf("%lld",&n);
    if(n<=1e6) for(reg int i=1;i<=n;++i) ans += 1.0/i * (n/i);
    else ans = pi*pi/6*n - 10;
    printf("%.9Lf",ans);
    return 0;	
}

ps：对于上面说到的这个式子

$$\sum_{i=1}^\infty i^{-2} = \frac{\pi^2}{6}$$

有很多有趣的证明方法，可以自己搞一搞