杜教篩入門

前置知識

迪利克雷卷積（*）：

先介紹三個重要的函數：

• 元函數$?(n)=[n==1]$

  原函數可以看成是迪利克雷卷積里的單位元，即$(??f)(n)=f(n)$，

  證明：$(??f)(n)={\sum }_{d\mid n}?(d)f(\frac{n}{d})=?(1)f(n)=f(n)$

• 恒等函數$I(n)=1$，通俗來講就是其值恒為1

• 單位函數$id(n)=n$

卷積的定義：$(f?g)(n)={\sum }_{d\mid n}f(d)g(\frac{n}{d})$

并且這個式子是滿足：交換律，結合律，分配律的。

與莫比烏斯函數有關的卷積：

${\sum }_{d\mid n}\mu (d)=[n==1]$

寫成卷積也就是$(I?\mu )(n)=?(n)=[n==1]$。

與歐拉函數有關的卷積：

${\sum }_{d\mid n}?(d)=n$

寫成卷積就是$(I??)(n)=id(n)$。

正式開始了

所謂杜教篩就是可以在$n^{\frac{2}{3}}$的時間復雜度內算出積性函數的淺醉和來，所以當數據$\ge 1e8$的時候就只能用杜教篩了。

假設有積性函數$f(n)$，我們要求$S(n)=\sum _{i=1}^{n}f(i)，n\le 1e10$。

根據迪利克雷卷積，我們引入一個新的積性函數$g(n)$，$F(n)=(g?f)(n)$
$$\begin{gathered} \sum _{i=1}^{n}F(i)=\sum _{i=1}^n(g?f)(i)=\sum _{i=1}^n\sum _{d\mid i}g(d)f(\frac{i}{d}) \\ =\sum _{d=1}^{n}g(d)\sum _{d\mid i}f(\frac{i}{d})=\sum _{d=1}^{n}g(d)\sum _{i=1}^{\frac{n}{d}}f(i) \\ =\sum _{d=1}^{n}g(d)S(\frac{n}{d}) \end{gathered}$$
所以有$\sum _{i=1}^{n}F(i)=g(1)S(n)+{\sum }_{d=2}^{n}g(d)S(\frac{n}{d})$

積性函數的定義有$g(1)=1$，所以接下來

$S(n)=\sum _{i=1}^{n}F(i)?\sum _{d=2}^{n}g(d)S(\frac{n}{d})$

如果我們能夠較快速的計算出$\sum _{i=1}^n(g?f)(i)$這個問題就可以通過數論分塊很好的解決了，當然在次之前我們還得預先篩選出前$n^{\frac{2}{3}}$的前綴和來，然后再通過記憶化搜索去得到答案。

幾個例子

一、求$S(n)=\sum _{i=1}^n\mu (i)$

我們先套用上面的式子$S(n)=\sum _{i=1}^{n}g?\mu ?\sum _{d=2}^{n}g(d)S(\frac{n}{d})$

我們考慮到$I?\mu =?$，于是我們得到$S(n)=\sum _{i=1}^n??\sum _{d=2}^{n}S(\frac{n}{d})=1?\sum _{d=2}^{n}S(\frac{n}{d})$

于是我們就完美解決了這個問題。

二、求$S(n)=\sum _{i=1}^{n}i\mu (i)$

上面式子按照套路模板寫下來$S(n)=\sum _{i=1}^{n}g?\mu ?id?\sum _{d=2}^{n}g(d)S(\frac{n}{d})$

同樣的有$\mu ?I=?，??id=id$，

所以我們得到$S(n)=\sum _{i=1}^{n}i?\sum _{d=2}^{n}S(\frac{n}{d})$

貌似推得很有道理，所以我們錯在哪？

事實上我們模板都抄錯了$i\mu (i)$這東西顯然不是迪利克雷卷積，，，

我們設$f(n)=n\mu (n)$，所以$g?f={\sum }_{d\mid n}f(d)g(\frac{n}{d})={\sum }_{d\mid n}d\mu (d)g(\frac{n}{d})$

容易想到${\sum }_{d\mid n}\mu (d)=[n==1]$，所以從這點出發我們考慮$dg(\frac{n}{d})\mu (d)$如何得到含有$\mu (d)$的形式。

顯然，通過觀察如果我們讓$g(n)=n$，上式就有$dg(\frac{n}{d})\mu (d)=d\frac{n}{d}\mu (d)=n\mu (d)$

帶入原式子就變成了$S(n)=\sum _{i=1}^n\sum _{d\mid i}i\mu (d)?\sum _{d=2}^{n}dS(\frac{n}{d})=\sum _{i=1}^{n}i\sum _{d\mid i}\mu (d)?\sum _{d=2}^{n}dS(\frac{n}{d})=\sum _{i=1}^{n}i(i==1)?\sum _{d=2}^{n}dS(\frac{n}{d})$

由此我們成功推出$S(n)=1?\sum _{d=2}^{n}dS(\frac{n}{d})$。

三、求$S(n)=\sum _{i=1}^n?(i)$

直接套就行了這個$S(n)=\sum _{i=1}^{n}g?phi?\sum _{d=2}^{n}g(d)S(\frac{n}{d})$

有$I??=id$，所以$S(n)=\sum _{i=1}^{n}i?\sum _{d=2}^{n}S(\frac{n}{d})$

就直接推出來了。

四、求$S(n)=\sum _{i=1}^{n}i?(i)$

仿照二先推出一個$g$出來，

$f?g={\sum }_{d\mid n}f(d)g(\frac{n}{d})={\sum }_{d\mid n}d?(d)g(\frac{n}{d})$

同樣聯想${\sum }_{d\mid n}?(d)=n$，所以我們同樣地取$g(n)=n=id$

就有$f?g={\sum }_{d\mid n}n?(d)$

帶入杜教篩式子就有$S(n)=\sum _{i=1}^{n}i\sum _{d\mid i}?(d)?\sum _{d=2}^{n}dS(\frac{n}{d})=S(n)=\sum _{i=1}^n{i}^2?\sum _{d=2}^{n}dS(\frac{n}{d})$

總結

以上是生活随笔為你收集整理的杜教筛入门详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。