（抄袭 Alex_Wei）
一、知识点
假设我们先现在希望求出函数 \(f\) 在 \(n\) 处的前缀和 \(s(n)=\sum\limits_{i=1}^nf(i)\)，我们构造另一个数论函数 \(g\)，设 \(h=f*g\)，则
\[\begin{aligned}&\sum\limits_{i=1}^nh(i)\\=&\sum\limits_{ij\leq n}f(i)g(j)\\=&\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\\=&\sum\limits_{d=1}^ng(d)s\left(\left\lfloor\dfrac{n}{d}\right\rfloor\right) \end{aligned} \]若 \(g,h\) 的前缀和可快速求出，我们就得到了 \(s(n)\) 关于其所有整除值处取值的递推式，即
\[g(1)s(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)s\left(\left\lfloor\dfrac{n}{d}\right\rfloor\right) \]一般 \(f,g\) 均为积性函数，因此 \(g(1)=1\)，公式又写为
\[s(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)s\left(\left\lfloor\dfrac{n}{d}\right\rfloor\right) \]一般预处理 \(f\) 及其前缀和到 \(n^{\frac{2}{3}}\) 处，复杂度优化为 \(\mathcal{O}(n^{\frac{2}{3}})\)。
二、例题
P4213 【模板】杜教筛
题意：求 \(\sum \varphi(i)\) 和 \(\sum \mu(i)\)，\(n\leq 2^{31}\)。
对于 \(f=\varphi\)，构造 \(g=1\)，\(f*g=id\)。
对于 \(f=\mu\)，构造 \(g=1\)，\(f*g=\epsilon\)。
P3768 简单的数学题
发现自己欧拉反演和莫比乌斯反演都学的依托……
对 \(\gcd(i,j)\) 作欧拉反演得 \(\gcd(i,j)=\sum\limits_{d\mid \gcd(i,j)}{\varphi(d)}\)。
所以原式
\[=\sum\limits_{d=1}^n{\varphi(d)\times d^2}\sum\limits_{i=1}^{\lfloor n/d \rfloor}\sum\limits_{j=1}^{\lfloor n/d\rfloor}{ij} \]后面那坨可以直接计算，对它整除分块，只需快速求出前面那坨的前缀和。
设 \(f=\varphi\times id^2\)，构造 \(g=id^2\)，那 \(f*g=id^3\)，可以使用杜教筛。时间复杂度大约 \(\mathcal{O}(n^{\frac{2}{3}})\)。
标签：lfloor,right,limits,sum,rfloor,杜教,left From： https://www.cnblogs.com/xishanmeigao/p/17995737