积性函数

Vision271 · 2023-01-04 16:42:29 · 个人记录

唯一分解定理

本定理事实上还代表着 \gcd 和 \operatorname{lcm} 实质上等价于质数-指数向量取 \min/\max。

积性函数

满足 \forall a\perp b,f(ab)=f(a)\times f(b) 的数论函数被称为积性函数。
特别地，满足 \forall (a,b),f(ab)=f(a)\times f(b) 的函数被称为完全积性函数。鉴于 OI 中基本没有用到这个的机会，我们不区分完全积性与否。
如无特殊说明，我们提到的积性函数都满足 f(1)=1。
- 因为 f(1)=f(1)f(1)\to f(1)=0\text{ or }1，但显然 f(1)=0\to f(n)=f(n)f(1)=0。
- 故仅有 f(1)=1 的积性函数有意义。
鉴于积性函数的取值总可以由 f(p^k) 推出，我们通常通过描述其在质数幂上的表现的方式来定义积性函数。
下面列出几个常见的积性函数：

\epsilon(n)：元函数。

定义：狄利克雷卷积中的一元。
表现：\epsilon(n)=[n=1]。

I(n)：恒等函数。

定义与表现：I(n)=1。

id_k(n)：幂函数。

定义与表现：id_k(n)=n^k。
特别地，id_1 简记为 id，称为单位函数。

\mu(n)：莫比乌斯函数。

定义：狄利克雷卷积中，恒等函数 I 的逆元。
表现：
\mu(n)= \begin{cases} 0 & \text{n 含有平方因子} \\ (-1)^{\omega(n)} & \text{otherwise} \end{cases}
积性的证明：比较显然，可以由 0 的性质和 \omega(n) 的完全和性证明。也可以参看狄利克雷卷积部分对于积性函数的逆元还是积性函数的证明。

\varphi(n)：欧拉函数。

定义：n 以内与 n 互质的数的个数。
积性的证明：
- 由定义，可以推出定义式 \varphi(n)=\sum\limits_{i=1}^n [\gcd(i,n)=1]。
- 故只需证
\forall a\perp b, \sum\limits_{i=1}^a [\gcd(i,a)=1] \sum\limits_{j=1}^b [\gcd(j,b)=1] =\sum\limits_{k=1}^{ab} [\gcd(k,ab)=1]
- 式左等价于 \sum\limits_{i=1}^a \sum\limits_{j=1}^b [\gcd(i,a)=1 \And \gcd(j,b)=1]。
- 我们尝试证明式左右的艾佛森括号一一对应，那么先设法把上式化成含 ab 的形式，这里取 [\gcd(ib+ja,ab)=1]，可以证明它和 [\gcd(i,a)=1 \And \gcd(j,b)=1] 等价：
  - 由唯一分解定理，a\perp b\to \gcd(ib,a)=\gcd(i,a)；
  - 由欧几里得定理，\gcd(i,a)=\gcd(i+ja,a)；
  - 由唯一分解定理，a\perp b\to [\gcd(x,a)=1 \And \gcd(x,b)=1]\leftrightarrow [\gcd(x,ab)=1]。
  - 联立，得到 a\perp b\to [\gcd(ib+ja,ab)=1]\leftrightarrow [\gcd(i,a)=1 \And \gcd(j,b)=1]。
- 问题变成证明 ib+ja 和 k 一一对应。容易证明，ib+ja 和 k 的数量一样，问题变成证明 ib+ja 互不相同。
- 不妨设 i_1b+j_1a=i_2b+j_2a，其中 i_1\neq i_2 或 j_1\neq j_2，于是 (i_1-i_2)b=(j_2-j_1)a。
- 显然四项都是整数，移项得到 (i_1-i_2)=\dfrac{(j_2-j_1)a}{b}，又 a\perp b，所以 |j_2-j_1|\bmod b=0，又 j_1,j_2\in [1,b]\to |j_1-j_2|<b，不成立，一定有 j_1-j_2=0\to j_1=j_2。
- 但显然可以对称证明 i_1=i_2，于是假设不成立，不存在 i_1\neq i_2 或 j_1\neq j_2 的 (i,j) 对，满足 i_1b+j_1a=i_2b+j_2a，即 ib+ja 互不相同，故式左右的艾佛森括号一一对应，证毕。
质数幂上的表现：\varphi(p^k)=p^k-p^{k-1}。
- 可以由定义推出，减去 1\sim p^k 中是 p 的倍数的 \frac{p^k}{p}=p^{k-1} 个。
- 这里认为 p^{-1}=0，于是在 k=0 时其表现正确。
特别地，通过化式子，其有一种基于质因数分解的计算方式，这里记 n=\prod\limits_{i=1}^m p_i^{k_i}：

