题解 P6028 【算术】

· · 题解

其实这个题有一个非常 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}

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