一些积性函数相关的简单筛法

---

useless algorithm 警告…

综述

记录了一些利用筛法求积性函数的方法.

前置知识

数论函数

数论函数指定义域为正整数, 陪域为复数的函数. 下面是几个常用的数论函数.

幂函数

$$\operatorname{Id}_k(n) = n^k$$

特别地, 当 $k = 1$ 时, 记 $\operatorname{Id} = \operatorname{Id}_1(n) = n$.

单位函数

$$\epsilon(n) = [n = 1]$$

其中 $[P]$ 在 $P$ 为真时值为 $1$, $P$ 为假时值为 $0$.

常数函数

$$1(n) = 1$$

积性函数

若数论函数 $f$ 满足

1. $f(1) = 1$.

2. 当 $a$ 和 $b$ 互质 (也记作 $a\perp b$), 即 $\gcd(a, b) = 1$ 时, 有 $f(ab) = f(a)\cdot f(b)$.

则称 $f$ 为积性函数. 特别地, 在此基础上如果 $f$ 还满足对于任意正整数 $a$, $b$ 均有 $f(ab) = f(a)\cdot f(b)$, 则称 $f$ 为完全积性函数.

狄利克雷卷积

对于数论函数 $f$ 与 $g$, 若数论函数 $h$ 满足

$$h(n) = \sum_{d|n}f(d) \cdot g\left(\frac{n}{d}\right)$$

则称 $h$ 为 $f$ 与 $g$ 的狄利克雷卷积, 记作 $h = f\ast g$.

狄利克雷卷积满足结合律, 交换律以及分配律. 此外, 对于任意数论函数 $f$ 有 $f\ast\epsilon = \epsilon\ast f = f$.

埃氏筛 / 埃拉托斯特尼筛

假定现在需要得到 $1$ 到 $n$ 中的所有质数, 一个直接的筛法是从 $2$ 到 $n$ 枚举整数 $i$, 那么除去 $i$ 外的所有 $i$ 的倍数一定是合数. 如果枚举到 $i$ 时该数还没有被标记为合数, 那么 $i$ 为合数. 根据调和级数这样做的时间复杂度为 $O(n\log n)$.

如果在上述过程中只枚举质数的倍数, 就可以得到埃氏筛. 由唯一分解定理可知这样做是对的. 埃氏筛的时间复杂度为

$$O\left(n\sum_{k=1}^{\pi(n)}\frac{1}{p_k}\right) = O(n\log\log n)$$

证明可参考 https://oi-wiki.org/math/number-theory/sieve/.

void eratosthenes(int n) {
  vector<int> npr(n), pr;
  npr[1] = true;
  for (int i = 2; i < n; ++i) {
    if (!npr[i]) {
      pr.push_back(i);
      for (int j = 2 * i; j < n; j += i)
        npr[j] = true;
    }
  }
}

后文的 min_25 筛一定程度上是埃氏筛的拓展.

欧拉筛

仍然考虑如何得到 $1$ 到 $n$ 中的所有质数. 从 $2$ 到 $n$ 枚举整数 $i$, 并依次枚举小于等于 $i$ 的所有质数 $p$. 显然 $i\cdot p$ 一定是合数. 同时, 为了避免一个数被重复标记, 此处希望 $p$ 是 $i\cdot p$ 的最小质因子, 因此当 $i \bmod p = 0$ 时就停止枚举.

这就是欧拉筛. 考虑到每个合数只会被对应的最小质因子标记一次, 欧拉筛的时间复杂度为 $O(n)$.

void euler(int n) {
  vector<int> npr(n), pr;
  npr[1] = true;
  for (int i = 2; i < n; ++i) {
    if (!npr[i]) pr.push_back(i);
    for (int j = 0; j < (int) pr.size() && i * pr[j] < n; ++j) {
      npr[i * pr[j]] = true;
      // pr[j] 是 i * pr[j] 的最小质因子
      if (i % pr[j] == 0) break;
    }
  }
}

一个重要的性质在于, 通过欧拉筛可以得到每个数的最小质因子. 凭借此点可以在 $O(n)$ 的时间复杂度内得到诸多积性函数前 $n$ 项的值. 譬如

