数论 整除分块 P3708题解

Prean · 2020-09-30 18:46:49 · 题解

题面很直白，就不说了罢qaq

首先很明显， \sum_{i=1}^n x \bmod i = nx - \sum_{i=1}^n i\lfloor \frac x i \rfloor

这道题要是直接求的话复杂度是不对的，而他让我们求 f(0) ~ f(n-1) 所有的值，所以考虑从 f(i) 得到 f(i+1)

对于后面的 \sum 分类讨论：

1. i|n $ 很明显多了一个 $ i
2. 反正没有多

所以，后面的 \sum 相当于是 \sum_{d|x}d ，也就是 \sigma(x)

所以就可以 O(n) 线性筛或 O(nlogn) 的暴力计算 \sigma 来解决此题啦！

由于自己太菜，不会线性筛 \sigma ，所以就只能写暴力啦

code：

#include<cstdio>
const int M=1e6+5;
int n;
long long ans,sigma[M];
signed main(){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        for(j=i;j<=n;j+=i){
            sigma[j]+=i;
        }
    }
    for(i=1;i<=n;++i){
        printf("%lld ",ans+=n-sigma[i]);
    }
}