谈谈筛法

一些常见筛法，还有一点新东西。

数论函数可以看做多元的形式幂级数，用 $x_{i}^{e_i}$ 的系数表示 $F\left(\prod_{i=1}^np_i^{e_i}\right)$，比如 $e=[n=1]$ 表示为 $1$，常值函数 $1$ 表示为 $\prod(1+x_i+x_i^2+x_i^3+\cdots)$，莫比乌斯函数 $\mu$ 表示为 $\prod(1-x_i)$。

积性函数的特点是形式幂级数可以表示为若干个一元形式幂级数的乘积，形如 $\prod F_i(x_i)$，而完全积性函数满足 $F_i(x)=\frac 1{1-a_ix}$。

两个函数的狄利克雷卷积可以表示为两个形式幂级数相乘，特别地，积性函数只需要把每个一元形式幂级数对应相乘即可。同时狄利克雷卷积的逆运算（下面称做狄利克雷除法）可以表示为两个形式幂级数相除，因此两个积性函数相除也是积性函数。

设 $D(n)$ 表示 $\{\lfloor\frac ni\rfloor|1\le i\le n\}$。

积性函数前缀和有关问题主要分为两类：都是给定积性函数 $F$，设 $sum_{F}(n)=\sum_{i=1}^nF(i)$，一类是求 $sum_{F}(n)$，另一类需要对所有 $x\in D(n)$，求出 $sum_{F}(x)$。

杜教筛

算法描述

杜教筛可以对满足一定性质的积性函数 $F$ 在所有 $D(n)$ 处求前缀和，复杂度为 $O(n^{\frac 23})$。

找到函数 $G$，设 $H=F\cdot G$，这里是狄利克雷卷积，满足 $G$ 和 $H$ 的前缀和都很好算。那么

