前言

好久没更了，刚考完省选有点颓。

前置知识

• 积性函数（乘性函数）
• 数论分块
• 线性筛（欧拉筛）
• 狄利克雷卷积（Dirichlet convolution）
• 莫比乌斯反演（Möbius inversion）

概述

杜教筛用于在 $\Theta\left(n^\frac32\right)$ 的时间内求解某些函数的前缀和。

公式

杜教筛的核心公式如下：
设 $f\left(i\right)$ 为目标函数（即我们要求前缀和的函数）
设 $g\left(i\right)$ 为我们构造的一个函数。

其中 $\left(f * g\right)\left(i\right)$ 为 $f\left(i\right)$ 与 $g\left(i\right)$ 的狄利克雷卷积。

如果能找到一个合适的积性函数 $g\left(x\right)$，能快速求出 $\sum\limits_{i = 1}^n\left(f * g\right)\left(i\right)$ 和 $\sum\limits_{i = l}^rg\left(i\right)$，那么就能使用数论分块递归求解了。

$f\left(i\right)$ 不一定要是积性函数。

证明

复杂度

假设算 $\sum\limits_{i = 1}^x\left(f * g\right)\left(i\right)$ 的复杂度为 $H\left(x\right)$，算 $\sum\limits_{i = 1}^xg\left(i\right)$ 的复杂度为 $G\left(x\right)$：

通常情况下 $H\left(N\right)$ 和 $G\left(N\right)$ 都为 $\Theta\left(1\right)$。

后面的那个可以忽略，于是

众所周知的杜教筛是 $\mathcal O\left(n^\frac23\right)$ 的，原因是可以先筛出前 $m$ 个答案。复杂度变为 $\Theta\left(m\right) + \mathcal O\left(\frac n{\sqrt m}\right)$，取 $m = \Theta \left(n^\frac23\right)$ 即可。

常见函数

再看例子前，可以先看看有哪些常作为 $g\left(x\right)$ 的函数。

• $\epsilon$ 元函数。满足 $f * \epsilon = f$。$\epsilon\left(x\right) = \left[x = 1\right]$
• $\varphi$ 欧拉函数
• $I$ 恒等函数。$I\left(x\right) = 1$
• $id$ 自身函数。$id\left(x\right) = x$
• $\mu$ 莫比乌斯函数

下面 $\left(f * g\right)\left(i\right)$ 为 $f\left(i\right)$ 与 $g\left(i\right)$ 的狄利克雷卷积。

• $\mu * I = \epsilon$
• $\varphi * I = id$
• $\mu * id = \varphi$

例子

$\varphi$ 函数前缀和

由于 $\varphi * I = id$，所以取 $g = I$，那么 $f * g = id$

auto apiadu_sieve_phi = [&](auto& $, tp n) -> tp {
  if (n <= m || ps_phi.count(n)) return ps_phi[n];
  tp ret = n * (n + 1) / 2;
  for (tp l = 2, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ret -= (r - l + 1) * $($, n / l);
  }
  return ps_phi[n] = ret;
};

$\mu$ 函数前缀和

由于 $\mu * I = \epsilon$，所以取 $g = I$，那么 $f * g = \epsilon$

auto apiadu_sieve_mu = [&](auto& $, tp n) -> tp {
  if (n <= m || ps_mu.count(n)) return ps_mu[n];
  tp ret = 1;
  for (tp l = 2, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ret -= (r - l + 1) * $($, n / l);
  }
  return ps_mu[n] = ret;
};

$f\left(i\right) = i \times\varphi\left(i\right)$ 函数前缀和

这是一个经典例子。尽管 $f\left(i\right)$ 不再是积性函数，但我们任然可以杜教筛。

取 $g = id$，$\left(f * g\right)\left(n\right) = \sum\limits_{d \mid n} \left(\varphi\left(d\right) \cdot d\right) \cdot \frac nd = n^2$

于是我们还是可以在常数时间内计算 $\left(f * g\right)\left(i\right)$。

卡常小技巧

参考

https://www.luogu.com.cn/article/tojxbb76
https://oi-wiki.org/math/number-theory/du/
https://www.luogu.com/article/hjw4837h