学习笔记——狄利克雷 前/后缀和、前/后差分
定义
定义因数求和为
\[f(n)=\sum_{d|n}g(d)
\]
这个式子可以反演得到
\[g(n)=\sum_{d|n}\mu(d)f(\frac nd)
\]
这个式子可以理解为求因数差分，是因数求和的逆运算
再定义倍数求和为
\[f(n)=\sum_{n|d}g(d)
\]
易可得
\[g(n)=\sum_{n|d}\mu(\frac dn)f(d)
\]
这个式子可以理解成求倍数差分，是倍数求和的逆运算
代码实现
狄利克雷 前缀和(因数求和)
for(int i=1;i<=num_p;++i)
for(int j=1;j<=lim/pr[i];++j)
w[j*pr[i]]+=w[j];
狄利克雷 后缀和(倍数求和)
for(int i=1;i<=num_p;++i)
for(int j=lim/pr[i];j>=1;--j)
w[j]+=w[j*pr[i]];
狄利克雷 前缀差分(因数差分)
for(int i=1;i<=num_p;++i)
for(int j=lim/pr[i];j>=1;--j)
w[j*pr[i]]-=w[j];
狄利克雷 后缀差分(倍数差分)
for(int i=1;i<=num_p;++i)
for(int j=1;j<=lim/pr[i]++j)
w[j]-=w[j*pr[i]];