杜教筛是一种快速求出积性函数前缀和的算法。

Part 1 前置知识

• 积型函数
  • 若对于任意满足 $x \perp y$ 的 $x,y$，都有 $f(x)f(y)=f(xy)$，则 $f(x)$ 是积性函数。
• 狄利克雷卷积
  • 定义函数 $f,g$ 的狄利克雷卷积 $(f \times g)(x) = \sum_{d \mid x}f(d)g(\frac{x}{d})$

Part 2 杜教筛

杜教筛可以在 $O(n^{\frac{2}{3}})$ 的复杂度内求出一个积性函数的前缀和。现在设我们要求出 $s(x) = \sum_{i = 1}^x f(i)$。先构造一个积性函数 $g$。我们现在来化简 $(f * g)$ 的前缀和。

$\sum_{i=1}^x (f * g)(i)$

$= \sum_{i=1}^x \sum_{d \mid i}f(d)g(\frac{i}{d})$

$= \sum_{d=1}^x g(d) \sum_{i=1}^{\lfloor \frac{x}{d} \rfloor}f(i)$

$= \sum_{d=1}^x g(d)s(\lfloor \frac{x}{d} \rfloor)$

$= g(1)s(x) + \sum_{d=2}^x g(d)s(\lfloor \frac{x}{d} \rfloor)$

解释一下每一步吧。第一步，我们将狄利克雷卷积展开了。第二步，我们从枚举 $i$ 和 $i$ 的约数变成了枚举 $d$ 和 $d$ 的倍数。第三步没什么可说的。第四步，我们将 $d$ 的枚举范围从 $1$ 到 $n$ 变成了从 $2$ 到 $n$。同时，将第一项单独拿出来。现在，我们得到了杜教筛的核心式子，$\sum_{i=1}^x (f * g)(i) = g(1)s(x) + \sum_{d=2}^x g(d)s(\lfloor \frac{x}{d} \rfloor)$。移项后变成

$g(1)s(x) = \sum_{d=2}^x g(d)s(\lfloor \frac{x}{d} \rfloor) - \sum_{i=1}^x (f * g)(i)$

只要我们能快速求出 $\sum_{i=1}^x (f * g)(i),\sum_{i=1}^x g(i)$ 就可以用数论分块求出右边的式子了。

核心代码：

ll get_sum(ll n) {
    if (n < Pig)
        return sum[n];
    ll res = g(1);
    for (ll l = 2, r; l <= n; l = r + 1) {
        r = (n / (n / l));
        res -= ((f*g)(r)-(f*g)(l-1)) * get_sum(n / l);
    }
    return res;
}

其中 $Pig$ 表示一个阈值，提前筛出小于 $Pig$ 的前缀和。

Part 3 复杂度证明

我们预处理了小于 $Pig$ 的所有前缀和。所以复杂度为 $O(Pig + \sum_{i=1}^{\lfloor \frac{n}{Pig} \rfloor}\sqrt{\frac{n}{i}})=O(Pig+nPig^{-\frac{1}{2}})$ 当 $Pig = n^{\frac{2}{3}}$ 时，原式取到最小值 $n^{\frac{2}{3}}$。

Part 4 本题做法

回到题目，题目要求 $\sum_{i=1}^n \varphi(i),\sum_{i=1}^n \mu(i)$。对于 $\varphi(i)$，$(\varphi * I) = id$。其中 $I(x) = 1$，$id(x) = x$。两个函数的前缀和都可以快速求出。对于 $\mu(i)$，$(\mu * I) = \epsilon$。其中 $\epsilon(x) = [x=1]$，两个函数的前缀和都可以快速求出。于是题目就做完了。