「Learning Notes」Prefix Sum of Multiplicative Functions

本文会随着笔者的水平提升持续更新。
若发现文中有叙述不严谨之处,欢迎指出。
本文主要介绍求积性函数前缀和的几种常见方法。
前置技能:Arithmetic Functions

Description

给定一个积性函数 f(n) ,求

S(n)=\sum_{i = 1}^{n}f(i)

杜教筛

该方法据传起源于 Project Euler,由 dls 引入中国的 OI/ACM 界,故称「杜教筛」。
其可以在 O\left(n^{\frac{2}{3}}\right) 的时间复杂度下解决一类数论函数的前缀和问题。
要求: f(x) [1, k] 内的所有点值可以快速求出。

Notations

  • 若无特殊说明,本节中出现的 '\ast' 符号均表示狄利克雷卷积(Dirichlet Convolution)
  • x / y := \left\lfloor\frac{x}{y}\right\rfloor

Method

考虑构造一个数论函数 g ,且 g f \ast g 的前缀和可以在较低的时间复杂度内求值,则:

\begin{aligned} \sum_{i = 1}^{n} (f \ast g)(i) &= \sum_{ij \le n} f(i) g(j) \\ &= \sum_{i = 1}^{n} g(i) \sum_{j \le n / i} f(j) \\ &= \sum_{i = 1}^{n} g(i) S(n / i) \\ g(1) S(n) &= \sum_{i = 1}^{n} (f \ast g)(i) - \sum_{i = 2}^{n} g(i) S(n / i) \end{aligned}

则按 n / d 的值分段并递归计算即可。

Complexity

由上一节中得到的递推式可知只需求出 S

1, 2, \dots, \left\lfloor\sqrt{n}\right\rfloor, n / \sqrt{n}, \dots, n / 2, n

O(\sqrt{n}) 个点的取值即可在 O(\sqrt{n}) 的时间复杂度内求出 S(n) ,即:

T(n) = O(\sqrt{n}) + \sum_{i^{2} \le n} T(i) + \sum_{i^{2} \le n} T\left(\frac{n}{i}\right) = O(\sqrt{n}) + \sum_{i^{2} \le n} O(\sqrt{i}) + \sum_{i^{2} \le n} O\left(\sqrt{\frac{n}{i}}\right)

此处更深层的复杂度为高阶小量,故不再进一步展开.

则有:

\sum_{i^{2} \le n} \sqrt{i} = \int_{0}^{\sqrt{n}} \sqrt{x} \mathrm{d} x = \int_{0}^{\sqrt{n}} x^{\frac{1}{2}} \mathrm{d} x = \left. \frac{2}{3} x^{\frac{3}{2}} \right|_{0}^{\sqrt{n}} = \frac{2}{3} n^{\frac{3}{4}}

\sum_{i^{2} \le n} \sqrt{\frac{n}{i}} = \sqrt{n} \int_{0}^{\sqrt{n}} \sqrt{\frac{1}{x}} \mathrm{d} x = \sqrt{n} \int_{0}^{\sqrt{n}} x^{-\frac{1}{2}} \mathrm{d} x = \sqrt{n} \times \left. 2x^{\frac{1}{2}} \right|_{0}^{\sqrt{n}} = 2n^{\frac{3}{4}}

T(n) = O(\sqrt{n}) + O\left(n^{\frac{3}{4}}\right) + O\left(n^{\frac{3}{4}}\right) = O\left(n^{\frac{3}{4}}\right)

由于 f(x) 的前缀区间内点值可以快速求出,则可以预处理一部分 S(n) 的值。

设预处理前 k S(n) 的值,且 \sqrt{n}\le k ,预处理时间复杂度为线性,则:

T(n) = O(\sqrt{n}) + O(\sqrt{n}) + \sum_{ik \le n} O\left(\sqrt{\frac{n}{i}}\right) + O\left(\sqrt{n} - \frac{n}{k}\right) = O\left(\sqrt{n} + \frac{n}{\sqrt{k}}\right)

总时间复杂度为

