min_25筛

Problem

对于积性函数 latex F(x),求 latex \sum\limits_{x=1}^{n}F(x),n\le 10^{10}

latex F(x) 满足 latex F(p) 可以用多项式表示,且可以快速求出 latex F(p^k)latex p 指质数)。


Prepare

latex P 为质数集合,latex P_i 表示第 latex i 个质数。

先不考虑怎么求答案,来求一下这个式子 latex \sum\limits_{i=1}^{n}[i\in P]F(i)

latex g(n,j)=\sum\limits_{i=1}^{n}[i\in P\text{或}i\text{的最小质因子大于}j]F(i)

这里的 latex F(i) 是把所有数都当作质数来算,也就是说只有质数位是对的,但仍要保证 latex F(i) 是积性函数。

如何设计 latex g(n,j) 的转移方程呢?

latex P_j^2 > n 时,latex P_j 不会产生贡献,有 latex g(n,j)=g(n,j-1)

latex P_j^2\le n 时,要减去最小质因子为 latex P_j 的数的贡献。即为 latex F(P_j)(g(\frac{n}{P_j},j-1)-g(P_j-1,j-1))

括号里面的部分可以理解为数 latex x 满足最小质因子等于 latex P_{j-1}latex xP_j\le n的贡献,后面一半减去了多余部分。

因为积性函数的性质,最外面乘一个 latex F(P_j) 即可。

这样我们得到了转移方程
g(n,j)= \begin{cases} g(n,j-1)&P_j^2\gt n\\ g(n,j-1)-F(P_{j})(g(\frac{n}{P_j},j-1)-g(P_j-1,j-1))&P_j^2\le n \end{cases}

显然我们现在想知道的 latex \sum\limits_{i=1}^{n}[i\in P]F(i)=g(n,|P|)

注意到用来转移的质数不超过 latex \sqrt{n}

latex g(n,j) 还有一个问题,我们始终不知道大于latex \sqrt{n} 的质数的函数值。

实际上这里把所有数都当作质数来求 latex g(n,j),一般来讲可以快速求出一个假的前缀和 latex g(n,0)

虽然我们的 latex g(n,0) 是假的前缀和,但是如果我们只取其中质数,就得到了真的 latex \sum\limits_{i=1}^{n}[i\in P]F(i)

显然假的前缀和都是不需要的,我们只需要 latex \sum\limits_{i=1}^{n}[i\in P]F(i)=g(n,|P|)。又注意到转移方程里有整除,那么第一维可数论分块到 latex \sqrt{n}


Solution

继续考虑真正要求的前缀和,设为 latex S(n,j)=\sum\limits_{i=1}^{n}[i\in P\text{或}i\text{的最小质因子大于等于}j]F(i)

这里的 latex F(i) 就需要真实的值了。

分成三个部分计算,质数、合数和 latex 1

质数直接调用之前的 latex g(n,|P|)latex 1 特判,合数枚举它的最小质因数转移。
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}))

解释一下最后一段,枚举最小质因子和次数,刨去最小质因子后计算剩余部分的答案,仍然是用积性函数的性质相乘。

注意到刨去最小质因子时 latex P_j^k 都被忽略了,所以要加上最后的 latex F(P_k^{e+1})

直接递归解出 latex S(n,1),不需要记忆化。

复杂度:latex O(\frac{n^{\frac{3}{4}}}{logn})

证明:不会


Example

[LOJ6053]简单的函数

[SPOJ]DIVCNTK – Counting Divisors (general)

参考资料

yyb的博客

发表评论

电子邮件地址不会被公开。 必填项已用*标注