杜教筛初步

之前学杜教筛的时候感觉没有学的很明白，现在重新学习一遍。

杜教筛简介

何为杜教筛？
说直白一点就是在低于线性的时间内求出某个积性函数的前缀和。

假设现在我们有一个积性函数$f(i)$，设$S(i)=\sum\limits_{j=1}^{i} f(i)$。

我们要求$S(n)$，假设我们找到了另一个任意数论函数$g(i)$ 。

那么可以很轻松地得到如下的推导：

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

然后我们做进一步推导：

$$\begin {align} &\begin {split} \sum _{i=1} ^{n} (f*g) (i) &= \sum _{d=1} ^{n} g(d) S( \lfloor \frac {n} {d} \rfloor) \\ &= g(1)S(n) + \sum _{d=2} ^{n} g(d) S( \lfloor \frac {n} {d} \rfloor ) \\ \end {split} \\ &\therefore g(1)S(n) = \sum _{i=1} ^{n} (f*g) (i) -\sum _{d=2} ^{n} g(d) S( \lfloor \frac {n} {d} \rfloor ) \end {align}$$

也就是说，如果我们能够找到一个积性函数$g$，并且我们能够快速计算$(f*g)$的前缀和，$g$的前缀和，那么我们的问题就可以用我们最后得到的那个式子进行计算，具体来说就是可以用数论分块，然后最后一项进行递归处理。

例题

BZOJ 3944

Link

题意

求$\sum\limits{i=1}^{n} \varphi(i)$和$\sum\limits{i=1}^{n} \mu(i)$。

$n\leqslant 2^{31}-1$

题解

我们首先考虑$\sum\limits_{i=1}^{n} \varphi(i)$。

按照刚才那套理论，我们需要找到一个函数$g$，并且$(g*\varphi)$和$g$的前缀和均能够容易求出。

我们不难想到，$\varphi *I=id$，并且$id$和$1$的函数均可以很容易地求出。

所以不妨令$g$函数就是恒等函数$I$。

那么我们就有：

$$\begin {align} S(n) &= \sum _{i=1} ^{n} i - \sum_{i=2} ^{n} S( \lfloor \frac {n} {i} \rfloor) \end {align}$$

然后就可以前半部分用公式，后半部分数论分块+递归。

我们再来考虑$\sum\limits_{i=1}^{n} \mu(i)$。

按照刚才那套理论，我们需要找到一个函数$g$，并且$(g*\mu)$和$g$的前缀和均能够容易求出。

我们不难想到$\mu *1=\varepsilon$。

那么我们不妨令$g$为恒等函数$I$。

于是我们带入得到：

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

直接数论分块+递归即可。

洛谷P3768 简单的数学题

Link

题意

求$\sum\limits{i=1} ^{n}\sum\limits\limits {j=1} ^{n} ij*gcd(i,j)$

$n \leqslant 10^{10}$

题解

我们首先对原式进行反演。

$$\begin {align} &\begin {split} Ans &= \sum _{i=1} ^{n} \sum _{j=1} ^{n} ij*gcd(i,j) \\ &= \sum _{i=1} ^{n} \sum _{j=1} ^{n} ij \sum _{d|i,d|j} \varphi(d) \\ &= \sum _{d=1} ^{n} \varphi(d)\sum _{i|d} ^{n} \sum _{j|d} ^{n} ij \\ &= \sum _{d=1} ^{n} \varphi(d) d^2 \sum_{i=1} ^{\lfloor \frac {n} {d} \rfloor} \sum _{j=1} ^{ \lfloor \frac {n} {d} \rfloor} ij\\ &= \sum _{d=1} ^{n} \varphi(d) d^2 (\sum_{i=1} ^{\lfloor \frac {n} {d} \rfloor} i)^2 \\ &= \sum _{d=1} ^{n} \varphi(d) d^2 \sum_{i=1} ^{\lfloor \frac {n} {d} \rfloor} i ^3 \end {split} \\ \end {align}$$

现在的问题就是快速求出$\varphi(d)d^2$的前缀和。

我们设$f(i)=\varphi(i)*i^2$，$S(i)=\sum\limits_{j=1}^{i} f(j)$。

现在我们要找到函数$g$，使得我们能够快速计算$(f*g)$的前缀和，$g$的前缀和。

也就是说，我们需要能够快速求以下这个式子：

$$\begin {align} &\begin {split} Ans &= \sum _{i=1} ^{n} \sum _{d|i} f(d)*g(\frac{i}{d}) \\ &= \sum _{i=1} ^{n} \sum _{d|i} \varphi(d)d^2*g(\frac{i}{d}) \end{split} \\ &\text{我们不妨令}g(i)=i^2 \\ &\begin {split} Ans &=\sum _{i=1} ^{n} \sum _{d|i} \varphi(d) i^2 \\ &=\sum _{i=1} ^{n}i^3 \end {split} \end{align}$$

所以我们只需要使$g(i)=i^2$，然后继续使用刚才的刚才的方法就可以完成此题。