基础数论函数

数论函数定义为定义域为正整数的函数。下面是一些基础函数：

• 恒等函数 $\text{id}(x)=x$
• 常数函数 $\text{1}(x)=1$
• 单位函数 $\epsilon(x)=[x=1]=\begin{cases}1\ (x=1)\\ 0\ (x>1)\end{cases}$
• 约数函数 $\tau(x)=\sum_{d|x} 1$ (约数个数)
• 约数和函数 $\sigma(x)=\sum_{d|x}d$
• 欧拉函数 $\phi(x)=|{1\le k\le x,\gcd(k,x)=1}|$ (小于等于 $x$ 且与 $n$ 互质的数的个数)
• 莫比乌斯函数 $\mu(x)=\begin{cases}1\ (x=1)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ 0\ (x\ 含有平方约数)\ \ \ \ \ \ \ \ \ \ \ \ \ \\(-1)^k(k为x的质因数个数)\end{cases}$
• 质因子函数，设 $x=\prod p_i^{e_i}$
  • $\Omega(x)=\sum e_i$
  • $\omega(x)=\sum 1(e_i)$
• Liouville 函数 $\lambda(x)=(-1)^{\Omega(x)}$

Dirichlet 卷积/狄利克雷卷积

狄利克雷卷积：对于数论函数 $f(x)$ 与 $g(x)$ ，其狄利克雷卷积记作 $(f*g)(x)$ ，定义为：

有一些基础的转换关系：

• $\tau=1*1$
• $\epsilon=\mu*1$
• $\sigma=\text{id}*1$
• $\phi=\text{id}*\mu$

同时，狄利克雷卷积具有一些数论性质。对于数论函数 $f\ ,g\ ,h$ ，狄利克雷卷积具有：

• 交换律：$f*g=g*f$
• 结合律：$(f*g)*h=f*(g*h)$
• 分配律：$(f+g)*h=f*h+g*h$
• 逆元：当且仅当 $f(1)\ne0$ 时，存在 $f*g=\epsilon$ ，并且称 $g$ 为 $f$ 的 Dirichlet 逆元，记作 $f^{-1}$
• 单位元：$f*\epsilon=f$ ，其中单位函数 $\epsilon$ 是卷积单位元。

所以我们可以发现，$1$ 与 $\mu$ 互为 Dirichlet 逆元。

我们定义积性函数 $f$ 为：对于 $\gcd(x,y)=1$ ，$f(xy)=f(x)f(y)$ 。
定义完全积性函数 $f$ 为：对于 $x,y$ ，$f(xy)=f(x)f(y)$ 。

对于积性函数 $f,\ g$ ：$f*g$ 也是积性函数，且 $f^{-1}$ 一定存在且也为积性函数。

对于完全积性函数 $\alpha$ 与数论函数 $f,g$ ，有：

• 分配律：$(\alpha f)*(\alpha g)=\alpha\cdot (f*g)$
• 逆元：$(\alpha f)^{-1}=\alpha f^{-1}$
• 积性函数 $h$ 为完全积性函数，当且仅当 $h^{-1}=\mu h$

证明略，可以查阅 OI-wiki

莫比乌斯反演

设 $f(x)\ ,\ g(x)$ 为两个数论函数，那么有：

使用狄利克雷卷积证明，命题等价为：

因为 $1*\mu=\epsilon$ ，所以：

得证。