杜教筛小记

对于一个函数$F(n)$，要在较低时间内求前缀和$S_F(n)=\sum_{i=1}^nF(i)$

假设我们能找到一个函数$G(n)$使得$G(n),S_{F \oplus G}(n)$能在较短时间内算出

其中$\oplus$表示狄利克雷卷积，$(F\oplus G)(n)=\sum_{d|n}F(d)G(\frac{n} {d})$

那么就有

$\displaystyle S_{F\oplus G}(n)=\sum_1^n G(i)S_F(\lfloor\frac{n} {i}\rfloor)$

$\displaystyle G(1)F(n)=S_{F\oplus G}(n)-\sum_2^nG(i)S_F(\lfloor\frac{n} {i}\rfloor)$

这个$\lfloor\frac{n} {i}\rfloor$的个数是$O(\sqrt n)$的，数论分段求解

由于每次从$2$开始枚举，每次子问题大小至少减半

(然而并没有分析复杂度)

当$n$较小时可以直接预处理出来前$m$个($m$为以常数)

不要存状态$\text{dp}$，直接递归求解用$\text{map}$维护记录即可

ps:实际上对于一个固定的$n$，每次计算$x$的答案时，可以根据当前的$\lfloor \cfrac{n} {x}\rfloor$为状态编号，去掉了$\text{map}$

当$m=n^{\frac{2} {3} }$时，复杂度最优为$O(n^{\frac{2} {3} })$

---

例子1：

对于$F(n)=\mu(n)$，求$S_\mu(n)$

由于$\sum_{d|n}\mu(d)=[n=1]$

那么就知道可以构造$G(n)=1$

则$(F\oplus G)(n)=[n=1]$

$S_{F\oplus G}(n)=1$

$\displaystyle S_F(n)=S_{F\oplus G}(n)-\sum_2^nS_F(\lfloor\frac{n} {i}\rfloor)$

---

例子1.5

$F(n)=\mu(n)n^k$，求$S_F(n)$

令$G(n)=n^k$

则$\displaystyle (F\oplus G)(n)=\sum _{d|n} \mu(d)d^k (\frac{n} {d})^k=n^k\sum_{d|n} \mu(d)=[n=1]\cdot n^k$

$\displaystyle S_F(n)=1-\sum_{i=2}^n i^kS_F(\lfloor \frac{n} {i}\rfloor )$

只要通过一些手段得到$i^k$前缀和即可

---

例子2：

对于任何$F(n)=\sum_{d|n}\mu(d)H(\frac{n} {d})$，其中$H(n)$前缀和可以求

类似上面的，构造$G(n)=1$

$(F\oplus G)(n)=\sum_{d|n}H(d)\sum_{k|\frac{n} {d} }\mu(k)=H(n)$

$\displaystyle S_F(n)=S_{H}(n)-\sum_2^nS_F(\lfloor\frac{n} {i}\rfloor)$

$$\$$

例子3+3.5:

$F(n)=\varphi(n)\cdot n^k$，求$S_F(n)$

性质：$\displaystyle \sum_{d|n}\varphi(d)=n$

原理简要证明：满足$\gcd(i,n)=\frac{n} {d}$的$i$共有$\varphi(d)$个，则累和就是枚举了所有$\gcd(i,n)$进行统计

所以构造$G(n)=n^{k}$

$\displaystyle (F\oplus G)(n)=\sum_{d|n}F(d)G(\frac{n} {d})=\sum_{d|n} \varphi(d)d^k(\frac{n} {d})^{k}=\sum_{d|n} \varphi(d) n^{k}=n^{k+1}$

同样的只需要求出

$\displaystyle S_{F\oplus G}(n)=\sum_{i=1}^n i^{k+1}$

$\displaystyle S_G(n)=\sum_{i=1}^n i^k$