【学习笔记】数论之筛法

前言：

可以会乱记一些技巧吧。

交换求和顺序

如果不确定可以将条件写成 [A] 的形式，交换完求和顺序再把这个条件放里面。
例如：

\[\sum_{i=1}^n \sum_{d} [d | i] = \sum_{d=1}^n \sum_{i} [d|i] = \sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} 1\]

狄利克雷前缀和与狄利克雷差分

设两个数论函数满足 \(f * I = g\)
狄利克雷前缀和是指给定 \(f\) 求 \(g\)
狄利克雷差分就是倒过来，也就是给定 \(g\) 求 \(f\)，乘 \(\mu\) 就好。

狄利克雷前缀和就是知道恰好为 \(x\) 的信息，要求为 \(x\) 的倍数的信息。
狄利克雷差分就是知道为 \(x\) 的倍数的信息，要求恰好为 \(x\) 的信息。

埃氏筛：

基础知识

埃氏筛的代码实现如下：

\([1,n]\) 中的质数个数为 \(\frac{n}{\log n}\)，所以第 \(i\) 个质数为 \(O(i \log i)\)。
所以埃氏筛的时间复杂度为 \(O(n \log \log n)\)

线性筛：

基础知识

线性筛的代码实现如下：

线性筛中内层循环相当于枚举最小质因子，如果满足 \(i \mod \text{prime}_{j} = 0\) 也就是意味着此时 \(i \times \text{prime}_k（k > j）\) 的最小质因子不是 \(\text{prime}_k\)，而至少应为 \(\text{prime}_j\) 所以可以直接跳过

所以每个数只会被其最小质因子筛一次，复杂度 \(O(n)\)。

常见积性函数筛法

线性筛的强大作用之一就是筛积性函数。

\(id_k(i)\)：

• 可以对于 \(id_k(p) (p \in \text{prime})\) 快速幂求，然后线性筛的过程中直接乘就是答案（注意到 \(id_k\) 是一个完全积性函数）

\(\varphi(i)\)：

• 若 \(i \mod p \not= 0\)，则 \(\varphi(i \times p) = \varphi(i) \times (p-1)\)
• 若 \(i \mod p = 0\)，则 \(\varphi(i \times p) = \varphi(i) \times p\)

\(\mu(i)\)：

• 若 \(i \mod p \not= 0\)，\(\mu(i\times p) = -\mu(i)\)
• 若 \(i \mod p = 0\)，\(\mu(i \times p) = 0\)

一般积性函数筛法

若对于积性函数 \(f\) 可以以 \(O(n)\) 的复杂度求出所有的 \(f(p^c) (p\in \text{prime})\)，那么就可以很快求解。

根据线性筛我们可以求出 \(mn_i\) 表示数 \(i\) 的最小质因子，求 \(pw_i\) 代表对 \(i\) 质因数分解之后 \(mn_i\) 对应的系数，则可以直接得到：\(f(i) = f(pw_i)f(\frac{i}{pw_i})\)

就以下面这个为例推一推：

\(f(x) = x\mu(x)\)，要求筛 \(g = f * I * id_2\)。

积性函数卷积性函数还是积性函数，所以 \(g\) 是积性函数。

因为 \(\mu * I = e\)，所以考虑先计算 \(f * I\)：

\[(f*I)(p^c) = \sum_{i=0}^c p^i \mu(p^i) = \begin{cases}1 & c = 0 \\(1-p) & c > 0\end{cases}\]

注意因为我们只在意 \(p^c\) 所以枚举因数就相当于枚举 \(p\) 的指数。
所以：

\[\begin{aligned}g(p^c) &= \sum_{i=0}^c (f*i)(p^i) \times id_2(p^{c-i}) \\&= 1 \times p^{2c} + \sum_{i=1}^c (1-p) p^{2(c-i)} \\&= \sum_{i=0}^c p^{2i} - p\sum_{i=0}^{c-1} p^{2i} \\&= \dfrac{(1-p^{2(c+1)}) - p(1-p^{2c})}{1-p^{2}}\end{aligned} \]

所以知道了这个就很简单了。

杜教筛

基础知识

杜教筛的作用就是求数论函数 \(f\) 的前缀和。

杜教筛首先需要我们构造一个数论函数 \(g\)，满足 \(f * g = h\)，通常情况下使用杜教筛的条件是 \(g,h\) 的前缀和很好求。

为了方便下面设 \(S(f,n)\) 表示数论函数 \(f\) 的前 \(n\) 项和。

