数论函数求和
TallBanana
·
·
算法·理论
- 约定单独的一个 p 表示素数。
- 约定 p_i 表示第 i 个素数，p_0=0。
- 约定 S_F(n)=\sum_{i=1}^n F(i)。
- 约定 minp_i 为 i 的最小的质因子。
- 约定 \mathbb{P} 表示素数集合。
杜教筛
- 基本和组：定义 S=\{ \left\lfloor n/x \right\rfloor \} 包含的位置的值为在 n 下的基本和组，即我们在整除分块时候需要用到的值。
- 整除定理：\left\lfloor \left\lfloor n/a \right\rfloor /b \right\rfloor=\left\lfloor n/ab \right\rfloor，即整除操作对于 S 是封闭的。
乘积式：给定数论函数 A,B 以及两者在 n 下的基本和组，对于 C=A*B，求 C 在 n 下的基本和组。
如果我们使用整除分块对于每个 $\left\lfloor n/i \right\rfloor$ 计算，复杂度是 $O(n^{3/4})$ 的。
如果我们可以预处理 $C$ 的 $\le T$ 部分的前缀和，那么我们只需要对于 $n/i> T$ 的部分进行整除分块，复杂度为 $O(T+nT^{-1/2})$，$T=n^{2/3}$ 时复杂度取得最小值，为 $O(n^{2/3})$。
**除式**：给定数论函数 $A,B$ 以及两者在 $n$ 下的基本和组，对于 $A=B*C$，求 $C$ 在 $n$ 下的基本和组。
$S_A(n)=\sum_{i=1}^n B(i)S_C(\left\lfloor n/i \right\rfloor)=S_C(n)+\sum_{i=2}^n B(i)S_C(\left\lfloor n/i \right\rfloor) \Leftrightarrow S_C(n)=S_A(n)-\sum_{i=2}^n B(i)S_C(\left\lfloor n/i \right\rfloor)$，也是可以整除分块的形式，需要递归计算，复杂度也是 $O(n^{2/3})$。
**迪利克雷双曲线法**：可以认为是杜教筛的另外一种形式。
求 $S_C(n)$ 相当于在求这个反比例函数下的 $A,B$ 的乘积。于是可以拆成绿色加蓝色部分，减去重复的部分。
$S_C(n)=\sum_{i=1}^{\left\lfloor \sqrt n \right\rfloor} A(i)S_B(\left\lfloor n/i \right\rfloor)+\sum_{i=1}^{\left\lfloor \sqrt n \right\rfloor} B(i)S_A(\left\lfloor n/i \right\rfloor)-S_A(\left\lfloor \sqrt n \right\rfloor)S_B(\left\lfloor \sqrt n \right\rfloor)
容易 O(\sqrt n) 计算，这在速度和实现上优于经典的杜教筛，对称性也比较明显。
除式与乘积式大同小异，此处不提。
- 一些常见数论函数的筛法：\
$\varphi=id/I$\
$\sigma_k=I*id_k
其中 id_k 可以使用拉格朗日插值快速求出基本和组。
- 当 C 是完全积性函数时，有 (A\cdot C)*(B\cdot C)=(A*B)\cdot C。\
利用该定理，可以构造一些关于点乘的数论函数的筛法。
-
\mu\cdot id_k$：$(\mu\cdot id_k) * id_k=(\mu\cdot id_k)*(I\cdot id_k)=\epsilon
-
\varphi\cdot id_k$：$(\varphi\cdot id_k)* id_k=(\varphi\cdot id_k)*(I\cdot id_k)=id_{k+1}
贝尔级数
- 对于积性函数 f，定义其在 p 意义下的贝尔级数为 \mathcal{F}_p(x)=\sum_{i=0}^\infty f(p^i)x^i。\
相当于我们利用积性，把乘法卷积转化为幂级数的加法卷积。
常见的贝尔级数：
-
\epsilon$：$1
-
I$：$\frac{1}{1-x}
-
id_k$：$\frac{1}{1-p^kx}
-
-
\mu^2$：$1+x
-
-
-
-
引理：点积 id_k 相当于把 x 带换成 p^kx。
-
\mu\cdot id_k$：$1-p^kx
-
\varphi\cdot id_k$：$\frac{1-p^kx}{1-p^{k+1}x}
- 对于完全积性函数 f：\frac{1}{1-f(p)x}。
- 例如刘维尔函数 \lambda(n)=(-1)^{n的质因子次数和}，是完全积性函数，贝尔级数：\frac{1}{1+x}，可得 \lambda*\mu^2=\epsilon。
贝尔级数好处是，我们可以更容易看出函数之间的卷积关系。
素数前缀统计
模板
问题引入：我们想要求 \sum_{i=1}^n [i\text{ is a prime}]F(i)，其中 F 是完全积性函数。
我们可以借鉴埃氏筛的思路，每次把 p_i 的倍数筛掉。
- 引理：合数 m 必然有一个 \sqrt m 以内的因子。
于是我们可以只用 \sqrt n 以内的素数筛出答案。
设 h(n,k)=\sum_{i=1}^n [i\text{ is a prime or }minp_i>p_k]F(i)，意义是我们埃氏筛筛了 p_{1\sim k} 的素数后剩下的数的贡献。
根据埃氏筛，有递推式
h(n,k)=h(n,k-1)-F(p_k)\begin{cases} h(\left\lfloor n/p_k \right\rfloor,k-1)-h(p_k-1,k-1) & p_k\le \sqrt n\\ 0 & p_k>\sqrt n \end{cases}
考虑这个递推式的意义，我们从 h(n,k-1) 继承过来，然后筛掉 p_k 的倍数的贡献。h(n,k-1) 还剩余的 p_k 的倍数应当满足 minp=p_k，于是我们可以先把这些应当筛掉的数先除以 p_k，然后就是 minp\ge p_k，于是就是 h(\left\lfloor n/p_k \right\rfloor,k-1) 减去 <p_k 的素数。
发现我们只会用到形如 h(\left\lfloor n/x \right\rfloor,k) 的取值，于是我们可以只记录 i\le \sqrt n 的 i 和 \left\lfloor n/i \right\rfloor 处的值。
边界是 $h(n,0)=\sum_{i=2}^n F(i)$，注意**不包括 1**。
* 暴力做这个递推式，显然是 $O(\frac{n}{\log n})$ 的，太慢了。
* 发现有的值在转移的过程中只会 $+0$，那么我们只维护加非 0 值的那些位置，于是复杂度通过积分可得是 $O(\frac{n^{3/4}}{\log n})$。
* 更优的做法我不会，也没必要学。
## Min_25 筛
问题引入：如果我们有积性函数 $F$，现在想要求 $S_F(n)$。
我们可以类似 素数前缀统计，设计一个 dp 来求这个东西。
令**完全**积性函数 $G(p)=F(p)$，即**素数拟合**。
使用素数前缀统计的方法，求出筛 $G$ 的 $h$ 数组。
令 $s(n,k)=\sum_{i=1}^n [minp_i> p_k]F(i)$，转移考虑分成素数和合数。
素数处 $G$ 与 $F$ 相同，于是是 $h(n,|\mathbb{P}|)$ 减去前 $k$ 个素数。
合数处我们就是加入 $minp=p_k$ 的数的贡献。
$$s(n,k)=h(n,|\mathbb{P}|)-h(p_k,|\mathbb{P}|)+\sum_{j>k}\sum_{i=1}^{{p_j}^i\le n}F({p_j}^i)(s(\left\lfloor n/{p_j}^i \right\rfloor,j)+[i>1])$$
解释 $+[i>1]$ 是为什么：因为 $s$ 中不包括 $F(1)$，而 $i=1$ 的时候就不能算 $F(p_j)$ 到合数中。
最终答案是 $s(n,0)+1$，因为 $F(1)$ 不会被算到。
如果只需要单点求值，不需要记忆化，暴力搜索即可。复杂度是 $O(\frac{n^{3/4}}{\log n})$。
如果我们需要求整个基本合组，我们也可以做到 $O(\frac{n^{3/4}}{\log n})$，具体可以对于一些更新比较小的位置打上懒标记。
## Powerful Number
定义 $\mathsf{powerful\ number}$ 为没有 $1$ 次质因子的数，简称 $\mathrm{PN}$。
* $n$ 以内的 $\mathrm{PN}$ 只有 $O(\sqrt n)$ 个。\
证明：显然 $\mathrm{PN}$ 可以表示成 $a^2b^3$ 的形式，简单积分得到 $O(\sqrt n)$。
**拟合法**：如果我们有积性函数 $f,g$ 满足 $f(p)=g(p)$，即他们**素数拟合**。已知 $g$ 的基本和组，求 $f$ 的基本和组。
构造积性函数 $h$ 满足 $h*g=f$。
观察到 $f(p)=h(1)g(p)+h(p)g(1)=h(p)+g(p)$，即 $h(p)=0$。因为积性，所以 $h$ 只在 $\mathrm{PN}$ 处有值。
根据杜教筛 $S_f(n)=\sum_{i=1}^n h(i)S_g(\left\lfloor n/i \right\rfloor)$。
由于 $h$ 有值的位置只有 $\sqrt n$ 个，我们可以搜索求值。复杂度是 $O(n^{2/3})$。