「from CommonAnts」质数计数II 题解

liu_cheng_ao 2017-06-11 22:03:15 2018-04-12 13:21:45

一道经典大水题……

考虑经典的质数计数递推公式。设 p_k 表示第 k 小的质数, S(n,k) 表示不超过 n 的与前 k 个质数互质的数的个数,则不超过 n 的质数有 S(n,\pi (\lfloor \sqrt{n} \rfloor))+\pi (\lfloor \sqrt{n} \rfloor)-1 个。
S 的转移为:

S(n,k)=\begin{cases} n& k=0\\ S(n,k-1)-S(\lfloor \frac{n}{p_k}\rfloor,k-1)& k>0 \end{cases}

那么,现在要计算模 m 意义下每种质数的个数。则可以扩展 S 的定义,即,设 S(n,k,r)(\gcd(m,r)=1) 表示不超过 n 的与前 k 个质数互质的模 m r 的数的个数, \pi (n) 表示不超过 n 的质数个数。则对于 r(\gcd(r,m)=1) 不超过 n 的模 m r 的质数有 S(n,\pi (\lfloor \sqrt{n} \rfloor),r)+\pi (\lfloor \sqrt{n} \rfloor,r)-\epsilon (r) 个,对于 r(\gcd(r,m)>1) 不超过 n 的模 m r 的质数只有可能是 r m+r(r=0) ,特判之。
S 的转移为:

S(n,k,r)=\begin{cases} n& k=0\\ S(n,k-1,r)& k>0,\gcd(p_k,m)>1\\ S(n,k-1,r)-S(\lfloor \frac{n}{p_k}\rfloor,k-1,p_k^{-1}r)& k>0,\gcd(p_k,m)=1 \end{cases}

这样大力递推是 O(\frac{n}{\log n}) 的,使用洲阁筛的优化(参见洲阁2016年集训队论文),就是 O(\frac{n^{\frac{3}{4}}}{\log n}) 的。

UPD:以下的复杂度证明都是错的,正确的优化方法比较复杂,可以参阅相关资料,如《2018年国家候选队论文集》的介绍。

优化:考虑 Meissel-Lehmer 定理。

Meissel-Lehmer 定理 \forall \lfloor \sqrt[3]{n} \rfloor < B \leq \lfloor \sqrt{n} \rfloor ,不超过 n 的质数有 S(n,\pi(B))+\pi(B)-1-\sum\limits_{B<p_i\leq \lfloor \sqrt{n} \rfloor}i (\pi(\lfloor \frac{n}{p_i} \rfloor)-i+1) 个。

以下都是错的 : 后半部分复杂度 O(\frac{n}{B}) ,前半部分 O(\frac{\sqrt{nB}}{\log n}) ,解得当 B=O(n^{\frac 1 3}{\log n}^{\frac 2 3}) 时,此算法达到最优复杂度 O({(\frac n {\log n})}^{\frac 2 3})
然后对Meissel-Lehmer 定理在模意义下同样拓展即可,总复杂度 O(m {(\frac n {\log n})}^{\frac 2 3})