min_25篩

用來干啥？

考慮一個積性函數\(F(x)\)，用來快速計算前綴和$$\sum_{i=1}^nF(i)$$

當然，這個積性函數要滿足\(F(x),x\in Prime\)可以用多項式表示

同時，\(F(x^k),x\in Prime\)要能夠快速計算答案

需要預處理的東西

先不考慮求前綴和的問題，考慮一個積性函數\(F(x)\)

求解$$\sum_{i=1}^n[i\in Prime]F(i)$$

直接求我也會懵逼的，還是找一個函數來算算，假設\(F(x)=x^k\)

那么，求解$$\sum_{i=1}^n[i\in Prime]i^k$$

設\(P\)是質數集合，\(P_i\)表示第\(i\)個質數。

設$$g(n,j)=\sum_{i=1}ⁿⁱk[i\in P\ or \ min(p)>P_j,p|i,p\in P\ ]$$

你問我為什么不寫中文？因為LaTex里面寫中文太丑了

翻譯成人話，\(i\)是質數，或者\(i\)的最小質因子大于\(P_j\)

我們考慮一下\(g(n,j)\)這個函數可以怎么轉移。

考慮第一種情況，如果\(P_j^2>n\)，很明顯，最小質因子是\(P_j\)的最小合數就是\(P_j^2\)

如果\(P_j^2> n\)，顯然不會產生新的貢獻了，此時有\(g(n,j)=g(n,j-1)\)

那么，如果\(P_j^2\le n\)呢？

顯然，從\(P_{j-1}\)到\(P_j\)，我們能夠產生貢獻的值變少了，因此我們要減去一些東西的值。

所以\(g(n,j)=g(n,j-1)-X\)，考慮一下\(X\)是啥。

我們減去的貢獻顯然就是哪些最小質因子是\(P_{j}\)的東西，所以前面有一個\(P_{j}^k\)的系數，

后面有還有一些東西。

現在因為所有數都分成了兩個部分，一個是已經被提出來的\(P_{j}\)，另外一部分是剩余的數。

考慮剩余的數的最小質因數，我們要減去的就是那些最小質因數仍然大于等于\(P_{j}\)的那部分

所以容斥一下，先算上所有的含有\(P_{j}\)這部分的貢獻\(g(\frac{n}{P_{j}},j-1)\)

再減掉其他質數以及最小質因數小于\(P_j\)的那部分，也就是\(g(P_j-1,j-1)\)

所以我們推出轉移

把兩個轉移合并一下，就是

考慮一下\(g(P_{j},j)\)的值？顯然是$$\sum_{i=1}^jP_jk$$

我們要求的是什么？\(g(n,|P|)\)，其中\(|P|\)是\(Prime\)集合的大小，也就是滿足條件的質數的個數。

而我們根據上面的轉移，發現需要的質數只有不大于\(\sqrt n\)的，所以只需要篩出這些質數就好了。

我們來思考一下\(g\)函數所代表的含義，

我們可以理解為在模擬埃氏篩法的過程，

\(g(n,j)\)表示\([1,n]\)排成一列放在這里，但是你已經曬過一些質數了，

你把前\(j\)個質數的倍數全部劃掉了，剩下的求個\(F(x)\)的和就是\(g\)函數。

所以轉移的過程可以理解為已經篩完了前\(j-1\)個質數，現在考慮刪除第\(j\)個質數的過程。

看到這里一定會感覺上面十分的有道理，但是又有一些疑問。

在上面的計算過程中，始終只考慮了\(\le\sqrt n\)的質數，那么，那些\(\gt\sqrt n\)的質數呢？

其實，我們的\(g\)函數要計算的本來就只有質數的值，所以，我們的\(g\)函數算出來的結果并不是真正的結果。

還記得上面對于這類積性函數有什么要求嗎？能夠快速的計算\(F(x),x\in Prime\)。

