min25_筛是一种用于快速求出一种积性函数的筛法.
它的使用有三个条件:
1.必须是积性函数
2.必须是低阶多项式的形式
3.(p^j)的函数值能够快速求出,不一定是(O(1)).
首先定义(g(n,j))表示[1,n]中最小质因子(>p_j)或者它是质数,满足两条件之一(i)的(i^k)(低阶多项式那一部分?)的和.
(g(n,j)=sum_{i=1}^n[min p>p_j|iin P]i^k)
(g(n,0)=sumlimits_{i=2}^ni^k)
转移的话分为(p_j^2<=n),(p_j^2>n).
1.若(p_j^2)>n,则不可能存在一个合数满足(min p>p_j),所以(g(n,j)=g(n,j-1))
2.(p_j^2)<=n.
考虑从(g(n,j-1))移动到(g(n,j))的损失必定是(min p==p_j)的那些数的函数值.
(g(n,j)=g(n,j-1)-p_j^k(g(frac{n}{p_j},j-1)-sumlimits_{i=1}^{j-1}p_i^k))
所以
质数函数值前缀和可以线性筛的时候顺便处理.
发现g的第二维是一定的,所以可以省掉一维.
接下来定义(S(n,j))
(S(n,j)=sumlimits_{i=1}^n[min p>=p_j]f(i))
转移讨论质数和非质数的情况.
解释一下.
首先把所有的合法的质数的函数值求出来.
由于g函数只求出来了(i^k)的质数的所有和,因此如果这个积性的函数还包括其他东西还要给它乘上去.
后面是合法的合数的函数值.
枚举k作为最小质因数再枚举出来一个幂次.
因为积性所以可以直接一个F*S.
加上的(F(p_k^{e+1}))是由于质因子里没有1这个东西.
所以对于(p_k^e(e>1))来说就直接被干掉了.
所以要加上(F(p_k^{e+1})).
为什么是(e+1)呢,因为(p^1)作为质数已经被计算了.
很多很多的小细节:
1.因为推式子中出现的(p_j^2<=n)的性质,使得两个函数都只需要(sqrt n)的质数来处理.
2.因为用到的所有的g和S下标都是(frac{n}{...})的形式,所以说只有(sqrt n)种取值.
3.在求g时省掉第二维需要把第一维从大到小枚举,由于整除分块时恰好是从大到小的所以直接正序枚举了.
4.g函数是萎的...因为我们只用它求质数的答案,我并不知道是否有合数的答案...
5.g函数是可以作为整个的F进行答案的计算的.
只不过只有初始值变成了(F(i))
(g(n,j)=g(n,j-1)-p_j^k(g(frac{n}{p_j},j-1)-sumlimits_{i=1}^{j-1}p_i^k))中的(p_j^k)并不能变成(F(p_j^k)).
(这都是牛口胡的)
6.g函数初始值不是自然数幂和,是从2开始的.