跳转至

# Min_25 筛

## 定义

从此种筛法的思想方法来说，其又被称为「Extended Eratosthenes Sieve」．

由于其由 Min_25 发明并最早开始使用，故称「Min_25 筛」．

## 性质

其可以在 𝑂(𝑛 3 4 l o g⁡𝑛)O(n 3 4 log⁡n) 或 Θ(𝑛 1−𝜖)Θ(n 1−ϵ) 的时间复杂度下解决一类 积性函数 的前缀和问题．

要求：𝑓(𝑝)f(p) 是一个关于 𝑝 p 可以快速求值的完全积性函数之和（例如多项式）；𝑓(𝑝 𝑐)f(p c) 可以快速求值．

## 记号

- 如无特别说明，本节中所有记为 𝑝 p 的变量的取值集合均为全体质数．
- 𝑥/𝑦 :=⌊𝑥 𝑦⌋x/y:=⌊x y⌋
- i s p r i m e⁡(𝑛) :=[|{𝑑 :𝑑 ∣𝑛}| =2]isprime⁡(n):=[|{d:d∣n}|=2]，即 𝑛 n 为质数时其值为 1 1，否则为 0 0．
- 𝑝 𝑘 p k：全体质数中第 𝑘 k 小的质数（如：𝑝 1 =2,𝑝 2 =3 p 1=2,p 2=3）．特别地，令 𝑝 0 =1 p 0=1．
- l p f⁡(𝑛) :=[1 <𝑛]m i n{𝑝 :𝑝 ∣𝑛} +[1 =𝑛]lpf⁡(n):=[1<n]min{p:p∣n}+[1=n]，即 𝑛 n 的最小质因数．特别地，𝑛 =1 n=1 时，其值为 1 1．
- 𝐹 p r i m e(𝑛) :=∑2≤𝑝≤𝑛 𝑓(𝑝)F prime(n):=∑2≤p≤n f(p)
- 𝐹 𝑘(𝑛) :=∑𝑛 𝑖=2[𝑝 𝑘 ≤l p f⁡(𝑖)]𝑓(𝑖)F k(n):=∑i=2 n[p k≤lpf⁡(i)]f(i)

## 解释

观察 𝐹 𝑘(𝑛)F k(n) 的定义，可以发现答案即为 𝐹 1(𝑛) +𝑓(1) =𝐹 1(𝑛) +1 F 1(n)+f(1)=F 1(n)+1．

考虑如何求出 𝐹 𝑘(𝑛)F k(n)．通过枚举每个 𝑖 i 的最小质因子及其次数可以得到递推式：

𝐹 𝑘(𝑛)=𝑛∑𝑖=2[𝑝 𝑘≤l p f⁡(𝑖)]𝑓(𝑖)=∑𝑘≤𝑖 𝑝 2 𝑖≤𝑛∑𝑐≥1 𝑝 𝑐 𝑖≤𝑛 𝑓(𝑝 𝑐 𝑖)([𝑐>1]+𝐹 𝑖+1(𝑛/𝑝 𝑐 𝑖))+∑𝑘≤𝑖 𝑝 𝑖≤𝑛 𝑓(𝑝 𝑖)=∑𝑘≤𝑖 𝑝 2 𝑖≤𝑛∑𝑐≥1 𝑝 𝑐 𝑖≤𝑛 𝑓(𝑝 𝑐 𝑖)([𝑐>1]+𝐹 𝑖+1(𝑛/𝑝 𝑐 𝑖))+𝐹 p r i m e(𝑛)−𝐹 p r i m e(𝑝 𝑘−1)=∑𝑘≤𝑖 𝑝 2 𝑖≤𝑛∑𝑐≥1 𝑝 𝑐+1 𝑖≤𝑛(𝑓(𝑝 𝑐 𝑖)𝐹 𝑖+1(𝑛/𝑝 𝑐 𝑖)+𝑓(𝑝 𝑐+1 𝑖))+𝐹 p r i m e(𝑛)−𝐹 p r i m e(𝑝 𝑘−1)F k(n)=∑i=2 n[p k≤lpf⁡(i)]f(i)=∑k≤i p i 2≤n∑c≥1 p i c≤n f(p i c)([c>1]+F i+1(n/p i c))+∑k≤i p i≤n f(p i)=∑k≤i p i 2≤n∑c≥1 p i c≤n f(p i c)([c>1]+F i+1(n/p i c))+F prime(n)−F prime(p k−1)=∑k≤i p i 2≤n∑c≥1 p i c+1≤n(f(p i c)F i+1(n/p i c)+f(p i c+1))+F prime(n)−F prime(p k−1)

