「Min_25 筛」学习笔记

发表于 | 分类于 |

Min_25 太神仙了！
据说这个筛法的复杂度是 \(O\genfrac(){}{}{n^{3/4}}{\log n}\) 或 \(\Theta\left(n^{1 - \epsilon}\right)\) 的。（别问我 \(\epsilon\) 是啥，问就不知道
本质上其实是扩展埃筛。

感谢 chd 哥哥让我学会 Min_25 筛！（@Trisolaris

筛啥用的？

积性函数前缀和，不然用着干啥（
要求被筛的函数 \(f\) 在质数 \(p\) 处的值 \(f\left(p\right)\) 的值为一个关于 \(p\) 的低次多项式，在 \(p^c\) 处的值 \(f\left(p^c\right)\) 可以快速计算。

记号

  • \(\mathbb P\) 表示全体质数的集合。
  • 本文一般默认 \(p \in \mathbb P\)。
  • \(p_k\) 为第 \(k\) 小的质数。特别地，\(p_0 = 1\)。
  • \(\text{lpf}\left(n\right)\) 表示 \(n\) 的最小质因子（即 Least Prime Factor
  • \(F_{\mathbb P} = \sum\limits_{2 \le p \le n} f\left(p\right)\)
  • \(F_k = \sum\limits_{i = 2}^n [p_k \le \text{lpf}\left(i\right)] f\left(i\right)\)

怎么筛？

假设我们已经算出了所有 \(F\)，可以发现答案就是 \(F_1\left(n\right) + f\left(1\right) = F_1\left(n\right) + 1\)。

求 F