约数函数

$$\sigma_k(n) = \sum_{d|n}d^k$$

显然这一系列函数都是积性函数, 下面先来讨论 $k$ 为 $0$ 和 $1$ 的两种情况.

约数个数函数

当 $k=0$ 时, 常用 $d(n)$ 来表示 $\sigma_0(n)$. 此时 $d(n)$ 的含义是 $n$ 的约数个数.

$$d(n) = \sigma_0(n) = \sum_{d|n}1$$

对于正整数 $n$, 由唯一分解定理设 $n$ 可表示为

$$n = \prod_i p_i^{c_i}$$

其中 $p_i$ 为质数. 那么 $d(n)$ 可表示为

$$d(n) = \prod_i (1 + c_i)$$

这就提供了一种计算 $d(n)$ 的方法, 设 $g(n)$ 表示 $n$ 的最小质因子对 $d(n)$ 的贡献, 也就是最小质因子的相应指数再加 $1$. 考虑欧拉筛的过程, 有

• $d(1) = 1$, $g(1) = 1$.

• 若 $i$ 为质数, 有 $d(i) = 2$, $g(i) = 2$.

• 若 $i$ 不为质数, 分两种情况讨论:

  • $i \bmod p_j \neq 0$

    此时 $p_j$ 为 $i\cdot p_j$ 的最小质因子, 且 $i\perp p_j$, 故有

    $$\begin{align*} g(i \cdot p_j) &= 2\\ d(i \cdot p_j) &= d(p_j) \cdot d(i) = 2 \cdot d(i) \end{align*}$$

  • $i \bmod p_j = 0$

    此时 $p_j$ 仍为 $i\cdot p_j$ 的最小质因子, 但对应的指数大于 $1$. 可以利用 $g(i)$ 来更新, 具体而言, 有 $g(i\cdot p_j) = g(i) + 1$. 根据上文的式子, $d(i)$ 和 $d(i \cdot p_j)$ 之间只有 $p_j$ 参与的部分存在不同. 因此有

    $$d(i \cdot p_j) = d(i)\ \frac{g(i \cdot p_j)}{g(i)}$$

另外, 有这样一个流传甚广的表格. 可以看到在 $n$ 很大的时候 $d(n)$ 并不是特别大. 其中的 $\omega(n)$ 表示 $n$ 的不同质因子的个数.

约数和函数

当 $k=1$ 时, 常用 $\sigma(n)$ 来表示 $\sigma_1(n)$. 此时 $\sigma(n)$ 的含义是 $n$ 的所有约数之和.

$$\sigma(n) = \sigma_1(n) = \sum_{d|n}d$$

同 $d(n)$ 类似, 约数和 $\sigma(n)$ 可以表示为

$$\sigma(n) = \prod_i(1+p_i^1+\cdots+p_i^{c_i})$$

记 $n$ 的最小质因子为 $p$, 对应指数为 $c$. 同样设 $g(n)$ 表示 $p$ 对答案的贡献. 则有

$$g(n) = 1 + p + p^2 + \cdots + p^c$$

接下来的过程和 $d(n)$ 几乎相同. 同样的思路可以在 $k \ge 1$ 的情况下沿用. 实际上, 对于任意质数 $p$ 有

$$\sigma_k(p^x) = 1 + p^{k\cdot 1} + p^{k\cdot 2} + \cdots + p^{k\cdot x} = \frac{(p^k)^{x+1} - 1}{p^k - 1}$$

凭借上式以及唯一分解定理就可以解决 $k\ge 1$ 的情况.

欧拉函数

记 $\varphi(n)$ 表示小于等于 $n$ 且同 $n$ 互质的正整数的个数. 即

$$\varphi(n) = \sum_{k=1}^n [\gcd(k, n) = 1]$$

这个形式看不出什么性质, 接下来将进一步推导出一个同 $n$ 的质因数分解相关的形式. 考虑到对于任意质数 $p$, 有

$$\varphi(p^k) = p^k - p^{k-1} = p^k\left(1 - \frac{1}{p}\right)$$