\begin{aligned} \varphi(n) & =\prod\limits_{i=1}^m \varphi(p_i^{k_i}) \\ & =\prod\limits_{i=1}^m p_i^{k_i}-p_i^{k_i-1} \\ & =\prod\limits_{i=1}^m p_i^{k_i-1}(p_i-1) \\ & =\prod\limits_{i=1}^m p_i^{k^i}\frac{p_i^{k_i-1}(p_i-1)}{p_i^{k^i}} \\ & =\prod\limits_{i=1}^m p_i^{k^i} \times \prod\limits_{i=1}^m \frac{p_i-1}{p_i} \\ & =n\prod\limits_{i=1}^m (1-\frac{1}{p_i}) \end{aligned}

显然，如此计算的复杂度应为 O(\sqrt{n})-O(\sqrt{n}+\log)（质因数分解+大质因数求逆元），如果 n 小到可以直接线性筛到 n 而非 \sqrt{n}，那么是 O(n)-O(\omega(n)) 的复杂度。

d(n)：约数个数函数。

定义：n 的约数个数。
表现：记 n=\prod\limits_{i=1}^m p_i^{k_i}，则 d(n)=\prod\limits_{i=1}^m k_i。
- 理由：约数在任意质数维上的次数可以为 [0,k_i] 中的任意数。
有时复杂度分析会用到这个函数，此时可以认为 d(n)=O(\sqrt[3]{n})。

\sigma_0(n)：约数和函数。

定义：n 的约数和。
表现：记 n=\prod\limits_{i=1}^m p_i^{k_i}，则 d(n)=\prod\limits_{i=1}^m \sum\limits_{i=0}^{k_i} p_i^{k_i}。
- 理由：任意质数维对约数的贡献可以为 \{p_i^{kn}\mid kn\in[0,k_i]\} 中的任意数。
另外，还有一个 bonus：

\omega(n)：质因数个数函数。

定义：n 的（可重）质因数个数。
表现：记 n=\prod\limits_{i=1}^m p_i^{k_i} 时的 \sum\limits_{i=1}^m k_i。
本函数不是积性函数，而是完全和性函数：\forall (a,b),\omega(ab)=\omega(a)+\omega(b)。
有时复杂度分析会用到这个函数，此时可以认为 \omega(n)\to \log_{10} n。

狄利克雷卷积

定义数论函数 f,g 的狄利克雷卷积函数 f\ast g 为 h(n)=\sum\limits_{d\mid n} f(d)\times g(\frac{n}{d})，这里 \ast 可以认为是卷积符号，和 \times 相区别。
狄利克雷卷积并不要求参与卷积的函数必须是积性函数，但在 OI 中我们通常只会用到积性函数的狄利克雷卷积。
一般地，若 h=\sum\limits_{i\oplus j=n}f(i)\times g(j)，其中 \oplus 为任意运算，则称 h 是 f\ast g，即一般化的卷积。可以说狄利克雷卷积是积卷积，因为其本质形式是 h(n)=\sum\limits_{i\times j=n} f(i)\times g(j)。
下面我们只谈狄利克雷卷积，\ast 和卷都指狄利克雷卷积。
代数结构 (R,+,\ast) 满足如下性质，其中 R 为数论函数集，+ 为函数加法，\ast 为狄利克雷卷积：

结合律：(f\ast g)\ast h=f\ast (g\ast h)

直接展开会发现式左右都是 \sum\limits_{i\times j\times k=n} f(i)\times g(j)\times h(k)。

单位元：f\ast \epsilon=f

证明：

\begin{aligned} (f\ast \epsilon)(n) & =\sum\limits_{d\mid n} f(d)\times \epsilon(\frac{n}{d}) \\ & =f(n)\ast \epsilon(1)+\sum\limits_{d\mid n \And d<n} f(d)\times \epsilon(\frac{n}{d}\neq 1) \\ & =f(n) \end{aligned}

证毕。这代表着 \epsilon 是狄利克雷卷积中的一元。

逆元：f=g\leftrightarrow f\ast h=g\ast h

这里数论函数 h 需要满足 h(1)\neq 0，也即 h 不是零元，否则不必要。
充分性显然，式子是全同的。略。
必要性：考虑使用反证法。取最小的 x 使得 f(x)\neq g(x)，于是有

\begin{aligned} (f\ast h)(x)-(g\ast h)(x) & =((f-g)\ast h)(x)\\ & =\sum\limits_{d\mid x} (f(d)-g(d))\times h(\frac{n}{d}) \end{aligned}

既然 x 是极小的，则对于 d<x，都有 f(d)-g(d)=0，于是

