LUOGU P3708 koishi的数学题

解题思路

发现当x+1时，有的x%i会+1，有的会变成0，而变成0的说明是x的约数，就可以nlogn预处理出每个约数的贡献，然后每次用n-约数。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

const int MAXN = 1e6+5;

typedef long long LL;

LL f[MAXN],sum[MAXN];

int n;

int main(){

    scanf("%d",&n);

    for(register int i=1;i<=n;i++)

        for(register int j=i;j<=n;j+=i) sum[j]+=i;

    for(register int i=1;i<=n;i++){

        f[i]=f[i-1]+n-sum[i];

        printf("%lld ",f[i]);

    }

    return 0;

}

巴特西

LUOGU P3708 koishi的数学题

解题思路

代码

最新文章

热门文章