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\) 可以较容易地计算。以下是做法：

\[H(n)=\sum_{i=1}^n\sum_{d|i}g(d)f(i/d)=\sum_{d=1}^n\sum_{d|i}^{n}g(d)f(i/d)\\ =\sum_{d=1}^ng(d)\sum_{t=1}^{n/d}f(t)=\sum_{d=1}^ng(d)F(n/d).\\ g(1)F(n)=\sum_{i=1}^n g(i)F(n/i)-\sum_{i=2}^n g(i)F(n/i)\\ =H(n)-\sum_{i=2}^ng(i)F(n/i). \]

定理：若 \(f*g=h\)，则 \(H(n)=\sum_{i=1}^nf(i)G(n/i)\)。

时间复杂度

通过一些微积分技巧得到复杂度为（这里 \(T(n/i)\) 被放缩为 \(\sqrt{n/i}\)）。

\[T(n)=O(\sqrt{n})+O\left(\sum_{i=1}^\sqrt{n}T(n/i)\right)\\ =O(\sqrt{n})+O\left(\sum_{i=1}^\sqrt{n}\sqrt{\frac{n}{i}}\right)\\ =O\left(\int_0^\sqrt{n}\sqrt{\frac{n}{x}}{\rm d}x\right)=O(n^{3/4}). \]

如果预处理 \(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\)。