杜教篩入門

Orz  OO0OOO00O0OOO0O00OOO0OO

前置知識

狄利克雷卷積

杜教篩

套路

杜教篩是用來求一類積性函數的字首和

它通過各種轉化，最終利用數論分塊的思想來降低複雜度

假設我們現在要求$S(n) = \sum_{i = 1}^n f(i)$，$f(i)$為積性函數,$n \leqslant 10^{12}$

直接求肯定是不好求的，不過現在假設有另一個積性函數$g$

我們來求它們狄利克雷卷積的字首和

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

$$= \sum_{d = 1}^n g(d) \sum_{d|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})$$

然後就化不動了，不過我們發現我們化出了$\frac{n}{d}$！excited

但是$S(n)$怎麼求呢？

容斥一下

$$g(1)S(n) = \sum_{d = 1}^n g(d)S(\frac{n}{d}) - \sum_{d = 2}^n g(d)S(\frac{n}{d})$$

前半部分是狄利克雷卷積的字首和的形式

後半部分可以數論分塊。這樣看起來就好搞多了

現在我們的問題是，如何選擇$g$才能使得上面這個式子好算

這個就要因情況而定了

下面煮幾個典型栗子

$\mu$函數

定理：$\sum_{d \mid n} \mu(d) = [n = 1]$

那麼我們如果選擇$g = 1(i)$，

這樣對于每一項，$(g * f)(i) = \sum_{d \ | i} 1 * \mu(\frac{i}{d}) = e$

其中$e$為原函數，$e = [n = 1]$

是以$g$與$\mu$的卷積的字首和肯定為$1$

上面的式子變為

$S(n) = 1 - \sum_{d = 2}^n S(\frac{n}{d})$

後半部分直接數論分塊就好

$\varphi$函數

定理：$\sum_{d \mid n}\varphi(d) = n$

我們的$g$還是選$1$做卷積

那麼$(g * f)(i) = \sum_{d \ | i} 1 \varphi(\frac{i}{d}) = i$

是以$\sum_{i = 1}^n g * f = \frac{n (n + 1)}{2}$

我們要求得式子變為

$$S(n) = \frac{n * (n + 1)}{2} - \sum_{d = 2}^n S(\frac{n}{i})$$

前半部分$O(1)$算，後半部分數論分塊

題目

目前沒有做多少題目，而且我的杜教篩是分兩波學的，是以碼風差異可能比較大qwq。

洛谷P4213 Sum

BZOJ4805

BZOJ4916

如果需要真·杜教篩題目的話可以去看糖教的部落格

https://blog.csdn.net/skywalkert/article/details/50500009

參考資料

杜教篩——省選前的學習1

我也不知道什麼是"莫比烏斯反演"和"杜教篩"

淺談一類積性函數的字首和

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。