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]];
    }
}