最后一步推导基于这样一个事实：对于满足 𝑝 𝑐 𝑖 ≤𝑛 <𝑝 𝑐+1 𝑖 p i c≤n<p i c+1 的 𝑐 c，有 𝑝 𝑐+1 𝑖 >𝑛 ⟺ 𝑛/𝑝 𝑐 𝑖 <𝑝 𝑖 <𝑝 𝑖+1 p i c+1>n⟺n/p i c<p i<p i+1，故 𝐹 𝑖+1(𝑛/𝑝 𝑐 𝑖) =0 F i+1(n/p i c)=0．
其边界值即为 𝐹 𝑘(𝑛) =0(𝑝 𝑘 >𝑛)F k(n)=0(p k>n)．

假设现在已经求出了所有的 𝐹 p r i m e(𝑛)F prime(n)，那么有两种方式可以求出所有的 𝐹 𝑘(𝑛)F k(n)：

1. 直接按照递推式计算．
2. 从大到小枚举 𝑝 p 转移，仅当 𝑝 2 <𝑛 p 2<n 时转移增加值不为零，故按照递推式后缀和优化即可．

现在考虑如何计算 𝐹 p r i m e(𝑛)F prime(n)．
观察求 𝐹 𝑘(𝑛)F k(n) 的过程，容易发现 𝐹 p r i m e F prime 有且仅有 1,2,…,⌊√𝑛⌋,𝑛/√𝑛,…,𝑛/2,𝑛 1,2,…,⌊n⌋,n/n,…,n/2,n 这 𝑂(√𝑛)O(n) 处的点值是有用的．
一般情况下，𝑓(𝑝)f(p) 是一个关于 𝑝 p 的低次多项式，可以表示为 𝑓(𝑝) =∑𝑎 𝑖 𝑝 𝑐 𝑖 f(p)=∑a i p c i．
那么对于每个 𝑝 𝑐 𝑖 p c i，其对 𝐹 p r i m e(𝑛)F prime(n) 的贡献即为 𝑎 𝑖∑2≤𝑝≤𝑛 𝑝 𝑐 𝑖 a i∑2≤p≤n p c i．
分开考虑每个 𝑝 𝑐 𝑖 p c i 的贡献，问题就转变为了：给定 𝑛,𝑠,𝑔(𝑝) =𝑝 𝑠 n,s,g(p)=p s，对所有的 𝑚 =𝑛/𝑖 m=n/i，求 ∑𝑝≤𝑚 𝑔(𝑝)∑p≤m g(p)．

注意

𝑔(𝑝) =𝑝 𝑠 g(p)=p s 是完全积性函数！

于是设 𝐺 𝑘(𝑛) :=∑𝑛 𝑖=2[𝑝 𝑘<l p f⁡(𝑖)∨i s p r i m e⁡(𝑖)]𝑔(𝑖)G k(n):=∑i=2 n[p k<lpf⁡(i)∨isprime⁡(i)]g(i)，即埃筛第 𝑘 k 轮筛完后剩下的数的 𝑔 g 值之和．
对于一个合数 𝑥 ≤𝑛 x≤n，必定有 l p f⁡(𝑥) ≤√𝑥 ≤√𝑛 lpf⁡(x)≤x≤n．设 𝑝 ℓ(𝑛)p ℓ(n) 为不大于 √𝑛 n 的最大质数，则 ∑2≤𝑝≤𝑛 𝑔(𝑝) =𝐺 ℓ(𝑛)(𝑛)∑2≤p≤n g(p)=G ℓ(n)(n)，即在埃筛进行 ℓ ℓ 轮之后剩下的均为质数． 考虑 𝐺 G 的边界值，显然为 𝐺 0(𝑛) =∑𝑛 𝑖=2 𝑔(𝑖)G 0(n)=∑i=2 n g(i)．（还记得吗？特别约定了 𝑝 0 =1 p 0=1）
对于转移，考虑埃筛的过程，分开讨论每部分的贡献，有：

1. 对于 𝑛 <𝑝 2 𝑘 n<p k 2 的部分，𝐺 G 值不变，即 𝐺 𝑘(𝑛) =𝐺 𝑘−1(𝑛)G k(n)=G k−1(n)．
2. 对于 𝑝 2 𝑘 ≤𝑛 p k 2≤n 的部分，被筛掉的数必有质因子 𝑝 𝑘 p k，即 −𝑔(𝑝 𝑘)𝐺 𝑘−1(𝑛/𝑝 𝑘)−g(p k)G k−1(n/p k)．
3. 对于第二部分，由于 𝑝 2 𝑘 ≤𝑛 ⟺ 𝑝 𝑘 ≤𝑛/𝑝 𝑘 p k 2≤n⟺p k≤n/p k，满足 l p f⁡(𝑖) <𝑝 𝑘 lpf⁡(i)<p k 的 𝑖 i 会被额外减去．这部分应当加回来，即 𝑔(𝑝 𝑘)𝐺 𝑘−1(𝑝 𝑘−1)g(p k)G k−1(p k−1)．

