杜教筛小记

对于一个积性函数\(F(n)\)，要在较低时间内求前缀和\(S_F(n)=\sum_{i=1}^nF(i)\)

假设我们能找到一个函数\(G(n)\)使得\(G(n),S_{F \oplus G}(n)\)能在较短时间内算出

其中\((F\oplus G)(n)=\sum_{d|n}F(d)G(\frac{n}{d})\)

那么就有

\(S_{F\oplus G}(n)=\sum_1^n G(i)F(\lfloor\frac{n}{i}\rfloor)\)

\(G(1)F(n)=S_{F\oplus G}(n)-\sum_2^nG(i)F(\lfloor\frac{n}{i}\rfloor)\)

这个\(\lfloor\frac{n}{i}\rfloor\)的个数是\(O(\sqrt n)\)的

当\(n\)较小时可以直接预处理出来前\(m\)个

不要存状态\(\text{dp}\)，直接递归求解用\(\text{map}\)维护记录即可

当\(m=n^{\frac{2}{3}}\)时，复杂度最优为\(O(n^{\frac{2}{3}})\)

---

求\(S_\mu(n)\)

由于\(\sum_{d|n}\mu(d)=[n=1]\)

那么就知道可以构造\(G(n)=1\)

则\((F\oplus G)(n)=[n=1]\)

\(S_{F\oplus G}(n)=1\)

\(F(n)=S_{F\oplus G}(n)-\sum_2^nF(\lfloor\frac{n}{i}\rfloor)\)