杜教筛
处理数论函数的前缀和问题，可以在低于线性的复杂度里求出 \(S(n)=\sum_{i=1}^{n} f(i)\)。
对于任意一个数论函数 \(g\)，必须满足 ：
\[\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n} \sum_{d \mid i} g(d)*d(\frac{i}{d}) \]\[=\sum_{d=1}^{n} g(d) \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} f(j)=\sum_{d=1}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor) \]那么可以得到：
\[g(1)S(n)=\sum_{i=1}^{n} g(i)S(\lfloor \frac{n}{i} \rfloor)-\sum_{i=2}^{n} g(i)S(\lfloor \frac{n}{i} \rfloor) \]\[=\sum_{i=1}^{n} (f*g)(i)-\sum_{i=2}^{n} g(i)S(\lfloor \frac{n}{i} \rfloor) \]时间复杂度最小为 \(n^{\frac{2}{3}}\)。
一般情况下，可以设出方便求前缀的 \(g\) 和 \(f*g\)，然后进行递归求解。
例如根据 \(I(n)=1\)，\(id(n)=n\)，\(\epsilon(n)=[n=1]\)
单位元 \(\epsilon\) 满足 \(f * \epsilon= f\)
根据狄利克雷卷积得到几个性质：
-
\(\mu * I =\epsilon\)
-
\(\varphi * I = id\)
-
\(\mu * id= \varphi\)
让 \(g\) 等于以上这些等等。
标签：lfloor,frac,epsilon,sum,rfloor,杜教,id From： https://www.cnblogs.com/jinjiaqioi/p/17978192