\begin{aligned} (f\ast h)(x)-(g\ast h)(x) & =\sum\limits_{d\mid x} (f(d)-g(d))\times h(\frac{n}{d}) \\ & =(f(x)-g(x))h(1) \\ & \neq 0 \end{aligned}

因为这里 h(1)\neq 0，故上式不为 0。前设不成立。
这实质上代表着零元外的所有函数都有逆元。
另一种更加常规的证明方式是这样的（上面的证明先证了可以左右同时卷）：
对非零元的任意数论函数 f，设 f\ast g=\epsilon，于是展开，得到

\begin{aligned} \epsilon(n) & =\sum\limits_{d\mid n} f(d)g(\frac{n}{d}) \\ & =f(1)g(n)+\sum\limits_{d\mid n\And d>1} f(d)g(\frac{n}{d}) \\ \end{aligned}

移项，得到

g(n)=\epsilon(n)-\sum\limits_{d\mid n\And d>1} f(d)g(\frac{n}{d})

g(n)= \begin{cases} 1 & n=1 \\ \sum\limits_{d\mid n\And d>1} f(d)g(\frac{n}{d}) & n>1 \end{cases}

显然 g 存在。

交换律：f\ast g=g\ast f

显然，其形式就是对称的。

对加法的分配律：(f+g)\ast h=f\ast h+g\ast h

直接展开，发现本质上是乘法对加法的分配律。
至此，我们证明了代数结构 (G,\ast) 是域。

积性函数上的封闭性

取 h=f\ast g，令 a\perp b，于是

\begin{aligned} h(a)h(b) & =\sum\limits_{d_1\mid a} f(d_1)g(\frac{a}{d_1}) \sum\limits_{d_2\mid b} f(d_2)g(\frac{b}{d_2}) \\ & =\sum\limits_{d\mid ab} f(d)g(\frac{ab}{d}) \\ & =h(ab) \end{aligned}

