對于求數論函數f的1..n前綴和，可以找另一個好求前綴和的函數g，配成狄利克雷卷積。
首先你要有一個好求的狄利克雷卷積前綴和類似
∑ni=1(g?f)(i) ∑ i = 1 n ( g ? f ) ( i ) ，這個東西要能高效率求，不妨設為H以便下文理解
（因為就像一個常數，不需要參與化簡）。

然后我們考慮將其化簡，目的是變出個sum(f(1..n))，然后將剩下的一大堆好求的東西移到另外一邊去。
=∑ni=1∑j|if(j)g(ij) = ∑ i = 1 n ∑ j | i f ( j ) g ( i j )

想要不走彎路化簡，則先枚舉另外函數自變量b，再枚舉被求函數f的自變量i ，以便配出sum(f(1..n))的形式（即上式中的i=下式中的bi）
=∑nb=1∑i=n/bi=1f(i)g(b) = ∑ b = 1 n ∑ i = 1 i = n / b f ( i ) g ( b )

限制的意思是(ib<=n)，再化簡
=∑nb=1g(b)sum(f(1..n/b)) = ∑ b = 1 n g ( b ) s u m ( f ( 1.. n / b ) )

很好，出現了一個可以分塊的n/b.
看到沒有，當b取1的時候我們所求sum(f(1..n))就出現了，將他拿出來。
=sum(f(1..n))+∑nb=2g(b)sum(f(1..n/b)) = s u m ( f ( 1.. n ) ) + ∑ b = 2 n g ( b ) s u m ( f ( 1.. n / b ) )

整理一下我們的成果
H=sum(f(1..n))+∑nb=2g(b)sum(f(1..n/b)) H = s u m ( f ( 1.. n ) ) + ∑ b = 2 n g ( b ) s u m ( f ( 1.. n / b ) )

移項得出最后的式子
sum(f(1..n))=H?∑nb=2g(b)sum(f(1..n/b)) s u m ( f ( 1.. n ) ) = H ? ∑ b = 2 n g ( b ) s u m ( f ( 1.. n / b ) )

這就是最終的結果了owo

因為我們一開始選用的函數g的前綴和就可以高效率求，

該分塊的分塊，再加上記憶化sum(i)，達到 O(n3/4) O ( n 3 / 4 ) 的復雜度。

只要預處理n的2/3次方的sum(i) (證明？？？)，復雜度可以進一步優化成 O(n2/3) O ( n 2 / 3 ) 的復雜度。

總結

以上是生活随笔為你收集整理的杜教筛如何推式子/堆柿子的全部內容，希望文章能夠幫你解決所遇到的問題。

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