杜教筛

什么是杜教筛？

用来在非线性时间内求积性函数前缀和的方法

已知\(f(i)\)为积性函数，设
\[S(n)=\sum\limits_{i=1}^{n}f(i)\]
我们若要低于线性的复杂度求出\(S(n)\),该如何做？

设
\[h=f*g\]
可以得出
\[\sum\limits_{i=1}^{n}h(i)=\sum\limits_{i=1}^{n}(f*g)(i)\]
\[=\sum\limits_{i=1}^{n}\sum\limits_{d|i}f(d)g(\frac{i}{d})\]
\[=\sum\limits_{d=1}^{n}g(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\]
\[=\sum\limits_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)\]
我们发现，其中含有\(S(n)\)的项\(g(1)S(n)\)等于
\[\sum\limits_{i=1}^{n}h(i)-\sum\limits_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)\]
如果我们找到一个可以快速求前缀和的\(h\)和\(g\)函数，那么我们就可以递归求解\(S\)的值了

如果我们预先处理出小于等于\(n^{\frac{2}{3}}\)的\(S\)的值，总复杂度就是\(O(n^{\frac{2}{3}})\) (我也不会证

杜教筛模板

求：
\[ans1=\sum\limits_{i=1}^{n}\phi(i)\]
\[ans2=\sum\limits_{i=1}^{n}\mu(i)\]
我们需要一些前置姿势：
\[\mu*1=?\]
以及
\[\phi*1=n\]

\(emmmmmm\)，然后好像套式子就行了，到此结束。

杜教筛

原文：https://www.cnblogs.com/knife-rose/p/12018532.html