Min25筛
Min25筛总结。
一些记号
1，记 $[A]$ 为表示式 $A$ 的真假。若 $A$ 为真则为 $1$，否则为 $0$。
2，记 $\mathbb{P}$ 为质数集合。
3，记 $P_i$ 为质数集合中第 $i$ 小的数。
4，记 $\min_i(p)$ 为 $i$ 的最小质因子。
5，记 $\pi(n)$ 为 $n$ 以内的质数个数。
简介
这个东东其实不是筛法。。。只是每个人都这么叫。
Min25筛是用来解决一些求积性函数前缀和的问题。设该函数为 $f(i)$，前提为：1， $f(i)$ 为积性函数；2， $\sum_{i=1}^n[i\in\mathbb{P}]f(i)$ 可以通过 $\sum_{i=1}^n[i\in\mathbb{P}]i^k$ 很容易地表示出来，或者直接快速算；3，$f(p^k)$ 可以快速计算。
时间复杂度为 $O(\frac{n^{\frac{3}{4}}}{\log n})$，空间复杂度为 $O(\sqrt n)$。
大概能算一两次 $10^{11}$ 到 $10^{12}$ 的样子。
过程
Part 1
先来看看 $\sum_{i=1}^n[i\in \mathbb{P}]f(i)$ 怎么算。
根据前提条件，这个要用 $\sum_{i=1}^n[i\in \mathbb{P}]i^k$ 表示出来。
也就是 $\sum_{i=1}^n[i\in \mathbb{P}]i^k$ 怎么算。
设 $g(n,j)=\sum_{i=1}^{n}[i\in \mathbb{P}or\min_i(p)> P_j]$，再看看这个怎么算。
相当于埃氏筛筛前 $n$ 个数中，筛完第 $j$ 个质数后，剩下的那些数的和。
考虑这个 $g(n,j)$ 是怎么转移的。如果从 $g(n,j-1)$ 转移过来的话，那么我们需要减掉第 $j$ 次埃氏筛过程中删掉的那些数的和。
也就是 $\min_{i}(p)=P_j$ 的 $i^k$ 的和。
分类讨论：
- 若 $P_j^2 > n$，那么第 $j$ 次埃氏筛就不会筛掉任何数，有 $g(n,j)=g(n,j-1)$。
- 若 $P_j^2\leq n$，那么第 $j$ 次埃氏筛筛的数就是 $\min_{i}(p)=P_j$ 的 $i^k$ 的和，也就是 $P_j^k(g(\left \lfloor \frac{n}{P_j} \right \rfloor,j-1)-g(P_{j-1},j-1))$。可以理解为先把一个 $P_j$ 提取出来，剩下的 $\left \lfloor \frac{n}{P_j} \right \rfloor$ 中 $\min_i(p)\geq P_j$ 的和。用 $g(\left \lfloor \frac{n}{P_j} \right \rfloor,j-1)$ 减掉前面的质数就好了。
那么这个 $g(n,j)$ 可以通过 $g(*,j-1)$ 来算了。
即：
$$g(n,j)=\begin{cases}
g(n,j-1) & \text{ if } P_j^2>n \
g(n,j-1)-P_j^k\left ( g(\left \lfloor \frac{n}{P_j} \right \rfloor,j-1)-g(P_{j-1},j-1) \right ) & \text{ otherwise }
\end{cases}$$
而这个 $j$ 只需要考虑 $\sqrt n$ 以内的数就可以了。
考虑 $g(n,j)$ 怎么转移成 $\sum_{i=1}^n[i\in \mathbb{P}]i^k$，显然有 $\sum_{i=1}^n[i\in \mathbb{P}]i^k=g(n,\pi( \left \lfloor \sqrt n\right \rfloor))$。
Part 2
现在再看看如何算 $\sum_{i=1}^nf(i)$。
设 $S(n,j)=\sum_{i=1}^{n}[\min_i(p)\geq P_j]f(i)$。
那么显然有：$\sum_{i=1}^nf(i)=S(n,1)+f(1)$。
考虑这个 $S(n,j)=\sum_{i=1}^{n}[\min_i(p)\geq P_j]f(i)$ 怎么算。
前面算质数算得这么辛苦，现在要用上了吧。。。
所以还是分类讨论一下。
- 当 $i$ 是质数的时候，答案的和为 $\sum_{i=1}^{n}[i\in \mathbb{P}~and ~i\geq P_j]f(i)$，差分一下变成：$\sum_{i=1}^n[i \in \mathbb{P}]f(i)-\sum_{i=1}^{P_{j-1}}[i\in \mathbb{P}]f(i)$，前面一个显然是可以用 $g(n,\pi( \left \lfloor \sqrt n\right \rfloor))$ 快速计算，后面一个也可以用 $g(P_{j-1},j-1)$ 快速计算。
- 当 $i$ 是合数的时候，由于 $f(i)$ 为积性函数，那么通过枚举最小质因子以及最小质因子的次数，删掉这个最小质因子，也就是：$\sum_{k=j}^{\sqrt n}\sum_{P_k^{q+1}\leq n}(f(P_k^q)S(\left \lfloor \frac{n}{P_k^q} \right \rfloor,k+1)+f(P_{k}^{q+1}))$。有一个 $f(P_{k}^{q+1})$ 是因为 $P_k^{q+1}$ 也被删掉了，需要补回来。
因此，我们得到了：
$$S(n,j)=\left ( g(n,\pi( \left \lfloor \sqrt n\right \rfloor)) \right )-g(P_{j-1},j-1))+ \sum_{k=j}^{\sqrt n}\sum_{P_k^{q+1}\leq n}(f(P_k^q)S(\left \lfloor \frac{n}{P_k^q} \right \rfloor,k+1)+f(P_{k}^{q+1}))$$
Part 3
最后来看看，需要的 $g$ 有哪些？
有两类，一类是 $g(\frac{n}{i},\pi( \left \lfloor \sqrt \frac{n}{i}\right \rfloor))$，令一类是 $g(P_{j},j)$。第一类可以按照 Part 1 ，整除分块预处理出所有的 $g(\frac{n}{i},0)=\sum_{i=2}^{\frac{n}{i}}i^k$，然后枚举质数去计算。第二类实际上就是 $\sum_{i=1}^jf(P_i)^k$，而我们只需要用到 $\sqrt n$ 以内的质数，因此在筛的质数顺便算一算就可以了。
时间复杂度
$O(\frac{n^{\frac{3}{4}}}{\log n})$
不会证。。。
应用
普通积性函数的前缀和
如 $\mu,\varphi$ 等。
$\mu$：当 $i$ 为质数时，$\mu(i)=-1$ ，
因此 $\sum_{i=1}^n[i\in \mathbb{P}]\mu(i)=-\sum_{i=1}^n[i\in \mathbb{P}]i^0$
$\varphi$：当 $i$ 为质数时，$\varphi(i)=i-1$，
因此 $\sum_{i=1}^n[i\in\mathbb{P}]\varphi(i)=(\sum_{i=1}^n[i\in \mathbb{P}]i^1)-(\sum_{i=1}^n[i\in \mathbb{P}]i^0)$
LOJ 6053
题解见此1 |
|