Dirichlet前缀和

快速计算模某些于倍数、约数相关的函数

引入

考试中，遇到这样一个问题：已知 $A(x)$ ，且 $B(d) = \sum_{i \mid d} A(i)$ ，求 $B$

显然暴力是调和级数 $O(n H(n))$ ，大部分情况下够用，但如果出题人把数据开到 $10^7$ ，就挂了；而狄利克雷前缀和提供了一个 $O(n \log \log n)$ 的做法

考虑因数分解， $i = \prod p_k^{c_k}, j = \prod p_k^{d_k} (c_k, d_k 可以为 0)$ ，那么 $A(i)$ 对 $B(j)$ 有贡献，当且仅当 $\forall k, c_k \le d_k$ ，这其实就是一个高维前缀和（类比 SOS dp ）

前缀和

先线性筛质数，然后初始让 $b = a$

for (int i = 1; i <= ct && pri[i] <= n; ++i)
    for (int j = 1; LL(j) * pri[i] <= n; ++j) b[j * pri[i]] += b[j];

后缀和

$B(d) = \sum_{d \mid i} A(i)$ ，类似的，反过来转移

for (int i = 1; i <= ct && pri[i] <= n; ++i)
    for (int j = n / pri[i]; j; --j) b[j] += b[j * pri[i]];

逆推前缀和

还是前缀和的式子 $B(d) = \sum_{i \mid d} A(i)$ ，现在已知 $B$ 要求 $A$

初始让 $a = b$

for (int i = ct; i; ++i)
    for (int j = n / pri[i]; j; --j) a[j * pri[i]] -= a[j];

逆推后缀和

for (int i = ct; i; ++i)
     for (int j = 1; LL(j) * pri[i] <= n; ++j) a[j] -= a[j * pri[i]];