Note -「Min_25 筛」“你就说这素因子你要不要吧?你要不要?”

  赛上想写,Track Lost 了属于是。

\(\mathscr{Intro}\)

  Min_25 筛是用于求积性函数前缀和,同时顺带求出一些“有意思”的信息的筛法。

  一些记号约定

  • \(\mathbb P\) 为素数集,对于以 \(p\) 为记号的数,有 \(p\in\mathbb P\)。
  • \(p_i\) 表示第 \(i\) 小的素数。特别地,\(p_0=1\)。
  • \(\newcommand{\lpf}[0]{\operatorname{lpf}} \lpf(n)\) 表示 \(n\) 的最小素因子。
  • \(a/b=\lfloor\frac{a}{b}\rfloor\).

\(\mathscr{Algorithm}\)

  明确我们的目标:对于积性函数 \(f(n)\),求出

\[\sum_{i=1}^nf(i). \]

此后,我们用 \(m\) 来表示一般的求和上标,而 \(n\) 恒为问题中待求的前缀值。


  Min_25 筛分两步走。第一步:对于所有 \(x\in D=\{n/i\mid i\in[1,n]\}\),求出 \(\sum_{p\le x} f(p)\)。

  这里需要运用 Min_25 筛的核心思想:首先承认所有合数为素数,然后逐步筛掉它们,修正得到正确答案。形式地,令 \(f_P(x)\) 表示 \(f(p)\) 处关于 \(p\) 的多项式,当然我们需要把 \(f_P(x)\) 的定义域从 \(\mathbb P\) 强行钦定为 \(\mathbb N^\star\);最后,定义 \(G(m,i)\) 为

\[G(m,i)=\sum_{j=2}^m[j\in\mathbb P\lor\lpf(j)>p_i]f_P(j). \]

它表示对于 \(2\sim m\),只用前 \(i\) 个素数做埃筛后,承认剩下的数都是素数,得到的 \(f\) 之和。可见我们的目标就是求出所有 \(G(x,\pi(\lfloor\sqrt{n}\rfloor))\)。尝试写出 \(G(m,i)\) 的递推式:

\[G(m,i)=G(m,i-1)-\sum_{j=2}^m[j\notin\mathbb P\land\lpf(j)=p_i]f_P(j). \]

如何优化掉和式?为了将和式转化成 \(G\) 的形式,自然的想法是令 \(j\leftarrow j/p_i\),那么此时就必须追加一个条件:\(f_P(x)\) 为完全积性函数。借此进一步转化:

\[G(m,i)=G(m,i-1)-f_P(p_i)\left[ G(m/p_i,j-1)-\sum_{j<i}f_P(p_j) \right]. \]

注意 \(j<i\le\pi(\lfloor\sqrt n\rfloor)\),所以 \(P(m)=\sum_{i=1}^mf_P(p_i)\) 可以直接预处理出来。复杂度待会儿说√

  可见,就算仅使用 Min_25 筛的第一步,也能解决一些问题。例如令 \(f(n)=1\),就能计算 \(\pi(n)\)。


  第二步:对于所有 \(x\in D\),求出 \(\sum_{i=2}^xf(i)\)。

  还是利用同样的思想,定义 \(F(m,i)\) 为

\[F(m,i)=\sum_{j=2}^m[j\in\mathbb P\lor \lpf(j)>p_i]f(j). \]

它表示素数以及所有被 \(p_{i+1..\pi(n)}\) 筛掉的合数的 \(f\) 之和,\(m\) 的最终答案即为 \(F(m,0)\)。类似与 \(G\) 的转移,不过由于 \(f\) 不一定完全积性,我们不得不枚举 \(p_i\) 的指数,有

\[F(m,i)=F(m,i+1)+\sum_{j\ge1,p_i^{j+1}\le m}f(p_i^j)F(m/p^j,i+1)+f(p_i^{j+1}). \]

注意 \(f(p_i)\) 早已计算过,所以和式的第二项从 \(f(p_i^2)\) 开始累加。

  这里还有一种两层和式的递推方式,据说会引出 \(\mathcal O(n^{1-\epsilon})\) 的递归求解算法。我不会证,而且我一写出来就是这种一层和式,你让我怎么硬生生再套一层,所以略过,抱歉 qwq。


  对于 \(F,G\) 的状态复杂度,有

\[\begin{aligned} T(n) &= \sum_{i=1}^{\sqrt n}\pi\left(\sqrt{n/i}\right)+\sum_{x=1}^{\sqrt n}\pi(i)\\ &= \sum_{i=1}^{\sqrt n}\mathcal O\left(\frac{\sqrt{n/i}}{\ln \sqrt{n/i}}\right)+\mathcal O\left(\frac{\sqrt i}{\ln \sqrt i}\right)\\ &= \mathcal O\left(\int_0^{\sqrt n} \frac{(n/x)^{\frac{1}{2}}}{\frac{1}{2}\ln(n/x)}\text dx\right)\\ &=\mathcal O\left(\int_0^{\sqrt n} \frac{(n/x)^{\frac{1}{2}}}{\frac{1}{4}\ln n}\text dx\right)\\ &= \mathcal O\left(\frac{n^{\frac{3}{4}}}{\ln n}\right). \end{aligned} \]

为了方便理解,\(\log\) 都确切地写作 \(\ln\) 啦。

  这里有个疑点,为什么 \(F\) 的递推形式转移不影响复杂度。没找到资料 qwq。

  对于空间复杂度,滚动 \(i\),\(F(m,i)\) 和 \(G(m,i)\) 都只需要记录 \(\mathcal O(\sqrt n)\) 个 \(n/i\) 的点值。

  麻了,原来什么都不会证。(

上一篇:记录一些密码学中常用符号


下一篇:随机过程总结(3)--一些非平稳过程