这是很好理解的. 若一个数同 $p$ 的某个幂次 $p^k$ 不互质, 这个数一定是 $p$ 的倍数, 同时在小于等于 $p^k$ 的范围内这个倍数存在 $p^{k-1}$ 个, 故 $\varphi(p^k) = p^k-p^{k-1}$.

又因为 $\varphi(n)$ 为积性函数, 故对于正整数 $n$, 有

$$\varphi(n) = n \prod_i\left(1 - \frac{1}{p_i}\right)$$

接下来分情况讨论就好了, 讨论过程可以参考 $d(n)$.

莫比乌斯函数

$$\mu(n) = \begin{cases} 1 & n=1\\ (-1)^s & n = \prod_{i=1}^s p_i\\ 0 & \text{otherwise} \end{cases}$$

换言之, 对于 $n > 1$, 如果 $n$ 不含有平方因子, 那么 $\mu(n) = (-1)^s$, 其中 $s$ 表示 $n$ 不同质因子的个数; 如果 $n$ 含有平方因子, 那么 $\mu(n) = 0$.

同样地, 接下来分情况讨论就好了.

总而言之, 对于积性函数 $f$, 记 $n$ 的最小质因子为 $p$, 对应次数为 $c$, 且 $n \neq p^c$, 则 $p^c \perp n/p^c$, 因此 $f(n) = f(p^c)f(n/p^c)$. 借此就可以利用欧拉筛计算 $f$.

杜教筛

杜教筛借助了狄利克雷卷积的一些性质, 可以在 $O(n^{2/3})$ 的时间复杂度内计算某些积性函数的前缀和.

欧拉函数

首先有性质 $\operatorname{Id} = \varphi\ast 1$. 这是因为

考虑枚举 $1$ 到 $n$ 中每个整数 $k$ 和 $n$ 的最大公约数 $d$, 有

$$\begin{align*} n &= \sum_{k=1}^n \sum_{d|n} [\gcd(k, n) = d] \\ &= \sum_{d|n} \sum_{k=1}^{n/d} \left[\gcd\left(k, \frac{n}{d}\right) = 1\right] \\ &= \sum_{d|n} \varphi\left(\frac{n}{d}\right) =\sum_{d|n}\varphi(d) \end{align*}$$

此外也可以利用 $(\varphi\ast 1)(p^k) = p^k$ 以及 $\operatorname{Id}_k$ 的完全积性来证明.

记 $\phi(n) = \sum_{k=1}^n \varphi(k)$. 则

$$\begin{align*} \sum_{k=1}^n k &= \frac{1}{2}n(n+1) \\ &= \sum_{k = 1}^n \sum_{d|k}\varphi\left(\frac{k}{d}\right) \\ &= \sum_{d = 1}^n \sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(k) = \sum_{d = 1}^n \phi\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{align*}$$

因此

$$\phi(n) = \frac{1}{2}n(n+1) - \sum_{d=2}^n \phi\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$$

只需用利用 $\lfloor\frac{n}{d}\rfloor$ 的 $O(\sqrt n)$ 种不同就取值就能够计算出 $\phi(n)$, 可以用记忆化搜索来实现, 空间复杂度为 $O(\sqrt{n})$. 此外, 计算一处 $\phi(n)$ 的时间复杂度为 $O(\sqrt{n})$, 即数论分块合并答案的时间复杂度. 记总体的时间复杂度为 $T(n)$, 则

$$\begin{align*} T(n) &= \sum_{k=1}^{\lfloor\sqrt{n}\rfloor} O(\sqrt{k}) + \sum_{k=1}^{\lfloor\sqrt{n}\rfloor}O\left(\sqrt{\left\lfloor\frac{n}{k}\right\rfloor}\right) \\ &= O\left(\int_1^{\sqrt{n}}\left(\sqrt{x} + \sqrt{\frac{n}{x}}\right)\mathrm d x\right) = O(n^{3/4}) \end{align*}$$

如果用欧拉筛预处理 $\phi$ 前 $S$ 项, 且 $S > \sqrt n$, 则有

$$\begin{align*} T(n) &= O(S) + \sum_{k=1}^{n/S} O\left(\sqrt{\left\lfloor\frac{n}{k}\right\rfloor}\right)\\ &= O\left(S + \int_1^{n/S} \sqrt{\frac{n}{x}}\mathrm dx\right) = O\left(S + \frac{n}{S^{1/2}}\right) \end{align*}$$