\[\begin{aligned}S(h,n) &= \sum_{i=1}^n \sum_{d | i}g(d)f(\frac{i}{d}) \\&= \sum_{d=1}^n g(d) \sum_{i=1}^{\lfloor \frac{n}{d}\rfloor} f(i) \\&= \sum_{d=1}^n g(d) S(f,\lfloor \frac{n}{d} \rfloor)\end{aligned}\]

因为我们要求的是 \(S(f,n)\) 所以就考虑把这一项单独提出来：

\[\begin{aligned}g(1)S(f,n) &= S(h,n) - \sum_{d=2}^n g(d)S(f,\lfloor \frac{n}{d} \rfloor) \\S(f,n) &= \dfrac{S(h,n) - \sum_{d=2}^n g(d)S(f,\lfloor \frac{n}{d} \rfloor)}{g(1)}\end{aligned}\]

对于后面显然需要整除分块求解，所以必须要快速求 \(\sum_{d=l}^r g(d)\)。
经过复杂度分析可以知道，当我们线性预处理出 \(S(f,n)\) 的前 \(O(n^{\frac{2}{3}})\) 项，我们的总时间复杂度就是 \(O(n^{\frac{2}{3}})\)

下面就是一个模板代码实现：

简单应用：

如果 \(f * g = h\) 中两个可以杜教筛一个可以线性筛，则三个都可以杜教筛。

数论函数点乘：\(f \cdot g \Longleftrightarrow (f \cdot g)(n) = f(n)g(n)\)。
若有完全积性函数 \(c\) 有：\((a\cdot c) * (b \cdot c) \Longleftrightarrow (a * b) \cdot c\)

例题一：对 \(f = \mu\) 做杜教筛
解法：取 \(g = I\)，则 \(f * g = e\)

例题二：对 \(f = \varphi\) 做杜教筛
解法：取 \(g = I\)，则 \(f * g = id\)

例题三：对 \(f = id_k \cdot \varphi\) 做杜教筛（注意这里是点乘）
解法：取 \(g = id_k\)，则 \(f * g = (\varphi \cdot id_k) * (I \cdot id_k) = (\varphi * I) \cdot id_k = id \cdot id_k = id_{k+1}\)

例题四：对 \(f = id_k · \mu\) 做杜教筛（注意这里是点乘）
解法：取 \(g = id_k\)，则 \(f * g = e \cdot id_k = e\)

例题五：对 \(f = \mu^2 * (\mu \cdot id)\) 做杜教筛
解法：取 \(g = id\)，则 \(f * g = \mu^2 ((\mu * I) \cdot id) = \mu^2 * e = \mu^2\)，\(\mu^2(i) = \sum_{d^2 | i} \mu(d)\)，所以其前缀和也是好求的

有了上面这些知识你就可以通过 P4213 【模板】杜教筛（Sum） 了。
代码如下：

贝尔级数

基础知识：

如果你看了上文中线性筛-一般积性函数筛法那一道例题，你就会惊奇的发现，当我们只关系 \(f(p^c)\) 的值时，狄利克雷卷积就是相当于加法卷积。于是就有贝尔级数：

\[f_{p}(x) = \sum_{i=0}^{\infty} f(p^i) x^i\]

如果你对生成函数有所了解会发现这东西就跟 OGF 一样，但是你如果没学也不要紧，下文会将你当作没学来看待。

因为相当于加法卷积，所以也就有：

\[f * g = h \Longleftrightarrow \forall p,f_p(x) * g_{p}(x) = h_p(x)\]

（第一个 \(*\) 代表狄利克雷卷积，第二个 \(*\) 代表加法卷积）
下面就列几个贝尔级数：

\[\begin{aligned}e_p(x) &= 1 \\I_p(x) &= \sum_{i=0}^{\infty} x^i = \frac{1}{1-x} \\(id_k)_p(x) &= \sum_{i=0}^{\infty} p^{ik} x^i = \frac{1}{1-p^kx} \\u_p(x) &= (I^{-1})_p(x) = 1-x \\u_p^2(x) & = 1 + x \\d_p(x) &= \sum_{i=0}^{\infty} (i+1)x^i = \frac{1}{(1-x)^2} \\(\sigma_k)_p(x) &= (I * id_k)_p(x) = \dfrac{1}{(1-x)(1-p^kx)} \\\varphi_p(x) &= (\mu * id)_p(x) = \dfrac{1-x}{1-px} \\\end{aligned}\]

对于 \(u_p(x),u^2_p(x)\) 也可以直接枚举只有前两项有值，也可以得到同样的结论

