Dirichlet学习笔记
Dirichlet前缀和
狄利克雷前缀和是求解形如
\[b_k=\sum\limits_{i|k}a_i \]的式子
首先我们可以想到枚举 \(i\) ，再枚举 \(i\) 的倍数 \(j\) $$b_j=b_j+a_i$$
此时的时间复杂度为 \(n/1+n/2+n/3+...+n/1\) 。由于调和级数，时间复杂度为 \(O(nlogn)\)
进一步分析式子，我们可以发现一个较大的 \(b_k\) 可以分解为几个 \(b_{k的因子}\) 相加，例如 \(b_8=a_1+a_2+a_3+a_4+a_8\) ，\(b_4=a_1+a_2+a_3+a_4\) , 所以 \(b_8=b_4+a_8\)
而 \(8=2*4\) ，我们可以考虑枚举质数因子，和质数的系数来求解。
例如
for(int i=1;i<=tot;i++){
for(int j=1;p[i]*j<=n;j++){
a[p[i]*j] += a[j];
}
}
\(p[i]\) 为枚举的质数，\(j\)为质数的系数，我们把 \(b\) 数组放到 \(a\) 数组中，节省空间更方便。
Dirichlet后缀和
后缀和和前缀和基本相同，只改变了赋值方向。
\[b_k=\sum\limits_{k|i}a_i \]for(int i=1;i<=tot;i++){
for(int j=n/p[i];j>=1;j--){
a[j] += a[p[i]*j];
}
}
倒Dirichlet前缀和
\[a_k=\sum\limits_{i|k}b_i \]给出 \(a_k\) 求 \(b_i\)。我们需要从大到小枚举
for(int i=tot;i>=1;i--){
for(int j=n/p[i];j>=1;j--){
a[p[i]*j] -= a[j];
}
}
倒Dirichlet后缀和
\[a_k=\sum\limits_{k|i}b_i \]for(int i=tot;i>=1;i--){
for(int j=1;p[i]*j<=n;j++){
a[j] -= a[p[i]*j];
}
}