杜教篩

做題發現普通的線性篩法已經解決不了問題了,如n給到1e9 1e10 此時還有20~40分就拿不到了。

但是我們發現要求出來的某個積性函數的字首和的個數是有限的 隻要我們能快速求出某個單點處的字首和即可.

如我們要求$\sum_{i}^{n}{f(i)}$ 我們隻需求出在點n處的值即可是以我們隻要在非線性的時間搞出來即可,顯然題目中的n的個數也是有限個的.

注意使用杜教篩的前提是 f是一個積性函數.

我們再構造兩個積性函數h和g.使得$h=f*g$;

記$S(n)=\sum_{i=1}^{n}f(i)$ 現在開始求$\sum_{i=1}^{n}{h(i)}$

$\sum_{i=1}^{n}{h(i)}=\sum_{i=1}^{n}{\sum_{d|i}{g(d)\cdot f(\frac{i}{d})}}$$\to =\sum_{d=1}^{n}g(d)\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$

$\to \sum_{i=1}^{n}h(i)=\sum_{d=1}^{n}{g(d)}\cdot S(\lfloor\frac{n}{d}\rfloor)$

把右邊第一項給提出來得到了一個杜教篩真正有用的式子.

$g(1)\cdot S(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)$

發現了什麼？隻要我們h這個函數字首和非常的好求 并且對後面的式子進行整除分塊我們就可以在較短的時間内求出S(n).

當然我們要先預處理出大概$n^{\frac{2}{3}}$這麼多的字首和再使用杜教篩此時複雜度為$n^{\frac{2}{3}}$

否則的話就是$n^{\frac{3}{4}}$當然過程中需要map來存一下值 免的重複計算會加速很多..

現在列舉幾個能杜教篩的式子.

1. 求$S(n)=\sum_{i=1}^{n}{\mu(i)}$

發現函數是$\mu$我們用哪一個積性函數卷一下能得到一個非常好用的h函數呢?

很自然的想到 $\sum_{d|n}{\mu(d)}=[n=1]$我們隻需要卷一個$I$即可.

$I*\mu=\sum_{d|n}{\mu(d)\cdot I(\frac{n}{d})}=e(n)$

$e$函數的字首和就是1 那麼杜教篩的式子就變成了 $S(n)=1-\sum_{d=2}^{n} S(\lfloor\frac{n}{d}\rfloor)$

采用上述方法遞歸計算即可.

2. 求$S(n)=\sum_{i=1}^{n}{\phi(i)}$

我們聯想一下$phi$這個函數有什麼優美的性質沒有，有的$\sum_{d|n}{\phi(d)}=n$

顯然卷上$I$函數就等于$id$函數了...

杜教篩的式子為 $S(n)=sum(n)-\sum_{d=2}^{n}S(\lfloor\frac{n}{d}\rfloor)$

$sum(n)=\sum_{i=1}^{n}{i}$等差數列很好計算.帶入求值即可.

3. 求$S(n)=\sum_{i=1}^{n}{i\cdot\phi(i)}$

$f(i)=i\cdot\phi(i)$ 先寫出卷積的形式$\sum_{d|n}{d\cdot\phi(d)\cdot g(\frac{n}{d})}$

我們就可以很顯然的選出函數$id$了

那麼剛才那個卷積就變成了$\sum_{d|n}{n\cdot\phi(d)}\to n\cdot\sum_{d|n}{\phi(d)}\to n^2$

杜教篩的式子為$S(n)=\sum_{i=1}^{n}{i^2}-\sum_{d=2}^{n}{d\cdot S(\lfloor\frac{n}{d}\rfloor)}$

顯然後面那個整除分塊的時候再乘一個等差數列即可.考慮前面的一項怎麼搞..

好尴尬..$\sum_{i=1}^{n}{i^2}$不會求...當然我們大力推式子也是能推的更簡便的方法是百度一下然後記住這個式子.

有了百度上說是$\sum_{i=1}^{n}{i^2}=n(n+1)(2n+1)/6$證明比較有技巧性這裡不再贅述.

是以上式也可以杜教篩了！

值得一提的是不要忽略了函數$h(i)=i^2$這個函數是一個積性函數證明的話原因是由于這是兩個積性函數的卷積是以還是一個積性函數吧.

這裡再寫一遍基礎式 因為很重要...$g(1)\cdot S(n)=\sum_{i=1}^{n}{h(i)}-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)$

一道例題入手：[簡單的數學題](https://www.luogu.com.cn/problem/P3768)(看三天的例題了 再推一邊。

求$(\sum_{i=1}^{n}\sum_{i=1}^{n}{i\cdot j\cdot gcd(i,j)})\mod p$

這裡我直接給出最終的式子 注意在推的時候細節别搞錯！

最後推到的式子是$\sum_{T=1}^{n}{sum(\lfloor\frac{n}{T}\rfloor)^2}\cdot T^2\sum_{x|T}{\frac{T}{x}\mu(x)}$

其中$sum(n)=\sum_{i=1}{n}$前面那個完全可以數論分塊的時候搞 看後面的式子如何杜教篩搞...

也就是我說我們想要在數論分塊中得到$f(T)=T^2\sum_{x|T}{\frac{T}{x}\mu(x)}$

我們發現這本身就是一個類似于卷積的形式了我們不能再給它卷積了那樣更篩不出來了...

卷積？沒錯是一個id函數和$\mu$函數的卷積再乘上了一個常數，那麼顯然$id*\mu=\phi$

是以$f(T)=T^2\phi(T)$再構造一個積性函數和f卷上 先把卷積的形式寫出來是$h(n)=\sum_{d|n}{f(d)\cdot g(\frac{n}{d})}$

卷出的具體結果是$h(n)=\sum_{d|n}{x^2\phi(x)\cdot g(\frac{n}{d})}$

是以很顯然我們構造$g(x)=x^2$那麼$h(n)=n^3$

$f*h=n^3$是以現在要求的是$1^3+2^3+3^3+...n^3$的字首和 這個東西根據國小奧數我們發現等于:$sum(n)^2$

綜上我們再數論分塊的時候使用杜教篩即可.時間複雜度我也不太會計算,但是需要用map來加速.

來道例題：[2020 CCPC-Wannafly Winter Camp Day3 D 求和](https://ac.nowcoder.com/acm/contest/4114/D)

題目意思很簡單就是讓我們推式子 下面是我推的過程.

求 $\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{i}gcd(i,j,k)$

$\sum_{d=1}^{n}d\sum_{i=1}^{n/d}\sum_{j=1}^{i}\sum_{k=1}^{i}\sum_{x|i,x|j,x|k}\mu(x)$

$\sum_{d=1}^{n}d\sum_{x=1}^{n/d}\mu(x)\sum_{i=1}^{n/xd}\sum_{j=1}^{i}\sum_{k=1}^{i}1$

$\sum_{d=1}^{n}d\sum_{x=1}^{n/d}\mu(x)\sum_{i=1}^{n/xd}i^2$

觀察 $x*d<=n$ 枚舉 $T=x*d而d=T/x$

$\sum_{T=1}^{n}\sum_{x|T}\mu(x)\frac{T}{x}\sum_{i=1}^{n/T}i^2$

$\sum_{T=1}^{n}\sum_{i=1}^{n/T}i^2\sum_{x|T}\mu(x)\frac{T}{x}$

因為$\sum_{x|T}\mu(x)\frac{T}{x}$=$\phi(T)$