所以，我們先假設所有的數的計算方法都等同于質數的計算方法，所以我們可以快速的計算前綴和

也就是\(g(n,0)\)，雖然這個值是假的。但是，如果\(g\)中只包含了質數的值的話，那么它的計算結果就是真正的結果。

因此，預處理\(g\)的過程，我們理解為一個計算所有質數的值的過程。

怎么算我們要的東西呢？

接著我們來考慮求積性函數的前綴和。

設$$S(n,j)=\sum_{i=1}^nF(i)[min(p)\ge P_j,p\in P,p|i\ ]$$

后面的意思和上面是一樣的，也就是所有最小質因數大于\(P_j\)的\(i\)的\(F(i)\)之和

那么，\(S(n,j)\)分為兩個部分計算，一部分是所有質數的和，一部分是所有合數的和，\(1\)的值單獨算一下。

所有質數的值顯然可以用\(g\)表示出來，也就是\(g(n,|P|)\)，當然，這里還需要考慮一下質數大小的限制

考慮合數部分的貢獻。

枚舉一下每個合數的最小質因子以及最小質因子的次冪，這樣可以進行轉移。

為什么？

因為\(F(x)\)是一個積性函數，所以我們把它的最小質因數拆出來，考慮剩下部分然后再乘起來是沒有問題的。

所以我們枚舉他的最小質因數，然后只需要考慮除完之后剩下部分的答案就好了。

因為最小質因數已經被除完，所以剩下部分中不能再含有最小質因數。

同時，所有的\(F(p_k^i)\)也被篩掉了，所以需要額外的補進來。

一個栗子

LOJ#6053 簡單的函數

積性函數為\(f(p^c)=p\oplus c,p\in Prime\)

我們來考慮質數的貢獻，因為除\(2\)外的所有質數都是奇數，所以\(f(p)=p-1\)

而\(f(2)=p+1=2+1=3\)

我們先把所有的數的貢獻都當做\(p\)來算，這樣可以方便我們計算\(g\)的值。

再注意到一點，我們真正在計算\(g(n,j)\)的時候，并不需要計算出所有的\(n\)值

我們發現每次轉移的時候只與整除有關，所以考慮一下數論分塊后的結果，

這樣的值大約只有\(2\sqrt n\)個，所以只需要這些數的值。我們可以預處理出來，然后存起來。

初值計算$$g(n,0)=\sum_{i=2}^nf(i)$$

當然這里的\(f(i)\)是“假的”\(f(i)\)，也就是我們把所有的數都當成質數來計算

也就是\(f(i)=i\)，所以求和的結果是\(\frac{n(n+1)}{2}-1\)

然后我們看到上面的式子，還需要維護一下篩出來的質數的前綴\(f(x)\)和，也就是\(g(P_i-1,i)\)

這個的話我們在篩質數的時候直接維護一下就好了。

因為對于所有的質數，我們實際的\(f(i)\)是\(i-1\)，所以還需要維護一下質數的個數，

也就相當于維護一個積性函數\(h(x)=1\)，和前面\(g\)函數一樣的計算就行了。

接下來就表示成\(h(n,j)\)了。

然后如何計算答案？

我們采用遞歸的方法，并且不需要記憶化

先考慮一下\(S(n,j)\)的初值，也就是所有滿足條件的質數的答案

這個答案是$$g(n,|P|)-\sum_{i=1}^{j-1}(P_i-1)-h(n,|P|)$$

為啥？首先是所有質數的\(f(x)\)的值，就是前面的\(g\)函數

然后因為最小的質數是\(P_j\)，所以把小于\(P_j\)的質數的貢獻給減掉

然后因為要計算的\(f(x)\)是\(x-1\)，所以還需要額外減那個\(1\)，也就是質數的個數。

如果\(j=1\)的時候，\(f(2)=3\)，但是在計算過程中我們算的是\(f(2)=1\)，所以需要額外的加二

這樣一來就差不多可以實現了。
代碼戳這里