一些前置知识

假设我们现在要求一个积性函数 $\mathbf{f}$ 的前缀和 $\mathbf{S}(n)$。

假设我们有一个奇妙的数论函数 $\mathbf{g}$，那么有
$$
\begin{aligned}
\mathbf{g}(1)\mathbf{S}(n)&=\sum_{i=1}^n\mathbf{g}(i)\mathbf{S}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)-\sum_{i=2}^n\mathbf{g}(i)\mathbf{S}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\
&=\sum_{i=1}^n(\mathbf{g}*\mathbf{f})(i)-\sum_{i=2}^n\mathbf{g}(i)\mathbf{S}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
\end{aligned}
$$
第二步是因为
$$
\begin{aligned}
\sum_{i=1}^n(\mathbf{g}*\mathbf{f})(i)&=\sum_{i=1}^n\sum_{d|i}\mathbf{g}(d)\mathbf{f}\left(\frac{i}{d}\right)\\
&=\sum_{d=1}^n\mathbf{g}(d)\sum_{d|i}^n\mathbf{f}\left(\frac{i}{d}\right)\\
&=\sum_{d=1}^n\mathbf{g}(d)\sum_{i=1}^{n/d}\mathbf{f}(i)\\
&=\sum_{d=1}^n\mathbf{g}(d)\mathbf{S}\left(\left\lfloor\frac{n}{d}\right\rfloor\right)
\end{aligned}
$$
那么如果 $\mathbf{g}$ 和 $\mathbf{g}*\mathbf{f}$ 的前缀和可以快速计算，那么就可以通过数论分块求 $\mathbf{S}$ 了。

复杂度 $\mathcal{O}(\int_{0}^{\sqrt{n}} \sqrt{\frac{n}{x}} \mathrm{d}x) = \mathcal{O}(n^{\frac{3}{4}})$，如果预处理前 $n^{\frac{2}{3}}$ 个元素复杂度变为 $\mathcal{O}(n^{\frac{2}{3}} + \int_{0}^{n^{\!\frac{1}{3}}} \sqrt{\frac{n}{x}} \mathrm{d}x) = \mathcal{O}(n^{\frac{2}{3}})$。

事实上 $\mathbf{g}$ 和 $\mathbf{g}*\mathbf{f}$ 的前缀和可以再套一层杜教筛，复杂度不变（这里存疑）。

下面举一个例子：求 $\mu$ 的前缀和。

我们知道，$\mathbf{I}*\mathbf{\mu}=\mathbf{\epsilon}$，所以可以得到
$$
\mathbf{S}(n)=[n\geq 1]-\sum_{i=2}^n\mathbf{S}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
$$

unordered_map<int,int> Mmu;
int Smu(int n) {
    if (n<L) return mu[n];
    if (Mmu.count(n)) return Mmu[n];
    int res=n>=1;
    for (int l=2,r;l<=n;l=r+1) {
        r=n/(n/l);
        res-=(r-l+1)*Smu(n/l);
    }
    return Mmu[n]=res;
}
最后修改：2021 年 04 月 07 日 03 : 12 PM
© 允许规范转载