跳转至

Min_25 筛

定义

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

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

性质

其可以在 的时间复杂度下解决一类 积性函数 的前缀和问题。

要求: 是一个关于 可以快速求值的完全积性函数之和(例如多项式); 可以快速求值。

记号

  • 如无特别说明,本节中所有记为 的变量的取值集合均为全体质数。
  • ,即 为质数时其值为 ,否则为
  • :全体质数中第 小的质数(如:)。特别地,令
  • ,即 的最小质因数。特别地, 时,其值为

解释

观察 的定义,可以发现答案即为


考虑如何求出 。通过枚举每个 的最小质因子及其次数可以得到递推式:

最后一步推导基于这样一个事实:对于满足 ,有 ,故
其边界值即为

假设现在已经求出了所有的 ,那么有两种方式可以求出所有的

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

现在考虑如何计算
观察求 的过程,容易发现 有且仅有 处的点值是有用的。
一般情况下, 是一个关于 的低次多项式,可以表示为
那么对于每个 ,其对 的贡献即为
分开考虑每个 的贡献,问题就转变为了:给定 ,对所有的 ,求

Notice: 是完全积性函数!

于是设 ,即埃筛第 轮筛完后剩下的数的 值之和。
对于一个合数 ,必定有 。设 为不大于 的最大质数,则 ,即在埃筛进行 轮之后剩下的均为质数。 考虑 的边界值,显然为 。(还记得吗?特别约定了
对于转移,考虑埃筛的过程,分开讨论每部分的贡献,有:

  1. 对于 的部分, 值不变,即
  2. 对于 的部分,被筛掉的数必有质因子 ,即
  3. 对于第二部分,由于 ,满足 会被额外减去。这部分应当加回来,即

则有:


复杂度分析

对于 的计算,其第一种方法的时间复杂度被证明为 (见 zzt 集训队论文 2.3);
对于第二种方法,其本质即为洲阁筛的第二部分,在洲阁论文中也有提及(6.5.4),其时间复杂度被证明为

对于 的计算,事实上,其实现与洲阁筛第一部分是相同的。
考虑对于每个 ,只有在枚举满足 转移时会对时间复杂度产生贡献,则时间复杂度可估计为:

对于空间复杂度,可以发现不论是 还是 ,其均只在 处取有效点值,共 个,仅记录有效值即可将空间复杂度优化至

首先,通过一次数论分块可以得到所有的有效值,用一个大小为 的数组 记录。对于有效值 ,记 中的下标,易得:对于所有有效值

然后分开考虑小于等于 的有效值和大于 的有效值:对于小于等于 的有效值 ,用一个数组 记录其 ,即 ;对于大于 的有效值 ,用一个数组 记录 ,由于 过大所以借助 记录 ,即

这样,就可以使用两个大小为 的数组记录所有有效值的 查询。在计算 时,使用有效值的 代替有效值作为下标,即可将空间复杂度优化至

过程

对于 的计算,我们实现时一般选择实现难度较低的第一种方法,其在数据规模较小时往往比第二种方法的表现要好;

对于 的计算,直接按递推式实现即可。

对于 ,可以用线性筛预处理出 来替代 递推式中的
相应地, 递推式中的 也可以用此方法预处理。

用 Extended Eratosthenes Sieve 求 积性函数 的前缀和时,应当明确以下几点:

  • 如何快速(一般是线性时间复杂度)筛出前 值;
  • 的多项式表示;
  • 如何快速求出

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

  1. 筛出 内的质数与前 值;
  2. 多项式表示中的每一项筛出对应的 ,合并得到 的所有 个有用点值;
  3. 按照 的递推式实现递归,求出

例题

求莫比乌斯函数的前缀和

易知 。则
直接筛即可得到 的所有 个所需点值。

求欧拉函数的前缀和

首先易知
对于 的一次项 ,有
对于 的常数项 ,有
筛两次加起来即可得到 的所有 个所需点值。

「LOJ #6053」简单的函数

给定

易知 。则按照筛 的方法筛,对 讨论一下即可。
此处给出一种 C++ 实现:

参考代码
  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;
}