设数论函数 $f$。希望求解 $S(n)=\sum\limits_{i=1}^n f(i)$。

引理

假设存在数论函数 $g$，则根据上述定义：

$\sum\limits_{i=1}(f*g)(i)=\sum\limits_{i=1}g(i)S(\lfloor \dfrac ni\rfloor)$

证明

$\sum\limits_{i=1}(f*g)(i)=\sum\limits_{i=1}{n}\sum\limits_{j=1}^{\lfloor\frac ni\rfloor}f(i)g(i)$。

这一步我们把 $f*g$ 变换一下枚举顺序就可以了。接下来把 $g(i)$ 提出来，里面的 $f(i)$ 换掉就是，

$\sum\limits_{i=1}g(i)S(\lfloor \dfrac ni \rfloor)$。

引理的应用

根据引理 $g(1)S(n)=\sum\limits_{i=1}(f*g)(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\dfrac{n}{i}\rfloor)$。

如果 $\sum\limits_{i=1}(f*g)(i)$ 知道了，可以用整除分块求出 $\sum\limits_{i=2}^ng(i)S(\lfloor\dfrac ni\rfloor)$，那么 $S(n)=\dfrac{\sum\limits_{i=1}(f*g)(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\dfrac{n}{i}\rfloor)}{g(1)}$ 就知道了。

现在就需要巧妙构造 $g(i)$ 以使得 $\sum\limits_{i=1}(f*g)(i)$ 可以快速计算。

例 1

求 $S(n)=\sum\limits_{i=1}^n\mu(i)$。

注意到 $\epsilon=\mu*1$。原因是 $\mu(n)$ 的隐性递归定义：$\sum\limits_{d|n}\mu(d)=\epsilon(n)$。

所以 $1\times S(n)=1-\sum\limits_{i=2}^nS(\lfloor\dfrac ni\rfloor)$。

实现时需要注意较大的 $n$ 会使得数组存不下，所以我们筛出当 $n$ 较小时的 $S(n)$，较大时再计算。

具体可以配合线性筛先求 $\mathcal O(n^{\frac23})$，再求剩余的部分，这个时候总复杂度恰好是 $\mathcal O(n^\frac23)$ 的，取最小。