解释一下，第一行变到第二行的实质是 d=d_1d_2，因为显然总有 d_1\perp d_2，直接将 f,g 积到一起，得到第二行的式子。
故 (R',+,\ast) 也是域，这里 R' 是数论函数集。

积性函数的逆元还是积性函数

累了，下次再补（逃）。
逻辑上讲我是不用证这个的，因为我已经证明了 (R',\ast) 是群，故由群公理可以直接导出逆元的封闭性。
有如下事实：

\mu 与 I 互为逆元：\mu\ast I=\epsilon

证明：
已知 \mu,I,\epsilon 均为积性函数，故只证 (\mu\ast I)(p^k)=\epsilon(p^k)，下同。
对于 p^k，容易看出狄利克雷卷积式可以化为

\begin{aligned} \sum\limits_{i=0}^{k} \mu(p^i)\times I(p^{k-i}) & =\sum\limits_{i=0}^{k} \mu(p^i) \\ & =\mu(p^0)+\mu(p^1) \\ & =1+(-1) \\ & =0 \end{aligned}

证毕。这代表着 I 和 \mu 在狄利克雷卷积中互为逆元。
一个常见的应用是

\begin{aligned} [\gcd(i,j)=1] & =\epsilon(gcd(i,j)) \\ & =(\mu\ast I)(gcd(i,j)) \\ & =\sum\limits_{d\mid gcd(i,j)} \mu(d) \end{aligned}

\varphi 的狄利克雷前缀和是 id：\varphi\ast I=id

证明：

\begin{aligned} (\varphi\ast I)(p^k) & =\sum\limits_{i=0}^k \varphi(p^i) \\ & =p^0+(p^1-p^0)+(p^2-p^1)+\dots \\ & =p^k \\ & =id \end{aligned}

\varphi=id\ast \mu。

在上式左右同时卷 \mu 可得。

d=I\ast I

按定义式展开，得到

(I\ast I)(n)=\sum\limits_{d\mid n} 1

显然这就是 d 的定义。

\sigma_0=id\ast I

同上，有

(id\ast I)(n)=\sum\limits_{d\mid n} d

这就是 \sigma_0 的定义。

狄利克雷前缀和

定义 f 的狄利克雷前缀和为 g(n)=\sum\limits_{d\mid n} f(d)。
注意到 f 的狄利克雷前缀和函数可以认为是 f\ast I。
另外，若将一个数写成质数-指数向量，则狄利克雷前缀和就是高维前缀和，对其 FMT 可以做到 O(n\log \log n)。
- FMT：可以认为 g(n)=\sum\limits_{i=1}^{num} h(n')+f(n)，这里 n' 是将 n 的质数-指数向量上的第 i 位改成 k_i-1 对应的数，h 是 FMT 过程中的临时和。
- 为什么是 \log \log：考察总枚举量，发现其实为 \sum\limits_{i=1}^{num} k_i，即 \sum\limits_p \frac{n}{p}，和埃氏筛一样。

整除分块

考虑求 \sum\limits_{i=1}^n \lfloor\frac{n}{i}\rfloor。
引理：\forall a,b,c\in \mathbb{Z},\lfloor\frac{a}{bc}\rfloor=\lfloor\dfrac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor。
- 不妨设 \frac{a}{b}=k+r，其中 k\in \mathbb{Z},r\in [0,1)，于是
\begin{aligned} \lfloor\frac{a}{bc}\rfloor & =\lfloor\frac{1}{c}\times \frac{a}{b}\rfloor \\ & =\lfloor\frac{k}{c}+\frac{r}{c}\rfloor \\ \end{aligned}
- 这里我们设 k=k'c+r'，其中 k',r'\in \mathbb{Z}，且 r'\in [0,c)，于是
\begin{aligned} \lfloor\frac{a}{bc}\rfloor & =\lfloor\frac{k}{c}+\frac{r}{c}\rfloor \\ & =\lfloor k'+(r'+\frac{r}{c})\rfloor \end{aligned}
- 注意到 r'<c\to c-r'\geqslant 1，但 r<1\to \frac{r}{c}<1，所以 r'+\frac{r}{c}<1，于是
\begin{aligned} \lfloor\frac{a}{bc}\rfloor & =k' \\ & =\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor \end{aligned}
- 证毕。
定理 1：\lfloor\frac{n}{i}\rfloor 只有 O(\sqrt{n}) 种不同取值。
- 记 sq=\lceil\sqrt{n}\rceil。
- 故 \lfloor\frac{n}{i}\rfloor 只有 O(\sqrt{n}) 种取值，表现大概是这样
定理 2：\forall \lfloor\frac{n}{j}\rfloor=\lfloor\frac{n}{i}\rfloor,j_{\max}=\lfloor\dfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor。
- 不妨设 n=ki+r，即 k=\lfloor\frac{n}{i}\rfloor，于是有
k\leqslant \frac{n}{i}\to \lfloor\frac{n}{k}\rfloor \geqslant \lfloor\frac{n}{\frac{n}{i}}\rfloor=\lfloor i\rfloor=i
- 换言之，\forall \lfloor\frac{n}{j}\rfloor=\lfloor\frac{n}{i}\rfloor,\lfloor\frac{n}{k}\rfloor \geqslant j，故 \lfloor\frac{n}{k}\rfloor=\lfloor\dfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor=j_{\max}。
- 当然我们还要证明 \lfloor\frac{n}{k}\rfloor 是一个合法的 j，即 \lfloor\dfrac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor=\lfloor\frac{n}{i}\rfloor。
- 将式子展开，得到
\lfloor\dfrac{n}{\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor}\rfloor=\lfloor\frac{n}{i}\rfloor
- 考虑拆掉最里层的 \lfloor\rfloor，发现 \lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\to \lfloor\frac{n}{\frac{n}{i}}\rfloor=\lfloor i \rfloor=i 是变小了，分母变小整体变大，故有
\lfloor\dfrac{n}{\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor}\rfloor\leqslant \lfloor\frac{n}{i}\rfloor
- 考虑拆掉中间层的 \lfloor\rfloor，发现分母变大整体变小，式子变为
\lfloor\dfrac{n}{\frac{n}{\lfloor\frac{n}{i}\rfloor}}\rfloor=\lfloor\lfloor\frac{n}{i}\rfloor\rfloor=\lfloor\frac{n}{i}\rfloor
- 就是说，有
\lfloor\dfrac{n}{\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor}\rfloor\geqslant \lfloor\frac{n}{i}\rfloor
- 联立，得到
\lfloor\dfrac{n}{\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor}\rfloor=\lfloor\frac{n}{i}\rfloor
- 所以 \lfloor\dfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor 既是最大的，又是合法的，所以它是段 \lfloor\frac{n}{i}\rfloor 的右端点。
总之，整除分块可以用来快速求和。其也可以推广到多维，即 \sum\limits_{i=1}^{\min_{j=1}^{m} n_j} \prod\limits_{j=1}^m \lfloor\dfrac{n_j}{i}\rfloor。
可以发现此时不同的 \prod 值只有 O(\sqrt{n}m) 种，因为对于左边界 l，右边界为 \min_{j=1}^m \lfloor\dfrac{n_j}{\lfloor\frac{n_j}{l}\rfloor}\rfloor，表现大概是这样：
常与莫比乌斯反演结合，通用方法为将 \sum\limits_{d\mid n} 提到最前面变成 \sum\limits_{d=1}^n，将 \sum\limits_{i-1}^n 改为 \sum\limits_{i=kd}^{i\leqslant n}=\lfloor\dfrac{n}{d}\rfloor 。