则有：

𝐺 𝑘(𝑛)=𝐺 𝑘−1(𝑛)−[𝑝 2 𝑘≤𝑛]𝑔(𝑝 𝑘)(𝐺 𝑘−1(𝑛/𝑝 𝑘)−𝐺 𝑘−1(𝑝 𝑘−1))G k(n)=G k−1(n)−[p k 2≤n]g(p k)(G k−1(n/p k)−G k−1(p k−1))

## 复杂度分析

对于 𝐹 𝑘(𝑛)F k(n) 的计算，其第一种方法的时间复杂度被证明为 𝑂(𝑛 1−𝜖)O(n 1−ϵ)（见朱震霆集训队论文 《一些特殊的数论函数求和问题》 2.3）；
对于第二种方法，其本质即为洲阁筛的第二部分，在任之洲论文 《积性函数求和的几种方法》 中也有提及（6.5.4），其时间复杂度被证明为 𝑂(𝑛 3 4 l o g⁡𝑛)O(n 3 4 log⁡n)．

对于 𝐹 p r i m e(𝑛)F prime(n) 的计算，事实上，其实现与洲阁筛第一部分是相同的．
考虑对于每个 𝑚 =𝑛/𝑖 m=n/i，只有在枚举满足 𝑝 2 𝑘 ≤𝑚 p k 2≤m 的 𝑝 𝑘 p k 转移时会对时间复杂度产生贡献，则时间复杂度可估计为：

𝑇(𝑛)=∑𝑖 2≤𝑛 𝑂(𝜋(√𝑖))+∑𝑖 2≤𝑛 𝑂(𝜋(√𝑛 𝑖))=∑𝑖 2≤𝑛 𝑂(√𝑖 l n⁡√𝑖)+∑𝑖 2≤𝑛 𝑂(√𝑛 𝑖 l n⁡√𝑛 𝑖)=𝑂(∫√𝑛 1√𝑛 𝑥 l o g⁡√𝑛 𝑥 d 𝑥)=𝑂(𝑛 3 4 l o g⁡𝑛)T(n)=∑i 2≤n O(π(i))+∑i 2≤n O(π(n i))=∑i 2≤n O(i ln⁡i)+∑i 2≤n O(n i ln⁡n i)=O(∫1 n n x log⁡n x d x)=O(n 3 4 log⁡n)

对于空间复杂度，可以发现不论是 𝐹 𝑘 F k 还是 𝐹 p r i m e F prime，其均只在 𝑛/𝑖 n/i 处取有效点值，共 𝑂(√𝑛)O(n) 个，仅记录有效值即可将空间复杂度优化至 𝑂(√𝑛)O(n)．

首先，通过一次数论分块可以得到所有的有效值，用一个大小为 𝑂(√𝑛)O(n) 的数组 l i s lis 记录．对于有效值 𝑣 v，记 i d(𝑣)id(v) 为 𝑣 v 在 l i s lis 中的下标，易得：对于所有有效值 𝑣 v，i d(𝑣) ≤√𝑛 id(v)≤n．

然后分开考虑小于等于 √𝑛 n 的有效值和大于 √𝑛 n 的有效值：对于小于等于 √𝑛 n 的有效值 𝑣 v，用一个数组 l e le 记录其 i d(𝑣)id(v)，即 l e 𝑣 =i d(𝑣)le v=id(v)；对于大于 √𝑛 n 的有效值 𝑣 v，用一个数组 g e ge 记录 i d(𝑣)id(v)，由于 𝑣 v 过大所以借助 𝑣′ =𝑛/𝑣 <√𝑛 v′=n/v<n 记录 i d(𝑣)id(v)，即 g e 𝑣′ =i d(𝑣)ge v′=id(v)．

这样，就可以使用两个大小为 𝑂(√𝑛)O(n) 的数组记录所有有效值的 i d id 并 𝑂(1)O(1) 查询．在计算 𝐹 𝑘 F k 或 𝐹 p r i m e F prime 时，使用有效值的 i d id 代替有效值作为下标，即可将空间复杂度优化至 𝑂(√𝑛)O(n)．

