Luogu P1403 [AHOI2005]约数研究

题目

实际上一开始看到题目我是打算写筛法的，后来发先是个除法分块秒切题目

显然

$$
\sum_{i = 1}^{n} f(i) = \sum_{i = 1}^{n} \lfloor \frac{i}{n} \rfloor
$$

除法分块即可

代码

#include <cstdio>

int n;
long long ans;

int main(){
    scanf("%d", &n);
    for(int left = 1, rig; left <= n; left = rig + 1){
        rig  = n / (n / left);
        ans += 1LL * (n / left) * (rig - left + 1);
    }
    printf("%lld", ans);
}