【算法】Min25 筛 — wrpwrp

用途

• 求积性函数前缀和。
• 要求该积性函数在质数点的取值为关于 $p$的多项式或者可以用完全积性函数模拟出来。

简介？

$\text{Min25}$筛还有一个本质上等价的筛法叫洲阁筛， 其本质来源于扩展的线性筛法。
不妨考虑一下线性筛法的复杂度瓶颈， 其统计答案利用的是枚举每个质因子去贡献其倍数的答案， 然后利用每个数被最小质因子筛去一次的性质进行答案计算。但是事实上在线性筛的过程中在大于 $\sqrt{n}$的质因子的贡献方式相当劣， 实际上只贡献了自己的答案， 考虑根号分治优化这个过程， 然后就有了 $\text{Min25}$和洲阁筛两个基于根号分治的筛法。

求解

大体分三个步骤。

• 筛出 $1\dots\sqrt{n}$中的质数。
• 求解质数处函数的取值。
• 求解合数处函数的取值。

不妨设答案为：
$$\sum_{i = 1}^nf(i)$$

求质数点

为了后文的推导， 使用多个完全积性函数代替原来的 $f$函数。不妨将这个函数记作 $f_0$。
考虑设数组 $g$， 其意义为：
$$g(n, j) = \sum_{i = 1} ^ nf_0(i)[i 是质数或者 i 的最小质因子大于 P_j]$$
那么显然 $g(n, 0) = \sum_{i = 2}^nf_0(i)$是容易求出的， 考虑递推 $g(n, j)$。
$$g(n, j) = g(n, j – 1) – f_0(P_j) \times (g(\lfloor \frac{n}{P_j} \rfloor, j – 1) – \sum_{i = 1}^{j – 1}f_0(P_i)[P_i\leq \lfloor \frac{n}{P_j} \rfloor)$$
意义就是对于所有最小质因子为 $P_j$的数提取到外面， 那么只要剩下的在 $\lfloor \frac{n}{P_j} \rfloor$的这一部分中的数没有被 $P_1\dots P_{j – 1}$这些质数筛除掉，答案中就会计入贡献，但是其中可能会有小于 $\lfloor \frac{n}{P_j} \rfloor$的 $P_1\dots P_{j – 1}$这些质数会计算到答案里面， 但是根据我们的状态这一部分是重复贡献的， 所以需要减掉。考虑放缩掉 $P_i$，那么总的转移式就是：
$$g(n, j) = g(n, j – 1) \ \ \ \ \ \ \ n \leq P_j ^ 2 \ g(n, j) = g(n, j – 1) – f_0(P_j) \times (g(\lfloor \frac{n}{P_j} \rfloor, j – 1) – \sum_{i = 1}^{j – 1}f_0(P_i)) \ \ \ \ n > P_j^2$$
由于第一维只有 $\sqrt{n}$种状态， 第二维的数代表的质数的平方不得超过 $\sqrt{n}$, 所以复杂度约为 $\frac{n ^{\frac{3}{4}}}{\log_n}$。

求合数点

设数组 $s$， 其意义为:
$$S(n, j) = \sum_{i = 1}^ nf(i)[i 是合数且 i 的最小质因子大于等于 P_j]$$

注意质数处是或， 此处是且， 且要求为大于等于某个数。

同样考虑递推， 考虑枚举当前考虑到的质因子的次数并分类讨论。
$$S(n, j) = 0 \ \ \ \ \ P_j^2 > n \ S(n, j) = S(n, j + 1)+\sum_{e = 1}( f(P_j^e) \times (S(\lfloor\frac{n}{p_j^e}\rfloor, j + 1) + \sum_{i = j + 1}f(P_i)[P_iP_j^e\leq n]) + f(P_j^{e + 1}) \ \ \ \ P_j^2 \leq n $$
实际上就是一次性除完最小质因子来递推。

• 除完后为合数， 由积性函数的性质即可。
• 除完以后为质数， 考虑计算大于 $P_j$的质数贡献。
• 除完以后为 $1$， 直接加上即可， 为了是合数将 $e$增加 $1$。

可以发现这三种转移 $P_j^{e + 1} \leq n$, 于是 $e$的上限就知道了。
考虑快速计算 $\sum_{i = j + 1}f(P_i) [P_iP_j^e\leq n]$。差分一下就可以得到下式：
$$\sum_{i = j + 1}f(P_i) [P_iP_j^e\leq n] = g(\lfloor\frac{n}{p^e}\rfloor, m) – \sum_{i = 1}^jf(P_i)[P_iP_j^e\leq n]$$

m 是筛出来的最大的质数的标号。

答案就是 $g(n, m) + S(n, 1) + f(1)$。

一点理解

实质上似乎是先有对于合数的推导， 然后为了解决其中一个求质数点前缀和的问题才引入了质数部分的求解。
这其实也启示我们， 质数部分的求解我们要求的只有那 $\sqrt{n}$个前缀和， 我们完全可以先求出标准的完全积性函数再对那些前缀和进行修正！

代码实现

• 在写代码的时候对于第一维离散化， 具体地， 先整除分块求出会有哪些点， 然后对于小于 $\sqrt{n}$的和大于的分别开数组 $id_0$和 $id_1$记录标号。
• 求质数点的时候可以把函数拆成很多完全积性函数。
• 递推 $g, S$的时候使用滚动数组。
• 递推的时候把第二维放外面， 第一维从 $1 -> num$枚举标号也就是从大到小枚举， 第二维求 $g$的时候从小到大， 求 $S$的时候从大到小枚举。

模板 (Luogu 5235)

Link

习题

$\text{Loj 6235}$

• 题意：
  • 求 $1\dots n$的素数个数。
  • $n\leq 10^{11}$
• 题解
  • 设 $f_0(i) = 1$然后做素数部分的筛法即可。

$\text{Loj 572}$

• 题意
  • $$\sum_{i = 1}^n\sum_{j = 1}^nf(gcd(i, j))^k \mod 2^{32}$$
  • $f(x)$表示 $x$次大的质因子， 重复的质因子多次计算。规定 $f(1) = 0, f(prime) = 1$。
  • $n, k\leq 2\times 10^9$。
• 题解
  • 显然先对这个式子莫比乌斯反演。
  • $$\sum_{i = 1}^n\sum_{j = 1}^nf(gcd(i, j))^k = \sum_{d = 1}^nf(d) ^k\sum_{i = 1}^{\frac{n}{d}}\sum_{j = 1}^{\frac{n}{d}}[gcd(i, j)== 1] \ = \sum_{d = 1}^nf(d)^k(2\sum_{i = 1}^{\frac{n}{d}}\varphi(i) – 1) = \sum_{d =1}^nf(d)^k g(\lfloor \frac{n}{d} \rfloor) $$
  • 显然右边可以整除分块了， 考虑左边怎么算。
  • 虽然那个 $f$不是积性函数， 但是由于其在质数处的特殊取值以及其和质因子相关的特性， 我们可以考虑一下使用 $\text{Min25}$筛。
  • 显然质数处的求值就是直接求素数个数就好了，我们考虑合数处的求值。
  • 同样考虑分类讨论除掉最小质因子的过程。
  • 如果除掉以后是合数， 那就递归下去。
  • 如果除掉以后是质数， 那就会贡献一次答案。
  • 如果除掉以后是 $1$，那当前点也会贡献一下答案。
  • 写出式子来就是:
  • $$S(n, j) = S(n, j + 1)+\sum_{e = 1}S(\lfloor\frac{n}{P_j^e}\rfloor, j+ 1)+P_j^k\times CountPrime(P_j, \frac{n}{P_j^{e}})$$
  • 直接递推就好了。后面那个显然我们会在之前处理掉。
  • $\text{Min25}$不只能筛积性函数！
  • 通过观察函数的性质调整合数和质数部分的求法可以得到奇奇怪怪的函数。

$\text{BZOJ 5234}$

• 题意
  • 求 $1\dots n$中 $\sigma_1$(约数和函数）整除 $p$的所有数之和。
  • $p = \text{2 or 2017}$。
  • $n\leq 10^{10}$。
• 题解
  • 考虑变成所有数减去不整除的部分。
  • 那么其约数和函数不整除 $p$的部分我们用一个函数 $f$来描述， 如果整除了就是 $0$， 否则就是原来那个数。那么我们就是要求这个东西的前缀和。
  • 显然这是个积性函数。
  • 当 $p = 2$的时候质数点除了 $2$都是 $0$， 直接筛就好了。
  • 当 $p = 2017$的时候可能为 $0$的点不多, 由于我们筛积性函数的时候对于质数的部分只需要那几个前缀和， 我们可以暴力枚举 $2017$的约数，用 $\text{Miller_Rabbin}$判断质数， 并维护那些前缀和就好了。