## 过程

对于 𝐹 𝑘(𝑛)F k(n) 的计算，我们实现时一般选择实现难度较低的第一种方法，其在数据规模较小时往往比第二种方法的表现要好；

对于 𝐹 p r i m e(𝑛)F prime(n) 的计算，直接按递推式实现即可．

对于 𝑝 2 𝑘 ≤𝑛 p k 2≤n，可以用线性筛预处理出 𝑠 𝑘 :=𝐹 p r i m e(𝑝 𝑘)s k:=F prime(p k) 来替代 𝐹 𝑘 F k 递推式中的 𝐹 p r i m e(𝑝 𝑘−1)F prime(p k−1)．
相应地，𝐺 G 递推式中的 𝐺 𝑘−1(𝑝 𝑘−1) =∑𝑘−1 𝑖=1 𝑔(𝑝 𝑖)G k−1(p k−1)=∑i=1 k−1 g(p i) 也可以用此方法预处理．

用 Extended Eratosthenes Sieve 求 积性函数 𝑓 f 的前缀和时，应当明确以下几点：

- 如何快速（一般是线性时间复杂度）筛出前 √𝑛 n 个 𝑓 f 值；
- 𝑓(𝑝)f(p) 的多项式表示；
- 如何快速求出 𝑓(𝑝 𝑐)f(p c)．

明确上述几点之后按顺序实现以下几部分即可：

1. 筛出 [1,√𝑛][1,n] 内的质数与前 √𝑛 n 个 𝑓 f 值；
2. 对 𝑓(𝑝)f(p) 多项式表示中的每一项筛出对应的 𝐺 G，合并得到 𝐹 p r i m e F prime 的所有 𝑂(√𝑛)O(n) 个有用点值；
3. 按照 𝐹 𝑘 F k 的递推式实现递归，求出 𝐹 1(𝑛)F 1(n)．

## 例题

Luogu P4213【模板】杜教筛

求 𝑛∑𝑖=1 𝜑(𝑖)∑i=1 n φ(i) 和 𝑛∑𝑖=1 𝜇(𝑖)∑i=1 n μ(i)．

解答

对于求 𝜑(𝑖)φ(i) 的前缀和，首先易知 𝑓(𝑝) =𝑝 −1 f(p)=p−1．对于 𝑓(𝑝)f(p) 的一次项 (𝑝)(p)，有 𝑔(𝑝) =𝑝,𝐺 0(𝑛) =∑𝑛 𝑖=2 𝑔(𝑖) =(𝑛+2)(𝑛−1)2 g(p)=p,G 0(n)=∑i=2 n g(i)=(n+2)(n−1)2；对于 𝑓(𝑝)f(p) 的常数项 ( −1)(−1)，有 𝑔(𝑝) = −1,𝐺 0(𝑛) =∑𝑛 𝑖=2 𝑔(𝑖) = −𝑛 +1 g(p)=−1,G 0(n)=∑i=2 n g(i)=−n+1．筛两次加起来即可得到 𝐹 p r i m e F prime 的所有 𝑂(√𝑛)O(n) 个所需点值．

对于求 𝜇(𝑖)μ(i) 的前缀和，易知 𝑓(𝑝) = −1 f(p)=−1．则 𝑔(𝑝) = −1,𝐺 0(𝑛) =∑𝑛 𝑖=2 𝑔(𝑖) = −𝑛 +1 g(p)=−1,G 0(n)=∑i=2 n g(i)=−n+1．直接筛即可得到 𝐹 p r i m e F prime 的所有 𝑂(√𝑛)O(n) 个所需点值．

LOJ 6053 简单的函数

给定 𝑓(𝑛)f(n)：

