【笔记】数论进阶（数论函数相关）
8.1 数论进阶（数论函数相关）
以下记 \(F\) 为 \(f\) 的前缀和。\(n/m\) 表示 \(\left\lfloor\frac{n}{m}\right\rfloor\)。
整除分块
- \(n/i\) 取值只有 \(O(\sqrt{n})\) 种。
- \(a/(bc)=(a/b)/c\)。
- 满足 \(n/i=n/j\) 的 \(j\) 的最大值为 \(n/(n/i)\)。
于是可以对每一个相同的 \(n/i\) 合并计算。
狄利克雷卷积
积性函数
- 数论函数可以认为是定义域、值域为整数的函数。
- 积性函数：\((a,b)=1\to f(ab)=f(a)f(b)\)。每个积性函数都应该有 \(f(1)=1\)。
- 完全积性函数：\(f(ab)=f(a)f(b)\)。
狄利克雷卷积
对于两个数论函数 \(f,g\)，我们定义它们的狄利克雷卷积为 \((f*g)(n)=\sum_{d|n}f(d)g(n/d)\)。（注意这里没有需要积性）
狄利克雷卷积有交换律和结合律。
狄利克雷卷积运算对积性函数封闭。积性函数怎么卷都是积性函数。
常见函数和卷积
以下是一些非常重要的完全积性函数：
- 元函数 \(\epsilon(n)=[n=1]\) 是单位元，有 \(f*\epsilon=f\)。
- 恒等函数 \(I(n)=1\)。
- 单位函数 \(id(n)=n\)
- 幂函数 \(id_k(n)=n^k\)
积性函数：
- 莫比乌斯函数 \(\mu\) 的定义是：有平方因子的数的 \(\mu\) 为 \(0\)，否则为 \((-1)^c\) 其中 \(c\) 是质因子个数。\(\mu*I=\epsilon\)，意思是 \(\mu\) 是 \(1\) 的逆元。
- 欧拉函数 \(\varphi=\sum_{1\leq i\leq n}[(i,n)=1]\)。\(\varphi*I=id\)，推论是 \(id*\mu=\varphi\)，\(\varphi*\mu=id*\mu^2\)。
- 因数个数函数 \(d=\sigma_0=I*I=\sum_{d|n}1\)。
- 除数函数 \(\sigma_k=id_k*I=\sum_{d|n}d^k\)。
积性函数可以在线性时间内进行线性筛得到每个点的点值。
杜教筛
杜教筛
杜教筛可以在低于线性的时间内计算数论函数 \(f\) 的前缀和，需要我们找到另外两个数论函数 \(g,h\) 满足 \(f*g=h\)，并且 \(g,H\) 可以较容易地计算。以下是做法：
定理：若 \(f*g=h\)，则 \(H(n)=\sum_{i=1}^nf(i)G(n/i)\)。
时间复杂度
通过一些微积分技巧得到复杂度为（这里 \(T(n/i)\) 被放缩为 \(\sqrt{n/i}\)）。
如果预处理 \(O(n^{2/3})\) 的函数 \(F\) 点值那么复杂度为 \(O(n^{2/3})\)。
Powerful Number 筛
Powerful Number
定义 Powerful Number 为所有满足所有质因子指数都 \(> 1\) 的数，可以证明这样的数一定能被写成 \(a^2b^3\) 的形式，那么这样的数一共不超过 \(O(\int_0^\sqrt{n}\sqrt[3]{n/x^2}\textrm dx)=O(\sqrt{n})\) 个。
想要求出所有 Powerful number，只需要线性筛 \(O(\sqrt n)\) 以内的质数然后 DFS 枚举质数指数。
Powerful Number 筛
Powerful number 筛可以求出积性函数 \(f\) 的前缀和，需要构造积性函数 \(g\) 使得 \(g(p)=f(p)\)（以下 \(p\) 为质数）且 \(G\) 比较好求。令 \(h*g=f\)，那么有：
- \(h\) 是积性函数。\(h(1)=1\)。
- \(h(p)=0\)，这是因为 \(f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)\)，又有 \(g(p)=f(p)\)，所以 \(h(p)=0\)。
- \(h\) 只可能在 Powerful number 处有值。因为如果 \(n\) 不是 Powerful number，那么 \(h(n=pc)=h(p)h(c)=0\)。
从而有：
所以爆搜所有 Powerful number 求值即可。
算法流程
- 构造 \(g\) 满足 \(g(p)=f(p)\)。
- 计算 \(G\)。
- 计算 \(h(p^c)\)。
- 爆搜所有 Powerful number 求值。
\(h\) 的求法
因为 \(h\) 是积性函数，在 DFS 的过程中我们可以将若干个 \(h(p^c)\) 乘起来就能计算 Powerful number 的点值，所以现在要算 \(h\) 的质数幂点值。
- 大力解析 \(h(p^c)\) 使其只和 \(p,c\) 有关。
- \(f=g*h\to f(p^c)=\sum_{k=0}^cg(p^k)h(p^{c-k})\to g(1)h(p^c)=f(p^c)-\sum_{k=1}^cg(p^k)h(p^{c-k})\)。
时间复杂度
对于第三步第二种方法，复杂度为 \(O(\sqrt{n}\log n)\)。
对于第四步，如果 \(G\) 是 \(O(1)\) 的那么复杂度为 \(O(\sqrt{n})\)；如果 \(G\) 是杜教筛那么复杂度为杜教筛复杂度，不证明了。
后面的内容，有 min_25 筛、类欧几里得算法，都学不动了。标记了。
Powerful number 的代码，也完全没有了，等一会吧。标记了，模板题是 divcnt3。