对于 \(d_p(x)\) 可以考虑组合意义，也就是两个物品每个物品可以选无限多次，询问选 \(i\) 个的方案就是 \(i+1\)，或者可以理解为 \(d_p(x) = I_p(x) \cdot I_p(x)\)

关于 \(id_k\) 在点乘中对贝尔级数的影响有如下结论：

\[(f \cdot id_k)_p(x) = f_p(p^kx)\]

也就是说可以直接将 \(p^kx\) 视为一个整体。
证明的话就是暴力展开：

\[(f \cdot id_k)_p(x) = \sum_{i=0}^{\infty} f(p^i) p^{ik} x^i = f_p(p^kx)\]

上述结论的简单应用就是：

• \(\mu \cdot id_k = 1 - p^kx\)
• \(\varphi \cdot id_k = \frac{1-p^kx}{1-p^{k+1}x}\)

简单应用：

例题一：对 \(f(p^k) = p^k + [k > 0](-1)^k\) 且已知 \(f\) 为积性函数，做杜教筛
解法：
考虑先求出 \(f\) 的贝尔级数：

\[f_p(x) = 1 + \sum_{i=1}^{\infty} (p^i + (-1)^i)x^i = 1 + \dfrac{1}{1-px} + \dfrac{1}{1+x}\]

考虑构造卷积 \(g_p(x) = (1-px)(1+x)\)，则 \((f*g)_p(x) = 1+px^2\)
分别考虑这两个的前缀和是不是很好做。
先考虑 \(g\)，\((1-px) = \mu · id,(1+x) = \mu^2\)，所以 \(g = \mu^2 * (\mu \cdot id)\)，这个就是我们杜教筛的例题五。
而 \(h_p(x) = 1 + px^2\)，以实际意义就是 \(h(n)\) 非 \(0\) 的 \(n\) 都满足质因子指数为 \(2\)，所以就直接枚举就好了：

\[S(h,n) = \sum_{i=1}^{\sqrt{n}} i \mu^2(i)\]

上面的式子其实是将合法的数直接开方做的一个映射。

Powerful Number

基础知识：

对于正整数 \(n\)，设其质因数分解的结果为 \(n = \prod_{i} p_i^{a_i}\)，满足 \(\forall i,a_i > 1\) 则称 \(n\) 为一个 Powerful Number，其实就是满足其所有质因子的指数大于等于 \(2\)。
其有如下的两个性质：

• 任意一个 Powerful Number 都可以表示为 \(a^2b^3\) 的形式
• 小于等于 \(n\) 的 Powerful Number 只有 \(O(\sqrt{n})\) 个

证明显然。

我们就有 PN 筛就是使用了 Powerful Number 的性质。

PN 筛也是求解一个积性函数的前缀和。

首先要构造一个易求出前缀和的积性函数 \(g\)，满足对于所有的质数 \(p\) 都有 \(g(p) = f(p)\)。

设 \(h = f / g\)，也就是 \(f = g * h\)，易得 \(h\) 也是一个积性函数，即 \(h(1) = 1\)。

考虑对于一个质数 \(p\)，\(f(p) = g(1)h(p) + g(p)h(1) = h(p) + g(p)\)，因为 \(f(p) = g(p)\) 所以 \(h(p) = 0\)，也就是 \(h\) 在所有的质数位置的值 \(0\)，因为 \(h\) 也是一个积性函数，易得 \(h\) 只有在 Powerful Number 位置值不为 \(0\)。

根据 \(f = g * h\) 推式子：

\[\begin{aligned}S(f,n) &= \sum_{i=1}^n f(i) \\&= \sum_{i=1}^n \sum_{d | i} h(d)g(\frac{i}{d}) \\&= \sum_{d=1}^n h(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} g(i)\\&= \sum_{d=1}^nh(d)S(g,\lfloor \frac{n}{d} \rfloor)\end{aligned}\]

可以直接 \(O(\sqrt{n})\) 找出所有的 Powerful Number 然后算出所有 \(h(p^c)\) 处的值就可以根据积性函数求出 \(h\) 的所有有效值，对于所有的有效值对答案累加上 \(h(d)S(g,\lfloor \frac{n}{d} \rfloor)\) 即可。

下面第一个就是究竟该怎么样才能找到 Powerful Number，就是直接枚举 \(p^c(c > 1,p\le \sqrt{n})\)，然后搜索即可。

然后就是如何求出 \(h(p^c)\) 位置的值，因为 \(f = g * h\)，所以 \(f(p^c) = \sum_{d=0}^c h(p^d)g(p^{c-d})\)，移项得：\(h(p^c) = f(p^c) - \sum_{d=1}^c h(p^d)g(p^{c-d})\)