𝑓(𝑛)=⎧{ {⎨{ {⎩1 𝑛=1 𝑝 x o r⁡𝑐 𝑛=𝑝 𝑐 𝑓(𝑎)𝑓(𝑏)𝑛=𝑎 𝑏∧𝑎⟂𝑏 f(n)={1 n=1 p xor⁡c n=p c f(a)f(b)n=a b∧a⟂b

求 𝑛∑𝑖=1 𝑓(𝑖)∑i=1 n f(i)．

解答

易知 𝑓(𝑝) =𝑝 −1 +2[𝑝 =2]f(p)=p−1+2[p=2]．则按照筛 𝜑 φ 的方法筛，对 2 2 讨论一下即可．

参考代码

      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
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    /* 「LOJ #6053」简单的函数 */
    #include <cmath>
    #include <iostream>

    constexpr int MAXS = 200000;  // 2sqrt(n)
    constexpr int mod = 1000000007;

    template <typename x_t, typename y_t>
    void inc(x_t &x, const y_t &y) {
      x += y;
      (mod <= x) && (x -= mod);
    }

    template <typename x_t, typename y_t>
    void dec(x_t &x, const y_t &y) {
      x -= y;
      (x < 0) && (x += mod);
    }

    template <typename x_t, typename y_t>
    int sum(const x_t &x, const y_t &y) {
      return x + y < mod ? x + y : (x + y - mod);
    }

    template <typename x_t, typename y_t>
    int sub(const x_t &x, const y_t &y) {
      return x < y ? x - y + mod : (x - y);
    }

    template <typename _Tp>
    int div2(const _Tp &x) {
      return ((x & 1) ? x + mod : x) >> 1;
    }

    // 以上目的均为防负数和取模
    template <typename _Tp>
    long long sqrll(const _Tp &x) {  // 平方函数
      return (long long)x * x;
    }

    int pri[MAXS / 7], lpf[MAXS + 1], spri[MAXS + 1], pcnt;

    void sieve(const int &n) {
      for (int i = 2; i <= n; ++i) {
        if (lpf[i] == 0) {  // 记录质数
          lpf[i] = ++pcnt;
          pri[lpf[i]] = i;
          spri[pcnt] = sum(spri[pcnt - 1], i);  // 前缀和
        }
        for (int j = 1, v; j <= lpf[i] && (v = i * pri[j]) <= n; ++j) lpf[v] = j;
      }
    }

    long long global_n;
    int lim;
    int le[MAXS + 1],  // x <= \sqrt{n}
        ge[MAXS + 1];  // x > \sqrt{n}
    #define idx(v) (v <= lim ? le[v] : ge[global_n / v])

    int G[MAXS + 1][2], Fprime[MAXS + 1];
    long long lis[MAXS + 1];
    int cnt;

    void init(const long long &n) {
      for (long long i = 1, j, v; i <= n; i = n / j + 1) {
        j = n / i;
        v = j % mod;
        lis[++cnt] = j;
        (j <= lim ? le[j] : ge[global_n / j]) = cnt;
        G[cnt][0] = sub(v, 1ll);
        G[cnt][1] = div2((long long)(v + 2ll) * (v - 1ll) % mod);
      }
    }

    void calcFprime() {
      for (int k = 1; k <= pcnt; ++k) {
        const int p = pri[k];
        const long long sqrp = sqrll(p);
        for (int i = 1; lis[i] >= sqrp; ++i) {
          const long long v = lis[i] / p;
          const int id = idx(v);
          dec(G[i][0], sub(G[id][0], k - 1));
          dec(G[i][1], (long long)p * sub(G[id][1], spri[k - 1]) % mod);
        }
      }
      /* F_prime = G_1 - G_0 */
      for (int i = 1; i <= cnt; ++i) Fprime[i] = sub(G[i][1], G[i][0]);
    }

    int f_p(const int &p, const int &c) {
      /* f(p^{c}) = p xor c */
      return p ^ c;
    }

    int F(const int &k, const long long &n) {
      if (n < pri[k] || n <= 1) return 0;
      const int id = idx(n);
      long long ans = Fprime[id] - (spri[k - 1] - (k - 1));
      if (k == 1) ans += 2;
      for (int i = k; i <= pcnt && sqrll(pri[i]) <= n; ++i) {
        long long pw = pri[i], pw2 = sqrll(pw);
        for (int c = 1; pw2 <= n; ++c, pw = pw2, pw2 *= pri[i])
          ans +=
              ((long long)f_p(pri[i], c) * F(i + 1, n / pw) + f_p(pri[i], c + 1)) %
              mod;
      }
      return ans % mod;
    }

    using std::cin;
    using std::cout;

    int main() {
      cin.tie(nullptr)->sync_with_stdio(false);
      cin >> global_n;
      lim = sqrt(global_n);  // 上限

      sieve(lim + 1000);  // 预处理
      init(global_n);
      calcFprime();
      cout << (F(1, global_n) + 1ll + mod) % mod << '\n';

      return 0;
    }

> 本页面最近更新：2026/2/8 14:42:40，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Marcythm, Tiphereth-A, Xeonacid, MegaOwIer, StudyingFather, CSPNOIP, Enter-tainer, HeRaNO, aofall, Backl1ght, c-forrest, CoelacanthusHex, Enoch-xm, Great-designer, Haohu Shen, iamtwz, Ir1d, kenlig, Konano, ksyx, Persdre, Revltalize, SamZhangQingChuan, shuzhouliu, ZnPdCo
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用