取 $S = n^{2/3}$, 则 $T(n) = O(n^{2/3})$, 此时的空间复杂度也是 $O(n^{2/3})$. 更为细致的复杂度分析可参考 杜教筛的时空复杂度分析 - riteme.site.

莫比乌斯函数

对于莫比乌斯函数, 则有 $\epsilon = \mu\ast 1$. 下面分两种情况证明这个结论.

当 $n = 1$ 时, 有 $\epsilon(1) = \mu(1) = 1$.

当 $n > 1$ 时, 有 $\epsilon(n) = 0$. 设 $n$ 有 $s$ 个不同质因子, 对于 $n$ 的约数 $d$, 如果 $d$ 能对和式的值产生贡献, 即 $\mu(d) \neq 0$, 则 $d$ 一定是若干 $n$ 的质因子的乘积. 枚举选择的质因子个数 $k$, 有

$$\sum_{d|n} \mu(d) = \sum_{k=0}^s (-1)^k \binom{n}{k} = (1 - 1)^s = 0$$

综上有 $\epsilon = \mu \ast 1$.

另外, 考虑到 $\epsilon \ast f = f$, 若 $g=f\ast 1$, 则有 $g\ast\mu=f\ast 1\ast\mu = f$, 即

$$g(n) = \sum_{d|n}f(d) \iff f(n) = \sum_{d|n}g(d)\mu\left(\frac{n}{d}\right)$$

其实就是所谓的莫比乌斯反演.

记 $M(n) = \sum_{k=1}^n \mu(k)$, 利用

$$\sum_{k=1}^n [k = 1] = 1 = \sum_{k=1}^n\sum_{d|k}\mu\left(\frac{k}{d}\right)$$

借助于分析 $\phi(n)$ 时同样的思路可以得到

$$M(n) = 1 - \sum_{d=2}^n M\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$$

约数个数函数

虽然有 $\sigma_k = \operatorname{Id}_k \ast 1$, 但是

$$\sum_{k=1}^n \sigma_k(n) = \sum_{d=1}^n \left\lfloor\frac{n}{d}\right\rfloor \cdot d^k$$

直接数论分块就好了, 剩余部分就是正整数的 $k$ 次方和.

稍微一般的形式

对于数论函数 $f$ 与 $g$, 记 $F(n) = \sum_{k=1}^n f(k)$, 则

$$\begin{align*} \sum_{k=1}^n \left(f \ast g\right)(k) &= \sum_{k=1}^n \sum_{d|k} g(d)\cdot f\left(\frac{k}{d}\right) \\ &= \sum_{d = 1}^n g(d) \sum_{k=1}^{\lfloor\frac{n}{d}\rfloor} f(k) = \sum_{d = 1}^n g(d) \cdot F\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{align*}$$

因此

$$g(1)\cdot F(n) = \sum_{k=1}^n \left(f\ast g\right)(k) - \sum_{d=2}^n g(d)\cdot F\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$$

在求 $\phi$ 与 $M$ 的过程中, $g$ 可以在 $O(1)$ 的时间复杂度内计算. 实际上, 如果 $f$, $g$, $f\ast g$ 三者的前缀和中存在两个可以在不劣于杜教筛的时间复杂度内计算, 就可以利用杜教筛计算第三个.

Powerful Number 筛

高中的时候听都没听过的东西. 以及终于不是用人名来命名了…

咕咕咕…

洲阁筛

咕咕咕…

min_25 筛

咕咕咕…

参考资料

• 冯东宇, 基础数论, 洛谷 2019 年 OI 夏令营.
• 11Dimensions, 从 1 开始的数论, 洛谷 2019 年 OI 夏令营.
• 任之洲, 积性函数求和的几种方法, 国家集训队 2016 论文集.
• OI wiki, https://oi-wiki.org/.
• riteme, 杜教筛的时空复杂度分析, https://riteme.site/blog/2018-9-11/time-space-complexity-dyh-algo.html
• 铃悬, 铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演, https://www.luogu.com.cn/blog/lx-2003/mobius-inversion.

---