回忆：狄利克雷卷积与积性函数¶
狄利克雷卷积¶
我们称一个函数 \(f\) 是数论函数（算术函数），当且仅当 \(f\) 的定义域为 \(\mathbb N^+\)，值域为 \(\mathbb C\)。
我们定义狄利克雷卷积如下：
区别于狄利克雷卷积，我们定义数论函数的乘法为：
直接套用定义，不难证明狄利克雷卷积有交换律，结合律，对加法的分配律，并且存在单位元 \(\epsilon(n) =[n=1]\)。并且对于任何一个 \(f(1)\neq 0\) 的 \(f\)，总存在一个逆元 \(g\) 使得 \(f*g=\epsilon\)。实际上数论函数在狄利克雷卷积作为乘法，函数加法作为加法的情况下构成整环。
这里看起来只有逆元是非平凡的，让我们来研究一下逆元：
要求出 \(g(n)\)，那么：
显然有：
积性函数¶
如果对于任意满足 \(n\perp m\) 的 \(n,m\in \mathbb N^+\)，有 \(f(n)f(m)=f(nm)\)，我们则称 \(f\) 是积性的。如果连 \(n\perp m\) 的条件也不需要，我们称其为完全积性的。
如果将正整数的每一个质因子视作独立的一维，积性的含义就是可以将两个维度不交的向量处的信息快速合并起来。
可以证明，两个积性函数的狄利克雷卷积仍然是积性函数，积性函数在狄利克雷卷积意义下的逆也是积性函数。
常见积性函数¶
下面举例列出一些常见的积性函数：
- \(\epsilon (n)=[n=1]\) （元函数）
- \(\mathbf{id}^k(n)=n^k\)
- \(\mathbf{I}(n)=1\) （恒等函数）
- \(\sigma_k(n)=\displaystyle \sum_{d|n}d^k\) （\(k\) 次因数和）
- \(\varphi(n)=\displaystyle\sum_{i=1}^{n}[\gcd(i,n)=1]\) （欧拉函数）
- \(\lambda(n)=(-1)^{\Omega (n)}\)，其中 \(\Omega(n)\) 为唯一分解定理中所有素数的幂次之和（刘维尔函数）
- \(\gamma(n)=(-1)^{\omega(n)}\)，其中 \(\omega(n)\) 为质因子个数。
- \(\mu(n)=\displaystyle\prod_{p\in\mathbb P,p\mid n}[p^2\not\mid n](-1)\) （莫比乌斯函数），此即为 \(\mathbf{I}(n)\) 在狄利克雷卷积下的逆元。用狄利克雷卷积逆的式子可以计算得到。
怎么筛出积性函数？¶
此内容仅适用于积性函数在素数幂处的点值可以被快速求出的情况。
我们知道 \(n\) 以内的质数个数 \(\pi(n)\sim \frac{n}{\ln n}\)，所以只要我们能在 \(\mathcal O(\log n)\) 的时间内求出每个素数幂处的函数值，套用如下方法就可以 \(\mathcal O(n)\) 求出 \(1\sim n\) 内的所有函数值。
考虑欧拉筛，欧拉筛的原理是每个 \(i\) 会被其最小质因子筛去，那么我们不妨同时维护每个数的最小质因子，记为 \(\mathbf{lpf}(n)\)，再记 \(\delta(n)\) 为最大的，能整除 \(n\) 的，\(\mathbf{lpf}(n)\) 的幂。那么 \(\frac{n}{\delta(n)}\perp \delta(n)\)，从而有 \(f(n)=f(\frac{n}{\delta(n)})f(\delta(n))\)，有时为了求出质数幂处的值，还要维护最小质因子的幂次。
例。
经典莫比乌斯反演¶
由于 \(\mu(n)\) 为 \(\mathbf {I}(n)\) 的狄利克雷卷积逆，所以：
在右侧式子的左右同卷上 \(\mathbf I\) 即可得到左侧的式子。
这可以被用来解决 \(f(n)\) 难求而 \(g(n)=\displaystyle \sum_{d\mid n}f(n)\) 易求的情况。
事实上莫比乌斯反演还有倍数形式：
其证明仍然可以参考铃悬的博客。