枚举最小质因子及其指数可得 \[ \newcommand\ffrac[2]{\genfrac\lfloor\rfloor{}{}{ #1 }{ #2 }} \begin{align*} F_k\left(n\right) & = \sum\limits_{k \le i,p_i^2 \le n} \sum\limits_{c \ge 1,p_i^c \le n}f\left(p_i^c\right)\left([c > 1] + F_{i + 1}\left(\ffrac n{p_i^c}\right)\right) + \sum\limits_{k \le i,p_i \le n} f\left(p_i\right) \\ & = \sum\limits_{k \le i,p_i^2 \le n} \sum\limits_{c \ge 1,p_i^c \le n}f\left(p_i^c\right)\left([c > 1] + F_{i + 1}\left(\ffrac n{p_i^c}\right)\right) + F_{\mathbb P}\left(n\right) - F_{\mathbb P}\left(p_{k - 1}\right) \\ & = \sum\limits_{k \le i,p_i^2 \le n} \sum\limits_{c \ge 1,p_i^{c+1} \le n}\left(f\left(p_i^c\right)F_{i+1}\left(\ffrac n{p_i^c}\right) + f\left(p_i^{c+1}\right)\right) + F_{\mathbb P}\left(n\right) - F_{\mathbb P}\left(p_{k - 1}\right) \end{align*}\]

看起来非常的迷，接受不了。
第一个等号后，第一个和式的意思就是枚举最小质因子，并且显然每个合数的最小质因子一定在 \(\sqrt n\) 内。
第二项是补回质数的贡献，因为 \(c=1\) 时没有计 \(f(p^c)=f(p)\) 的贡献。

第二个等号后只是把第二项根据定义拆成前缀和的形式。

最后一个等号比较奇怪。
注意到若 \(p_i^c \le n < p_i^{c+1}\)，显然有 \(\left\lfloor\frac n{p_i^c}\right\rfloor < p_{i+1}\)，故 \(F_{i+1}\left(\left\lfloor\frac n{p_i^c}\right\rfloor\right) = 0\)。

假设已经求得了所有 \(F_{\mathbb P}\)，现在理论上有两种方法计算 \(F\)，根据上式直接递归就是其中一种。

Yet Another F

话说其实 Min_25 筛有无数种实现方式……重要的是埃氏筛的思想。
所以我也不知道从哪里看来的改成递推形式要换 \(F\) 的定义（逃
（如果不换的话也从上式能导出比较显然的递推式，不过也许这种更好写？

令 \[F_k(n) = \sum\limits_{i=2}^n [p_k \le \text{lpf}(i) \lor i \in \mathbb P]f(i)\]

易知答案同样为 \(F_1(n)+1\)。

考虑一个递推式 \[\begin{align*}F_k(n) =&F_{k+1}(n) \\ +&\sum\limits_{c\ge1,p_k^{c+1}\le n}\left(f(p_k^c)\left(F_{k+1}\left(\ffrac n{p^c}\right)-F_{\mathbb P}\left(p_k\right)\right)+f(p_k^{c+1})\right)\end{align*}\]

于是同样地枚举最小质因子即可。
边界条件为 \(F_{\pi(\sqrt n)+1}(n) = F_{\mathbb P}(n)\)。
似乎因为指数不会很大所以复杂度仍然是 \(O\left(\frac{n^{3/4}}{\log n}\right)\)。

求 f 在质数处的值

根据递推式可以发现实际上需要用到的 \(F_{\mathbb P}\) 只有形如 \(\ffrac n x\) 的 \(O\left(\sqrt n\right)\) 处。
根据条件，\(f\left(p\right)\) 可以写作 \(\sum a_i p^i\)。
故我们可以分别讨论每一项的贡献。

设 \(G_{k,s}\left(n\right) = \sum\limits_{i = 1}^n [p_k < \text{lpf}\left(i\right) \lor i \in \mathbb P]i^s\)。
熟悉埃筛的话，你会发现这相当于是埃筛筛了 \(k\) 轮后剩下的数的 \(s\) 次方之和。

最后我们想要的实际上就是 \(G_{\pi(\sqrt n),s}\left(n\right)\)，其中 \(\pi(\sqrt n)\) 表示 \(|\{p : p \le \sqrt n\}|\)。
因为一个合数的最小质因子肯定不会超过 \(\sqrt n\)。

考虑转移。
对于 \(n < p_k^2\)，并没有筛掉新的数，故直接转移即可。
对于 \(p_k^2 \le n\)，筛掉的数显然有质因子 \(p_k\)，故减去 \(p_k^s G_{k - 1,s}\left(\left\lfloor\frac n{p_k}\right\rfloor\right)\)。
然鹅我们筛掉的应该是 \(\text{lpf}\left(m\right) = p_k\) 的 \(m\)，故要考虑 \(\text{lpf}\left(m\right) < p_k\) 的 \(m\) 的贡献。
实际上就是加回 \(p_k^s G_{k - 1,s}\left(p_{k - 1}\right)\)。
综上所述，有 \[ G_{k,s}\left(n\right) = G_{k - 1,s} - [p_k^2 \le n]p_k^s\left(G_{k-1,s}\left(\ffrac n{p_k}\right) - G_{k-1,s}\left(p_{k-1}\right)\right) \]

复杂度？

并不会证明，由论文可得求 \(F_k\) 的复杂度为 \(\Theta\left(n^{1-\epsilon}\right)\)（第一种方法）。
求 \(F_{\mathbb P}\) 的复杂度为 \(O\left(\frac{n^{3/4}}{\log n}\right)\)（第二种方法的复杂度也长这样）。

一些提示

很多东西可以直接欧拉筛预处理，至于是啥，自己想想。

例题 - LibreOJ 6053.简单的函数

注意到质数除了 \(2\) 都是奇数，故 \(f\left(p\right) = p - 1 + 2[p=2]\)。

于是有 \(G_{0,0}\left(n\right) = -n + 1,G_{0,1} = \dfrac{\left(n+2\right)\left(n-1\right)}2\)。
然后对 \(2\) 讨论一下即可。

递归写法的代码见 https://www.alpha1022.me/articles/loj-6053.htm
Yet Another F 中的写法代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const long long N = 1e10;
const int MX = 1e5;
const int mod = 1e9 + 7;
const int inv = 5e8 + 4;
long long n;
int lim;
int vis[MX + 5],prime[MX + 5],cnt,Gprime[MX + 5];
int tot,le[MX + 5],ge[MX + 5];
long long lis[2 * MX + 5];
int G[2 * MX + 5][2],F[2 * MX + 5];
inline int &id(long long x)
{
    return x <= lim ? le[x] : ge[n / x];
}
int main()
{
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            prime[++cnt] = i,Gprime[cnt] = (Gprime[cnt - 1] + i) % mod;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
        }
    }
    scanf("%lld",&n),lim = sqrt(n);
    for(register long long l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        lis[id(n / l) = ++tot] = n / l;
        G[tot][0] = (n / l % mod - 1 + mod) % mod,G[tot][1] = (n / l % mod + 2) * (n / l % mod - 1 + mod) % mod * inv % mod;
    }
    for(register int k = 1;k <= cnt;++k)
    {
        int p = prime[k];
        long long s = (long long)p * p;
        for(register int i = 1;lis[i] >= s;++i)
            G[i][0] = (G[i][0] - (G[id(lis[i] / p)][0] - (k - 1) + mod) % mod + mod) % mod,
            G[i][1] = (G[i][1] - (long long)p * ((G[id(lis[i] / p)][1] - Gprime[k - 1] + mod) % mod) % mod + mod) % mod;
    }
    for(register int i = 1;i <= tot;++i)
        F[i] = (G[i][1] - G[i][0] + mod) % mod;
    for(register int k = cnt;k;--k)
    {
        int p = prime[k];
        long long s = (long long)p * p;
        for(register int i = 1;lis[i] >= s;++i)
        {
            long long pw = p,pw2 = s;
            for(register int c = 1;pw2 <= lis[i];++c,pw = pw2,pw2 *= p)
                F[i] = (F[i] + (long long)(prime[k] ^ c) * (F[id(lis[i] / pw)] - (Gprime[k] - k + mod) + mod) % mod + (prime[k] ^ c + 1)) % mod;
        }
    }
    printf("%d\n",(F[1] + 1 + (n >= 2) * 2) % mod);
}