$$\begin{aligned} sum_H(n)&=\sum_{i\cdot j\le n}F(i)G(j)\\ &=\sum_{j=1}^nG(j)\cdot sum_F(\lfloor\frac nj\rfloor)\\ &=\sum_{i\in D(n)}sum_F(i)\cdot(sum_G(\lfloor\frac ni\rfloor)-sum_G(\lfloor\frac n{i+1}\rfloor) \end{aligned}$$

把 $sum_F(n)$ 提到左边：

$$sum_F(n)=sum_H(n)-\sum_{i\in D(n)\setminus\{n\}}sum_F(i)\cdot(sum_G(\lfloor\frac ni\rfloor)-sum_G(\lfloor\frac n{i+1}\rfloor)$$

按照上式对 $D(n)$ 中的元素 $x$ 从小到大去计算上式，单次复杂度为 $O(\sqrt x)$，总复杂度表示为

$$\sum_{i=1}^{\sqrt n}\sqrt i+\sum_{i=1}^{\sqrt n}\sqrt{\frac ni}\approx\sum_{i=1}^{\sqrt n}\sqrt{\frac ni}\approx\int_{0}^{\sqrt n}\sqrt{\frac nx}dx=n^{\frac 34}$$

注意到积性函数可以用线性筛来求较小的前缀和，如果对前 $n^{\frac 23}$ 线性筛，那么只需要对 $D(n)$ 中大于 $n^{\frac 23}$ 的元素跑整除分块，复杂度降为 $O(n^{\frac 23})$。

扩展

杜教筛是利用 $G$ 和 $H$ 在 $D(n)$ 处的前缀和计算出 $H/G$ 在 $D(n)$ 处的前缀和，这说明数论函数在 $D(n)$ 处的前缀和在卷积和除法下具有封闭性。

形式化的，设 $S_F(n)$ 表示 $\{sum_F(x)|x\in D(n)\}$。给定 $S_F(n)$ 和 $S_G(n)$，可以求出 $S_{F\cdot G}(n)$ 和 $S_{F/G}(n)$，其中 $S_{F/G}(n)$ 就是杜教筛，$S_{F\cdot G}(n)$ 类似于杜教筛。因此 $S_F(n)$ 构成一个四则运算封闭的域。

计算 $S_{F\cdot G}(n)$ 的朴素的实现是 $O(n^{\frac 34})$ 的，但可以优化，下面给出一个引理：

设 $S_F(n)$ 的差分函数

$$diff(S_F(n))=\begin{cases} sum_F(i)-sum_F(\lfloor\frac n{\lfloor n/i\rfloor+1}\rfloor)&(i\in D(n))\\ 0&(\text{otherwise})\end{cases}$$

那么 $F\cdot G$ 和 $diff(S_F(n))\cdot diff(S_G(n))$ 在 $D(n)$ 处的前缀和相等。

把 $S_{F\cdot G}(n)$ 分成 $[1,\frac{n}{\log^2n}),[\frac{n}{\log^2n},n]$ 两部分，前一部分使用差分加狄利克雷卷积，后一部分整除分块，复杂度 $O(n^{\frac 23}\log^{\frac 13}n$)。

特别地，如果 $F$ 和 $G$ 都是积性函数，那么可以做到 $O(n^{\frac 23})$。如果知道 $F$ 和 $G$ 的定义可以直接线性筛，否则需要更复杂的做法，不过既然知道是积性函数一般也知道定义。

应用

求 $sum_{\mu}(n)$ 和 $sum_{\varphi}(n)$

$\mu=\frac{e}{1},\varphi=\frac{id}{1}$，直接杜教筛。另外 $S_{\mu}(n)$ 和 $S_{\varphi}(n)$ 也可以相互转化。

给定多项式 $A,B$，求 $\sum_{i=1}^n\mu(i)A(i)B(\lfloor\frac ni\rfloor)$。

对每个 $k$ 分别求出 $\mu(i)i^k$ 在 $D(n)$ 处的前缀和，再枚举 $\lfloor\frac ni\rfloor$ 统计答案。

其中 $\mu(i)i^k$ 的狄利克雷卷积逆元是 $F(i)=i^k$，$F(i)$ 的前缀和可以快速求。

除数函数 $\sigma_k(n)$ 表示 $n$ 所有因数的 $k$ 次方之和，对 $x\in D(n)$ 求出 $sum_{\sigma_k}(n)$。

函数 $F(i)=i^k$ 与 $1$ 的狄利克雷卷积，扩展中介绍的方法。

有一个变量 $x$ 初始为 $1$，每次随机一个整数 $k\in [2,m]$，然后令 $x=x\cdot k$，求 $x>n$ 的期望步数。

设 $F(i)$ 表示到达 $x=i$ 这个状态的概率，那么答案为 $sum_F(n)$。

设 $G(i)=\begin{cases}\frac 1{m-1}&(i\in[2,m])\\0&(\text{otherwise})\end{cases}$，那么 $F=e+G+G^2+G^3+\cdots=\frac{1}{e-G}$。

因为 $e-G$ 的前缀和是好求的，但 $F$ 并不是积性函数，所以只能用 $O(n^{\frac 23}\log^{\frac 13}n)$ 的算法。

杜教筛并不要求函数是积性的，只要能通过简单函数四则运算得到就可以求。

对于满足 $F(1)=1$ 的数论函数 $F$，定义 $\sqrt F$ 为一个函数 $G$ 满足 $G\cdot G=F$，且 $G(1)=1$，可以说明 $G$ 是唯一的，给定 $F$ 在 $D(n)$ 处的前缀和 $S_F(n)$，求 $S_G(n)$。

设 $H=G-e$，那么 $H^2+2H+e=F\Rightarrow H=\frac 12(F-e)-\frac 12 H^2$。

可以发现 $H$ 是自己卷自己的形式，扩展中介绍的算法是在线的，因此 $S_H(n)$ 可以从小大逐项计算，复杂度 $O(n^{\frac 23}\log^{\frac 13}n)$。

杜教筛还可以解数论函数的代数方程。

Powerful Number 筛

算法描述

Powerful Number 筛可以对满足一定性质的积性函数 $F$ 算一次前缀和，复杂度为 $O(\sqrt n)$。

Powerful Number 定义：所有质因子的指数都大于 $1$ 的数叫 Powerful Number。

引理：$n$ 以内的 Powerful Number 的数量为 $O(\sqrt n)$ 级别。

证明：Powerful Number 可以表示为 $a^2b^3$，枚举 $a$，可以算出数量的上界：

$$\sum_{i=1}^{\sqrt n}\sqrt[3] {\frac n{a^2}} < \int_0^{\sqrt n}\sqrt[3] {\frac n{a^2}}da=3\sqrt n$$

找到一个积性函数 $G$ 满足 $G(x)=F(x) (x \in Prime)$，设 $H=F/G$，即狄利克雷除法，可知 $H(x)$ 仅在 Powerful Number 和 $1$ 处取值不为 $0$（形式幂级数上一次项都为 $0$）。

首先预处理出 $H(x)$ 在 $p^k(p \in Prime,k > 1)$ 处的取值，这里可以做到 $O(\sqrt N)$（无论 $O(1)$ 算 $H(p^k)$ 还是 $O(k)$ 算都是这个复杂度）。然后通过 dfs 各个质因子的指数可以遍历 Powerful Number，同时也可以算出它们在 $H$ 上的取值。

于是

$$sum_F(i)=\sum_{ab \le n}G(a)H(b)=\sum_{b=1}^nH(b)sum_G(\lfloor \frac nb \rfloor)$$

最后要求 $G$ 的前缀和好求或者在 $D(n)$ 处的前缀和能快速求。

扩展

称一个只在 Powerful Number 和 $1$ 处取值不为 $0$ 积性函数 $H$ 为稀疏函数。

上述筛法是把 $F$ 拆成 $G$ 和一个稀疏函数 $H$ 的狄利克雷卷积，然后考虑 $H$ 中非 $0$ 项对答案的贡献。

稀疏函数 $H$ 有一个性质是 $S_H(n)$ 由 $O(\sqrt[3]n)$ 个值相等的连续段构成，证明考虑把 $D(n)$ 拆成两段 $[1,n^{\frac 23}), [n^{\frac 23}, n]$，前一段中只有 $O(\sqrt[3]n)$ 个 Powerful Number，因此前缀和只有 $O(\sqrt[3]n)$ 种，后一段中只有 $O(\sqrt[3]n)$ 个元素。

通过这个性质，对 Powerful Number 排序并处理前缀和，可以 $O(\sqrt[3]n)$（可能要带 $\log$）查询 $sum_F(n)$，从而降低多测的复杂度。

另外，可以以低于杜教筛的复杂度求出 $F$ 在所有 $D(n)$ 处的前缀和，对前 $n^{\frac 35}$ 线性筛，$>n^{\frac 35}$ 的部分用立方根整除分块即可做到 $O(n^{\frac 35})$ 的总复杂度。

进一步，对于积性函数 $F$ 和稀疏函数 $G$，给定 $S_F(n)$ 和 $S_G(n)$，可以 $O(n^{\frac 35})$ 的复杂度计算 $S_{F\cdot G}(n)$ 和 $S_{F/G}(n)$，由于 $O(n^{\frac 35})$ 比任何通用筛法复杂度要低，因此积性函数的前缀和和完全积性函数的前缀和应该是等难的。

应用

定义函数 $F(x)$ 表示最大的 $b$ 使得 $x=ab^2$，求 $sum_F(n)(n\le 10^{15})$，$2000$ 组询问。

$F$ 在质数处的取值为 $1$，所以 $F$ 可以表示 $1$ 和一个稀疏函数的狄利克雷卷积，特别地，这个稀疏函数只在完全平方数处有值，每次询问使用立方根整除分块。

定义积性函数 $F(x)$ 满足 $F(p^c)=p\oplus c$，求 $F$ 在所有 $D(n)$ 处的前缀和。

注意到 $F$ 和 $\varphi$ 在奇质数处的取值相同，但 $2$ 处不同，令 $F=\varphi\cdot G$，$G$ 只在 Powerful Number 和 $2^k$ 的乘积还有 $1$ 处取值非 $0$，这个数量是 $O(\sqrt n+\sqrt\frac n2+\sqrt\frac n4+\cdots)=O(\sqrt n)$，所以仍然可以将 $G$ 视作稀疏函数，先用杜教筛求出 $S_{\varphi}(n)$，然后可以 $O(n^{\frac 35})$ 乘上 $S_G(n)$。

扩展埃氏筛（min_25 筛，洲阁筛）

算法描述

这两种筛法可以对 $p^c$ 处定义简单的的积性函数求前缀和，min_25 筛复杂度为 $O(n^{1-\epsilon})$ 但可以跑 $10^{12}$，洲阁筛为 $O(n^{\frac 34}\cdot\log^{-1}n)$，并且洲阁筛可以计算出在所有 $D(n)$ 处的前缀和。

两种筛法的第一部分都是求出 $F$ 在质数处的取值。

首先找若干个完全积性函数 $H_i$ 使得 $F(x)=\sum k_iH_i(x) (x \in Prime)$，对每个完全积性函数 $H_i$ 分别算出在质数处的取值，现在考虑只有一个 $H$ 的情况。

考虑埃氏筛，从小到大枚举每一个质数，把以这个质数为最小质因子的合数筛掉。

$p_i$ 表示第 $i$ 个质数，$d_i$ 表示 $i$ 的最小质因子。

设 $g(n, i) = \sum_{j=2}^n [j \in P \lor d_j > p_i]H(j)$，转移为

$$g(n, i) = g(n, i - 1) - H(p_i)\left(g(\big\lfloor\frac n {p_i}\big\rfloor, i - 1) - \sum_{j=1}^{i-1}H(p_j)\right)$$

减后面那项是因为 $p_ip_j(j < i)$ 的最小质因子不是 $p_i$。

当 $n < p_i^2$ 时，$g(n,i)=g(n,i-1)$，即不需要转移，这是复杂度的关键。

初始化 $g(n, 0) = \sum\limits_{i=2}^n H(i)$，注意 $1$ 不算。

复杂度为 $O(n^{\frac 34}\cdot\log^{-1}n)$，分析较为复杂。

min_25 筛的第二部分为一个复杂度为 $O(n^{1-\epsilon})$ 的搜索，从小到大枚举每个质因子的指数，如果后面只剩一个质因子且指数为 $1$，那么就使用前面计算的 $g$ 数组，只递归考虑剩下质因子的指数和大于 $1$ 的情况。

$$\begin{aligned} S(n, i)=&\sum_{j = 2}^n [d_j > p_i]f(j)\\ =&\sum\limits_{j = i+1}^{p_j \le n} f(p_j) + \sum\limits_{j = i+1}^{p_j^2 \le n}\sum\limits_{k=1}^{p_j^k \le n} f(p_j^k)(S(\big\lfloor \dfrac n{p_j^k} \big\rfloor, j) + [k>1]) \end{aligned}$$

答案是 $S(N, 0)+1$。

洲阁筛的第二部分复杂度是 $O(n^{\frac 34}\cdot\log^{-1}n)$，它相当于第一部分的逆过程，倒着把第一部分筛掉的合数加回去，但由于 $F$ 不是完全积性函数，要复杂一点。

设 $g(n, i) = \sum_{j=2}^n [j \in P \lor d_j > p_i]F(j)$，转移为

$$g(n, i - 1) = g(n, i)+\sum_{k\ge 1}F(p_i^k)\left(g(\big\lfloor\frac n {p_i^k}\big\rfloor, i - 1) - \sum_{j=1}^{i-1}F(p_j)\right)$$

和第一部分相比有几倍的常数，但复杂度不变。另外，Powerful Number 筛可以把积性函数的问题转化为完全积性函数的问题，提高这部分的速度。

扩展

另外，洲阁筛计算得到的信息天然就是按最小质因子分类的，而 min_25 筛在搜索中也容易记录最小质因子。

应用

求 $[1,n]$ 中的质数个数。

相当于求 $1$ 函数在质数处的取值之和，对应两种筛法的第一部分，复杂度 $O(n^{\frac 34}\cdot\log^{-1}n)$。

定义积性函数 $F(x)$ 满足 $F(p^c)=p\oplus c$，求 $F$ 在所有 $D(n)$ 处的前缀和。

$F(p)=p-1+2[n=2]$，先计算质数数量和质数和，再加上 $n=2$ 的贡献就可以得到 $F$ 在质数处的取值，然后再使用洲阁筛的第二部分，min_25 筛不太行。

继续考虑上面的积性函数 $F$，再给定多项式 $A$，求 $\sum_{i=1}^nF(i)B(d_i)$，其中 $d_i$ 表示 $i$ 的最小质因子。

考虑分开计算质数和合数的贡献，质数的贡献就是 $F(i)B(i)$ 在质数处的取值和，可以用第一部分计算。对于合数，我们把它们按最小质因子分类，对每一类算出 $F$ 函数之和，这可以在洲阁筛第二部分过程中统计，再乘上 $B(d_i)$。

比较

• 三种筛法通过改进都可以解决积性函数在所有 $D(n)$ 处的前缀和。

• 速度从高到低依次为：Powerful Number 筛，扩展埃氏筛，杜教筛。

• 在实现难度上，Powerful Number 筛和杜教筛比较容易，两种扩展埃氏筛要麻烦一点。

• 在多次询问时，Powerful Number 筛可以优化到 $O(\sqrt[3]n)$，杜教筛可以通过调整阈值来提高速度，扩展埃氏筛不行。

• 在适用范围上，扩展埃氏筛在积性函数上通用，应该是完全覆盖 Powerful Number 筛的，杜教筛可以计算一些非积性函数的前缀和。

对于一个积性函数求和问题，个人认为应该首选原生的 Powerful Number 筛，再考虑杜教筛，最后考虑两种扩展埃氏筛。

参考资料

• 杜教筛(+贝尔级数+powerful number)
• https://www.luogu.com.cn/blog/command-block/new-sieve
• ZZT 筛
• ZKY 筛