O(k) + T(n) = O\left(k + \sqrt{n} + \frac{n}{\sqrt{k}}\right)

可知当 k = n^{\frac{2}{3}} 时可取到最小,为 O\left(n^{\frac{2}{3}}\right)

大部分情况下杜教筛都用于解决积性函数的前缀和问题,故预处理部分可以用线性筛做到线性时间复杂度;
但有时会有特殊情况,如「HDU 5608」。此时需要重新平衡时间复杂度。

Implementation

用杜教筛求数论函数 f 的前缀和时,最重要的就是要找到合适的 g
f 不是常见的积性函数甚至不是积性函数(如「HDU 5608」)时,可能需要构造一个。
实现时使用线性筛预处理出前 n^{\frac{2}{3}} S(n) 的值,对于 n^{\frac{2}{3}} < x S(x) 使用 hash 表记忆化即可。

一个可以有效减小常数的小 trick: 此处其实并不需要使用 hash 表。
n^{\frac{2}{3}} < x 时,由 (n / a) / b = n / ab 发现所有的 x 均能表示成 n / y 的形式;又由于 n^{\frac{2}{3}} < x ,则必有 y < n^{\frac{1}{3}}
故使用一个长度为 n^{\frac{1}{3}} 的数组储存即可。其中 S(x) 的值储存在下标为 n / x 的位置。
Notice当有多组询问且每组询问的 n 不同时,应在处理询问之前将该数组清零。

这个 trick 在洲阁筛和 Extended Eratosthenes Sieve 的实现中均有用到。

Examples

Prefix Sum of Möbius Function

\displaystyle \sum_{i = 1}^{n} \mu(i)

由于 \mu \ast 1 = \epsilon ,故取 g = 1 ,有:

\begin{aligned} 1(n) S(n) &= \sum_{i = 1}^{n} \epsilon(i) - \sum_{i = 2}^{n} 1(i) S(n / i) \\ S(n) &= 1 - \sum_{i = 2}^{n} S(n / i) \end{aligned}

Prefix Sum of Euler's Totient Function

\displaystyle \sum_{i = 1}^{n} \varphi(i)

由于 \varphi \ast 1 = I ,故取 g = 1 ,有:

\begin{aligned} 1(n) S(n) &= \sum_{i = 1}^{n} I(i) - \sum_{i = 2}^{n} 1(i) S(n / i) \\ S(n) &= \frac{n(n + 1)}{2} - \sum_{i = 2}^{n} S(n / i) \end{aligned}

Extended Eratosthenes Sieve

由于其由 min25 发明并最早开始使用,故又称「min25 筛」。
其可以在 O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right) \Theta\left(n^{1 - \epsilon}\right) 的时间复杂度下解决一类积性函数的前缀和问题。
要求: f(p) 是一个关于 p 的项数较少的多项式或可以快速求值; f(p^{c}) 可以快速求值。

Notations

  • 如无特别说明,本节中所有记为 p 的变量的取值集合均为全体质数。
  • x / y := \left\lfloor\frac{x}{y}\right\rfloor
  • \operatorname{isprime}(n) := [ |\{d : d | n\}| = 2 ]
  • p_{k} :全体质数中第 k 小的质数(如: p_{1} = 2, p_{2} = 3 )。特别地,令 p_{0} = 1
  • \operatorname{lpf}(n) := [1 < n] \min\{p : p | n\} + [1 = n]
  • F_{\mathrm{prime}}(n) := \sum_{2 \le p \le n} f(p)
  • F_{k}(n) := \sum_{i = 2}^{n} [p_{k} \le \operatorname{lpf}(i)] f(i)

Method

观察 F_{k}(n) 的定义,可以发现答案即为 F_{1}(n) + f(1) = F_{1}(n) + 1


考虑如何求出 F_{k}(n) 。通过枚举每个 i 的最小质因子及其次数可以得到递推式:

