【模板】杜教筛

杜教筛用来解决积性函数求前缀和的问题。
复杂度为\(O(n^\frac{2}{3})\)
适用情况：
已知函数\(f\)，求\(\sum f\)，
存在\(f*g=F\)，且\(g,\sum g,F,\sum F\)容易求出。

常用公式：
\(\mu*I=[n=1]\)
\(\varphi*I=id\)

以求\(\sum \mu\)为例。

构造出所求函数\(\mu\)

设\(t=i/d\)

设\(M(\lfloor \frac{n}{t} \rfloor) = \sum\limits_{d = 1}^{\lfloor \frac{n}{t} \rfloor} \mu(d)\)$

对于\(i<10^7\)，可以预处理出\(M(i)\)的值，存到数组里。
比较大的数可以通过数论分块递推求解。

qvq

【模板】杜教筛

原文：https://www.cnblogs.com/mogeko/p/13335990.html