【学习笔记】杜教筛

标签：lfloor frac limits sum 笔记 杜教 学习 rfloor times

如果我们要求一个积性函数 \(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\)对于某一类积性函数，可以通过观察积性函数的关系来构造函数。

标签：lfloor,frac,limits,sum,笔记,杜教,学习,rfloor,times
From： https://www.cnblogs.com/flywatre/p/17356525.html