UOJ Logo taorunz的博客

博客

π(n)的计算++

2015-03-13 16:38:43 By taorunz

大家好我叫有兴趣的人!超人熊

看了毛爷爷的【π(n)的计算】之后,我直接被吓傻了

然而,在看了【帅气的算法二】之后,我发现了一个不优美的地方!

就是那个$P_k(x,n)$的计算复杂度和$\Phi(x,n)$的计算复杂度不一样!捂脸熊

这怎么能忍!!!炸弹熊

其实我们可以做到$O(x^\frac34)$

我们把$y$取成一个$x^{\frac14}$左右的数

这样,$\Phi(x,n)$的计算降低到了$O(x^\frac34)$

同时$P_k(x,n)$由于涉及到最大到$\frac xy$的$\pi$值,所以需要筛出$O(x^\frac34)$的质数

总共加起来的复杂度还是$O(x^\frac34)$的! 坏笑熊

一个小bug

Wait!

这里有个问题!

由于$y$减小了$P_3(x,n)$不再是0了!

思考熊

怎么办呢?

其实可以直接暴力的!

$P_3(x,n)$的意思是小于$x$的数中,可以表示为$3$个大于$p_n$的质数之积的个数。

我们枚举第一小和第二小的质数,会发现一个不超过$x^\frac13$,一个不超过$x^\frac38$,总共只有$x^\frac{17}{24}$,比$x^\frac34$少了$x^\frac1{24}$呢!

这样就完美解决啦!鼓掌熊

经过修改的算法比原来的$n^\frac56$相比,在$x=10^9$的时候,从$329\texttt{ms}$ 缩短到了$94\texttt{ms}$(vfk教导我们单位要用等宽字体)!

$x=10^{10}$也可以1秒出解啦!

(其实这篇blog里所有表情都出现啦!)

评论

VictorWonder
前排ORZ
ydc
妈呀
vivym
前排跪....
Picks
玛雅
TKD
前排Orz
18357
前排Orz
zangfenziang
orz
matthew99
干嘛不在3月14日15时9分发
PoPoQQQ
前排跪
WuHongxun
后排Orz!
nneztlk
现在再看这篇感觉trz萌萌哒(最后一个UOJ太不自然辣,差评)
liu_cheng_ao
用Lehmer定理可以做到$O(n^{\frac 2 3})$ 令$\sqrt[3]m\leq y \leq \sqrt m, n=\pi(y), p_n=\text{第}n\text{个质数}$,设: $$ \phi(m,0)=m \\ \phi(m,n) = \phi(m,n-1) - \phi\left(\frac{m}{p_n}, n-1\right) \\ P_2(m,n) = \displaystyle \sum_{y\lt p \leq \sqrt m}\left(\pi\left(\frac{m}{p}\right)-\pi(p)+1\right) $$ 有: $$ \pi(m)=\phi(m,n)+n-1-P_2(m,n) $$ 其中$\phi$可以递推计算(参加2016年洲阁的集训队论文),由于只需考虑不超过$\lfloor \frac n 3 \rfloor$的质数,复杂度为$O(\frac {n^{\frac 2 3}} {\log n})$(证明方法与洲阁的集训队论文相同),其它部分均用线性筛暴力算,复杂度为$O(n^{\frac 2 3})$,总复杂度$O(n^{\frac 2 3})$。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。