\begin{aligned} F_{k}(n) &= \sum_{i = 2}^{n} [p_{k} \le \operatorname{lpf}(i)] f(i) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c} \le n}} f\left(p_{i}^{c}\right) ([c > 1] + F_{i + 1}\left(n / p_{i}^{c}\right)) + \sum_{\substack{k \le i \\ p_{i} \le n}} f(p_{i}) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c} \le n}} f\left(p_{i}^{c}\right) ([c > 1] + F_{i + 1}\left(n / p_{i}^{c}\right)) + F_{\mathrm{prime}}(n) - F_{\mathrm{prime}}(p_{k - 1}) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c + 1} \le n}} \left(f\left(p_{i}^{c}\right) F_{i + 1}\left(n / p_{i}^{c}\right) + f\left(p_{i}^{c + 1}\right)\right) + F_{\mathrm{prime}}(n) - F_{\mathrm{prime}}(p_{k - 1}) \end{aligned}

最后一步推导基于这样一个事实:对于满足 p_{i}^{c} \le n < p_{i}^{c + 1} c ,有 p_{i}^{c + 1} > n \iff n / p_{i}^{c} < p_{i} < p_{i + 1} ,故 F_{i + 1}\left(n / p_{i}^{c}\right) = 0
其边界值即为 F_{k}(n) = 0 (p_{k} > n)

假设现在已经求出了所有的 F_{\mathrm{prime}}(n) ,那么有两种方式可以求出所有的 F_{k}(n)

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

现在考虑如何计算 F_{\mathrm{prime}}{(n)}
观察求 F_{k}(n) 的过程,容易发现 F_{\mathrm{prime}} 有且仅有 1, 2, \dots, \left\lfloor\sqrt{n}\right\rfloor, n / \sqrt{n}, \dots, n / 2, n O(\sqrt{n}) 处的点值是有用的。
一般情况下, f(p) 是一个关于 p 的低次多项式,可以表示为 f(p) = \sum a_{i} p^{c_{i}}
那么对于每个 p^{c_{i}} ,其对 F_{\mathrm{prime}}(n) 的贡献即为 a_{i} \sum_{2 \le p \le n} p^{c_{i}}
分开考虑每个 p^{c_{i}} 的贡献,问题就转变为了:给定 n, s, g(p) = p^{s} ,对所有的 m = n / i ,求 \sum_{p \le m} g(p)

Notice: g(p) = p^{s} 是完全积性函数!

于是设 G_{k}(n) := \sum_{i = 1}^{n} \left[p_{k} < \operatorname{lpf}(i) \lor \operatorname{isprime}(i)\right] g(i) ,即埃筛第 k 轮筛完后剩下的数的 g 值之和。
对于一个合数 x ,必定有 \operatorname{lpf}(x) \le \sqrt{x} ,则 F_{\mathrm{prime}} = G_{\left\lfloor\sqrt{n}\right\rfloor} ,故只需筛到 G_{\left\lfloor\sqrt{n}\right\rfloor} 即可。
考虑 G 的边界值,显然为 G_{0}(n) = \sum_{i = 2}^{n} g(i) 。(还记得吗?特别约定了 p_{0} = 1
对于转移,考虑埃筛的过程,分开讨论每部分的贡献,有:

  1. 对于 n < p_{k}^{2} 的部分, G 值不变,即 G_{k}(n) = G_{k - 1}(n)
  2. 对于 p_{k}^{2} \le n 的部分,被筛掉的数必有质因子 p_{k} ,即 -g(p_{k}) G_{k - 1}(n / p_{k})
  3. 对于第二部分,由于 p_{k}^{2} \le n \iff p_{k} \le n / p_{k} ,故会有 \operatorname{lpf}(i) < p_{k} i 被减去。这部分应当加回来,即 g(p_{k}) G_{k - 1}(p_{k - 1})

则有:

G_{k}(n) = G_{k - 1}(n) - \left[p_{k}^{2} \le n\right] g(p_{k}) (G_{k - 1}(n / p_{k}) - G_{k - 1}(p_{k - 1}))


Complexity

对于 F_{k}(n) 的计算,其第一种方法的时间复杂度被证明为 O\left(n^{1 - \epsilon}\right) (见 zzt 集训队论文 2.3);
对于第二种方法,其本质即为洲阁筛的第二部分,在洲阁论文中也有提及(6.5.4),其时间复杂度被证明为 O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right)

