Dirichlet 前缀和

标签（空格分隔）：数论

\[f[n] = \sum_{d|n}^Ng[d], \text{已知 $g$，求 $f$}

\]

我们先考虑一种 \(\text{dp}\)。

设 \(f[i][n]\) 为当前考虑的数是 \(n\), 考虑了前 \(i\) 种质数, 严格来说是 ：

\[f[i][n] = \sum_{d |n, \frac{n}{d}只包含前i种质数}g(d)

则有一个比较漂亮的转移：

\[f[i + 1][n] = f[i][n] + f[i + 1][\dfrac{n}{p_{i + 1}}]

转移的意义是这样的，我们考虑 \(f[i + 1][n]\) 的来源。

1. \(\frac{n}{d}\) 不包含第 \(i + 1\) 个质数的，即 \(f[i][n]\) 。
2. \(\frac{n}{d}\) 包含第 \(i + 1\) 个质数的，此时要求 \(p_{i + 1} | \frac{n}{d}\)，贡献是\(f[i + 1][\frac{n}{p_{i + 1}}]\)

考虑滚掉第一维。

for(int i = 1 ; i <= cnt; ++ i ) {
    for(int j = 1; j * pri[i] <= n; -- j) {
        f[j * pri[i]] += f[j];
    }
}
           

同理，考虑后缀和，倒推前缀和，倒推后缀和。

\[f[d] = \sum_{d|n}^Ng[n],\text{已知 $g$，求 $f$}

for(int i = 1 ; i <= cnt; ++ i ) {
    for(int j = n / pri[i]; j >= 1; -- j) {
        f[j] += f[j * pri[i]];
    }
}
           

\[f[n] = \sum_{d|n}^Ng[d],\text{已知 $f$，求 $g$}

for(int i = cnt; i >= 1; i --) {
    for(int j = n / pri[i]; j >= 1; -- j) {
        f[j * pri[i]] -= f[j];
    }
}
           

\[f[d] = \sum_{d|n}^Ng[n],\text{已知 $f$，求 $g$}

for(int i = cnt; i >= 1; i --) {
    for(int j = 1; j <= n / pri[i]; j ++) {
        f[j] -= f[j * pri[i]];
    }
}