首页 > 其他 > 详细

Min_25筛 学习笔记

时间:2018-12-11 14:11:28      阅读:438      评论:0      收藏:0      [点我收藏+]

这儿只是一个简单说明/概括/总结。
原理见这:
https://www.cnblogs.com/cjyyb/p/9185093.html
https://www.cnblogs.com/zhoushuyu/p/9187319.html


首先计算\[g(n,j)=\sum_if(i),\quad i是质数\ 或\ i的最小质因子严格大于P_j\\g(n,j)=\begin{cases}g(n,j-1)&P_j^2\gt n\\ g(n,j-1)-f(P_j)\left[g(\frac{n}{P_j},j-1)-\sum_{i=1}^{j-1}f(P_i)\right]&P_j^2\le n\end{cases}\]

类似埃氏筛法,\(P(n,j)\)就是筛\(j\)次后剩下的数的\(f\)和,再加上所有质数\(p\)\(f(p)\)之和。

\(P_j^2>n\)时,这一次筛不会筛掉任何数,所以就是\(g(n,j-1)\)

\(P_j^2\leq n\)时,考虑第\(j\)次筛掉了哪些数,也就是最小质因子是\(P_j\)的那些数。因为是积性函数,所以我们直接提出一个\(P_j\)(来保证它含\(P_j\))。
要被筛掉的数在除掉一个\(P_j\)后的最小质因子一定仍大于等于\(P_j\)(否则在之前就被筛掉了),这符合\(g(\frac{n}{P_j},j-1)\)的定义。所以减掉一个\(f(P_j)g(\frac{n}{P_j},j-1)\)。但是\(g(\frac{n}{P_j},j-1)\)还包含所有质数的\(f(p)\)之和,所以再加上\(\sum_{i=1}^{j-1}f(P_i)\)

那初值呢?先把所有合数的\(f\)的计算方式看做和质数一样,以便对所有数的\(f\)值快速求个和,用它作为\(g(n,0)\)。这样虽然合数的\(f\)值是假的,但是\(g(n,|P|)\)还是能正确的表示所有质数\(p\)\(f(p)\)之和。


现在考虑算上合数的\(f\)值求和。令\[S(n,j)=\sum_if(i),\quad i是质数\ 或\ i的最小质因子大于等于P_j\]

我们把\(S(n,j)\)分两部分计算,一是所有质数的贡献,二是所有合数的贡献。对于\(f(1)\)最后单独算下。

那么所有质数的贡献可以用\(g\)表示,也就是\(g(n,j)-\sum_{i=1}^{j-1}f(P_i)\)(因为最小质因子要大于等于\(P_j\),所以把那些减掉)。

对于合数,枚举这个合数的最小质因子及其次数,用积性函数的性质直接算:\[S(n,j)=g(n,j)-\sum_{i=1}^{j-1}f(P_i)+\sum_{k=j}^{P_k^2\leq n}\sum_{e=1}^{P_k^{e+1}\leq n}\left[f(P_k^e)\times S(\frac{n}{P_k^e},k+1)+f(P_k^{e+1})\right]\]

\(f(P_k^{e+1})\)\(S\)没有考虑的那部分(就是\(P_k^{e+1}\)这样的合数,而\(S(..,k+1)\)就把这些数忽略掉了)。

答案就是\(S(n,1)+f(1)\)


流程:

  1. 把所有合数看做质数,求一遍和,得到初值\(g(n,0)\)。同时预处理一个\(f(P_i)\)的前缀和。

  2. \[g(n,j)=\begin{cases}g(n,j-1)&P_j^2\gt n\\ g(n,j-1)-f(P_j)\left[g(\frac{n}{P_j},j-1)-\sum_{i=1}^{j-1}f(P_i)\right]&P_j^2\le n\end{cases}\]
    计算\(g(x,|P|)\)(把第二维滚动掉)。

  3. \[S(n,j)=g(n,j)-\sum_{i=1}^{j-1}f(P_i)+\sum_{k=j}^{P_k^2\leq n}\sum_{e=1}^{P_k^{e+1}\leq n}\left[f(P_k^e)\times S(\frac{n}{P_k^e},k+1)+f(P_k^{e+1})\right]\]
    计算\(S(n,1)+f(1)\)

计算\(S,g\)的复杂度都是\(O(\frac{n^{\frac34}}{\log n})\)

对于其它积性函数,同\(g\)一样计算。


例题:
LOJ 6053 简单的函数

Min_25筛 学习笔记

原文:https://www.cnblogs.com/SovietPower/p/10101811.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!