对于 F_{\mathrm{prime}}(n) 的计算,事实上,其实现与洲阁筛第一部分是相同的。
考虑对于每个 m = n / i ,只有在枚举满足 p_{k}^{2} \le m p_{k} 转移时会对时间复杂度产生贡献,则时间复杂度可估计为:

\begin{aligned} T(n) &= \sum_{i^{2} \le n} O\left(\pi\left(\sqrt{i}\right)\right) + \sum_{i^{2} \le n} O\left(\pi\left(\sqrt{\frac{n}{i}}\right)\right) \\ &= \sum_{i^{2} \le n} O\left(\frac{\sqrt{i}}{\ln{\sqrt{i}}}\right) + \sum_{i^{2} \le n} O\left(\frac{\sqrt{\frac{n}{i}}}{\ln{\sqrt{\frac{n}{i}}}}\right) \\ &= O\left(\int_{1}^{\sqrt{n}} \frac{\sqrt{\frac{n}{x}}}{\log{\sqrt{\frac{n}{x}}}} \mathrm{d} x\right) \\ &= O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right) \end{aligned}

对于空间复杂度,可以发现不论是 F_{k} 还是 F_{\mathrm{prime}} ,其均只在 n / i 处取有效点值,共 O(\sqrt{n}) 个。
则可以使用杜教筛一节中介绍的 trick 来将空间复杂度优化至 O(\sqrt{n})

Implementation

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

对于 F_{\mathrm{prime}}(n) 的计算,直接按递推式实现即可。

对于 p_{k}^{2} \le n ,可以用线性筛预处理出 s_{k} := F_{\mathrm{prime}}(p_{k}) 来替代 F_{k} 递推式中的 F_{\mathrm{prime}}(p_{k - 1})
相应地, G 递推式中的 G_{k - 1}(p_{k - 1}) = \sum_{i = 1}^{k - 1} g(p_{i}) 也可以用此方法预处理。

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

  • 如何快速(一般是线性时间复杂度)筛出前 \sqrt{n} f 值;
  • f(p) 的多项式表示;
  • 如何快速求出 f(p^{c})

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

  1. 筛出 [1, \sqrt{n}] 内的质数与前 \sqrt{n} f 值;
  2. f(p) 多项式表示中的每一项筛出对应的 G ,合并得到 F_{\mathrm{prime}} 的所有 O(\sqrt{n}) 个有用点值;
  3. 按照 F_{k} 的递推式实现递归,求出 F_{1}(n)

Examples

Prefix Sum of Möbius Function

\displaystyle \sum_{i = 1}^{n} \mu(i)

易知 f(p) = -1 。则 g(p) = -1, G_{0}(n) = \sum_{i = 2}^{n} g(i) = -n + 1
直接筛即可得到 F_{\mathrm{prime}} 的所有 O(\sqrt{n}) 个所需点值。

Prefix Sum of Euler's Totient Function

\displaystyle \sum_{i = 1}^{n} \varphi(i)

易知 f(p) = p - 1
对于 f(p) 的一次项 (p) ,有 g(p) = p, G_{0}(n) = \sum_{i = 2}^{n} g(i) = \frac{(n + 2) (n - 1)}{2}
对于 f(p) 的常数项 (-1) ,有 g(p) = -1, G_{0}(n) = \sum_{i = 2}^{n} g(i) = -n + 1
筛两次加起来即可得到 F_{\mathrm{prime}} 的所有 O(\sqrt{n}) 个所需点值。

「LOJ #6053」简单的函数

给定 f(n)

f(n) = \begin{cases} 1 & n = 1 \\ p \operatorname{xor} c & n = p^{c} \\ f(a)f(b) & n = ab \land a \perp b \end{cases}

易知 f(p) = p - 1 + 2[p = 2] 。则按照筛 \varphi 的方法筛,对 2 讨论一下即可。
代码实现