\(\displaystyle f(x) = \sum_{i=1}^n x \bmod i\)
对于一个i,枚举k
对于[xk, x(k+1) ),中的数,贡献的形式都为a[i]-i*k
直接差分维护即可
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e6+5;
const ll mo=998244353;
ll n,c[N];
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld",&n);
fo(i,1,n) {
fo(j,1,n/i){
c[i*j]+=i*j;
c[min(i*(j+1),(ll)N-1)]-=i*j;
}
}
ll ans=0;
fo(i,1,n) {
ans+=c[i];
printf("%lld ",n*i-ans);
}
return 0;
}
标签:取模,P3708,int,ll,fo,ans,include,koishi,define
From: https://www.cnblogs.com/ganking/p/17785155.html