杜教筛学习笔记

设现在要求积性函数 $f$ 的前缀和， 设 $\sum \limits_{i=1}^{n} f(i) = S(n)$。

再找一个积性函数 $g$ ，则考虑它们的狄利克雷卷积的前缀和

$$\begin{aligned} \sum\limits_{i=1}^{n}(f*g)(i) &= \sum\limits_{i=1}^{n} \sum \limits _{d|i} f(d)g(\frac{i}{d}) \\\ &= \sum \limits _{d=1}^{n} g(d)\sum\limits _{i=1}^{\lfloor \frac{n}{d}\rfloor } f(i) \\\ &= \sum \limits _{d=1}^{n} g(d) S(\lfloor \frac{n}{d} \rfloor) \end{aligned}$$

其中得到第一行是根据狄利克雷卷积的定义。

得到第二行则是先枚举 $d$ 提出 $g$ 。

得到第三行则是把 $\sum\limits _{i=1}^{\lfloor \frac{n}{d}\rfloor } f(i) $ 替换为 $S(\lfloor \frac{n}{d} \rfloor) $

接着考虑 $g(1)S(n)$ 等于什么。

可以发现，他就等于

$$\sum \limits _{i=1}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor) - \sum \limits _{i=2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)$$

（可以理解成从1开始的前缀和减去从2开始的前缀和就是第一项）

前面这个式子 $\sum \limits _{i=1}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)$

根据刚才的推导，他就等于 $\sum\limits_{i=1}^{n}(f*g)(i)$

所以得到杜教筛的核心式子：

$$g(1)S(n)=\sum\limits_{i=1}^{n}(f*g)(i) - \sum \limits _{i=2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)$$

得到这个式子之后有什么用呢？

现在如果可以找到一个合适的积性函数 $g$ ，使得可以快速算出 $\sum\limits_{i=1}^{n}(f*g)(i)$ 和 $g$ 的前缀和，便可以用数论分块递归地求解。

代码按照理解大概可以写成这样（默认 ll 为 long long）
（可以理解成一个伪代码。。就是一个思路的框架）

ll GetSum(int n) { // 算 f 前缀和的函数
  ll ans = f_g_sum(n); // 算 f * g 的前缀和
  // 以下这个 for 循环是数论分块
  for(ll l = 2, r; l <= n; l = r + 1) { // 注意从 2 开始
    r = (n / (n / l)); 
    ans -= (g_sum(r) - g_sum(l - 1)) * GetSum(n / l);
    // g_sum 是 g 的前缀和
    // 递归 GetSum 求解
  } return ans; 
}

这个代码的复杂度是 $O(n^{\frac{3}{4}})$，证明如下：

设求出 $S(n)$ 的复杂度是 $T(n)$ ，要求出 $S(n)$ 需要求出 $\sqrt n$ 个 $S (\lfloor \frac{n}{i} \rfloor)$ 的值，结合数论分块的复杂度 $O(\sqrt n)$ 可得：

$$T(n) = \sum\limits_{i=1}^{\sqrt n} O(\sqrt i) + O(\sqrt {\frac{n}{i}})=O(n^{\frac{3}{4}})$$

还可以进一步优化杜教筛，即先线性筛出前 $m$ 个答案，之后再用杜教筛。这个优化之后的复杂度是：

$$T(n) = \sum\limits_{i=1}^{\lfloor \frac{n}{m} \rfloor} \sqrt \frac{n}{i} = O({\frac{n}{\sqrt m}})$$

当 $m = n ^ {\frac{2}{3}}$ 时，$T(n) = O(n^{\frac{2}{3}})$

可以使用哈希表来存下已经求过的答案，也可以不用。

考虑到上面的求和过程中出现的都是 $\lfloor \frac{n}{i} \rfloor $ 。开一个大小为两倍 $\sqrt n$ 的数组 $dp$ 记录答案。如果现在需要求出 GetSum(x) ，若 $x \leq \sqrt n$ ，返回 dp[x] ，否则返回 dp[sqrt n + n / i] 即可。这样可以省去哈希表的复杂度。