min_25筛

时间:2021-10-18 00:41:16

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}^ni^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(n,j)=g(n,j-1)-P_{j}^k[g(\frac{n}{P_{j}},j-1)-g(P_j-1,j-1)]\]

把两个转移合并一下,就是
\[
g(n,j)=
\begin{cases}
g(n,j-1)&P_j^2\gt n\\
g(n,j-1)-P_{j}^k[g(\frac{n}{P_j},j-1)-g(P_j-1,j-1)]&P_j^2\le n
\end{cases}
\]
考虑一下\(g(P_{j},j)\)的值?显然是\[\sum_{i=1}^jP_j^k\]

我们要求的是什么?\(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|)\),当然,这里还需要考虑一下质数大小的限制

考虑合数部分的贡献。

枚举一下每个合数的最小质因子以及最小质因子的次幂,这样可以进行转移。

\[S(n,j)=g(n,|P|)-\sum_{i=1}^{j-1}f(P_i)+\sum_{k\ge j}\sum_{e}(F(P_k^e)S(\frac{n}{P_k^e},k+1)+F(P_k^{e+1}))\]

为什么?

因为\(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\),所以需要额外的加二

这样一来就差不多可以实现了。
代码戳这里