简单应用：

例题一：P5325 【模板】Min_25筛
解法：考虑 \(f(x) = x(x-1)\) 构造 \(g(x) = x\varphi(x)\)，然后剩下的就按照上文的套路推就好了。

Min_25 筛

基础知识

Min_25 筛可以做到以亚线性得复杂度求解积性函数的前缀和。
其要求为：\(f(p)\) 为低阶多项式，\(f(p^c)\) 可以快速计算。
其基本思想就是用埃氏筛的想法，将问题拆分成与质因子相关的子问题。

为了下文推导方便，我们有如下规定：
\(\text{prime}_i\) 表示第 \(i\) 个质数的值
\(|\text{prime}_n|\) 表示 \([1,n]\) 中质数的个数
\(mn_i\) 代表 \(i\) 的最小质因子

我们要求的就是 \(f\) 的前缀和，考虑构造 \(g(n,i)\) 表示在埃氏筛中小于等于 \(n\) 的数里，前 \(k\) 个质数筛完后剩下数的 \(f\) 之和。也就是所有的质数的 \(f\) 和所有最小质因子大于 \(\text{prime}_k\) 的合数的 \(f\) 之和。

其实也就是说：

\[g(n,i) = \sum_{j \in \text{prime} \vee mn_j > i} f(j)\]

可以显然发现 \(g(n,|\text{prime}_n|)\) 代表 \([1,n]\) 所有质数的 \(f\) 之和，\(g(\text{prime}_k,k)\) 代表前 \(k\) 个质数的 \(f\) 之和。

会发现 \(g(n,i)\) 满足如下的递推式：

\[g(n,i) = \begin{cases}g(n,i-1) & \text{prime}_i^2 > n \\g(n,i-1) - f(\text{prime}_i) \times (g(\lfloor \frac{n}{\text{prime}_i}\rfloor,i-1) - g(\text{prime}_{i-1},i-1)) & \text{prime}_i^2 \le n\end{cases}\]

第一个转移很好理解，因为此时 \(\text{prime}_i\) 不会筛掉任何一个数

第二个转移就有点神仙了，考虑 \(mn_x = \text{prime}_i\) 相当于将数除去 \(\text{prime}_i\) 后，其最小质因子大于 \(\text{prime}_{i-1}\)，其实就是对应着 \(g(\lfloor \frac{n}{\text{prime}_i}\rfloor,i-1)\)，可是此时我们也会将 \(\sum_{j=1}^{i-1} f(\text{prime}_j)\) 的贡献删掉，但是根据定义我们不应该删掉，所以最后就用 \(g(\text{prime}_{i-1},i-1)\) 将这一部分贡献补回来。

但是我们会发现能把 \(f\) 提出来的条件就是 \(f\) 是一个完全积性函数，但是它不是，那么该怎么办呢。

所以我们就想办法构造一个完全积性函数啦，因为我们的 \(f\) 一般都是多项式的形式，而幂是一个完全积性函数，所以可以考虑对于 \(f\) 的每一项分别通过 \(g\) 递推然后加和即可。

考虑我们需要对于 \(p \in [1,n]\) 都求出 \(g(p,i)\) 嘛，其实没有必要，因为我们递归下去的形式为 \(\lfloor \frac{n}{x} \rfloor\)，这其实就是数论分块的形式，所以其实只用 \(O(\sqrt{n})\) 种不同的位置需要求，然后在这个上面滚动就好了。

现在处理完了 \(g(n,i)\) 考虑一个新的式子，设 \(S(n,i)\) 表示小于等于 \(n\) 的数里，最小质因子大于 \(\text{prime}_i\) 的数的 \(f\) 值的和。

那么我们的答案就可以表示为：\(S(n,0) + f(1)\)。

那么 \(S(n,i)\) 就满足如下的式子：

\[S(n,i) = g(n,|\text{prime}|) - g(|\text{prime}_i|,|\text{prime}|) + \sum_{j > i}\sum_{p_j^k \le n} f(p_j^k) S(\lfloor \frac{n}{p_j^k} \rfloor,j + [k > 1])\]

其实就是分为两部分计算贡献。

第一部分为：大于 \(\text{prime}_i\) 的质数
这一部分的贡献就直接通过得到的 \(g\) 就可以快速取得

第二部分为：最小质因子大于 \(\text{prime}_i\) 的质数，可以考虑直接枚举最小质因子以及其指数，然后就可以直接递归求解。

根据某个神仙的定理，即使我们在递归过程中不记忆化复杂度依旧正确。