如果我们要求一个积性函数 \(f(x)\) 的前缀和，可以用杜教筛在 \(O(n^{\frac{2}{3}})\) 的复杂度求出。
具体地，构造函数 \(g(x)\) 和函数 \(h(x)\) ，使得 $h=f*g $，要求的式子是 \(S(n)=\sum\limits_{i=1}^{n}f(i)\)。
开始推式子。
\[\sum\limits_{i=1}^{n}h(i)=\sum\limits_{i=1}^{n}g(i)\sum\limits_{i=1}^{}\sum\limits_{d|i}^{i}g(d)\times f(\frac{i}{d})\\
\sum\limits_{i=1}^{n}h(i)=\sum\limits_{i=1}^{n}g(i)\sum\limits_{j=1}^{\lfloor\frac{n}{j}\rfloor}f(j)\\
\sum\limits_{i=1}^{n}h(i)=g(1)S(n)+=\sum\limits_{i=1}^{n}g(i)\times S(\lfloor\frac{n}{i}\rfloor)\\
\sum\limits_{i=1}^{n}h(i)=g(1)S(n)+\sum\limits_{i=2}^{n}g(i)\times S(\lfloor\frac{n}{i}\rfloor)\\
g(1)S(n)=\sum\limits_{i=1}^{n}h(i)-\sum\limits_{i=2}^{n}g(i)\times S(\lfloor\frac{n}{i}\rfloor)
\]
如果\(h(x)\)的前缀和好做，后面的式子可以整除分快。
对于莫比乌斯函数，可以构造 \(g(x)\)为\(I\)函数。
那么:\(S(n)= 1- \sum\limits_{i=2}{d}S(\lfloor{\frac{n}{d}}\rfloor)\)。
对于欧拉函数，可以构造为 \(I\).
那么： \(S(n) = \sum\limits_{i=1}^{n}-\sum\limits_{d=2}^{n}S(\lfloor{\frac{n}{d}}\rfloor)\)。
对于$ S(n) = \sum\limits_{i=1}^{n} i\times \phi(i)$，可以构造函数 \(g(x)=\frac{n}{d}\)。
\(\to\)对于某一类积性函数，可以通过观察积性函数的关系来构造函数。