LOJ#6053. 简单的函数 Min_25筛

发布于 2018-05-27  3.03k 次阅读


Min_25筛可以求一些积性函数的前缀和,复杂度\( O(\frac{n^{\frac{3}{4}}}{ln(n)}) \)。

具体来说,如果对于质数p,f(p)是一个低阶多项式,那么我们就可以求出指数的k次方以及对应系数的乘积来做。

设最终我们求的是f(x)的前缀和:

$$\sum_{i=1}^{n} f(i)  (n \leq 10^{10})$$

$$= \sum _{2 \leq p \leq \sqrt n 且为质数,e \ge 1} f(p^e) (1 + \sum _{2 \leq i \leq \lfloor \frac {n}{p^e} \rfloor ,i无 \leq p的质因子} f(i)) + \sum _{\sqrt n \le p \leq n ,p为质数} f(p)$$

设g(n,m)为上界为n,且最小质因子大于等于第m个质数的p^k的前缀和。我们可以\( O(\frac{n^{\frac{3}{4}}}{ln(n)}) \)的预处理所有素数的前缀和,具体做法与LOJ #2565. 「SDOI2018」旧试题这的筛法比较相似。

之后,设F(n,m)为上界为n,且最小质因子大于等于第m个质数的f的前缀和,我们可以枚举最小质因子以及枚举其次数,然后又出来了一个递推式:

$$F(n,m) = \sum _{t = m, e = 1, P= p_{t}^{e}} f(P) ([e > 1] + F(\lfloor \frac{n}{P}), t+1) +  h_{n} - h_{p_m}$$

然后就可以直接做了。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974