数论函数
数论函数（或称算术函数）是指定义域为正整数，陪域为复数的函数，即 $\boldsymbol{f} : \mathbb{Z}^{+} \rightarrow \mathbb{C}$
数论函数的加法为逐项相加，即
$$
(\boldsymbol{f} + \boldsymbol{g})(n) = \boldsymbol{f}(n) + \boldsymbol{g}(n)
$$
数论函数的数乘为这个数逐项相乘，即
$$
(x \boldsymbol{f})(n) = x \boldsymbol{f}(n)
$$
积性函数
如果一个数论函数 $\boldsymbol{f}$ 在 $n \perp m$ 时（ $n$ 与 $m$ 互质）有
$$
\boldsymbol{f}(nm) = \boldsymbol{f}(n) \boldsymbol{f}(m)
$$
那么这个数论函数就是积性函数。
如果数论函数 $\boldsymbol{f}$ 对任意 $n$ 和 $m$ 均成立，那么这个函数就是完全积性函数
$\boldsymbol{\varphi}(n)$ 和 $\boldsymbol{\sigma}_0(n)$ 就是常见的积性函数，其中 $\boldsymbol{\varphi}(n)$ 指欧拉函数（小于 $n$ 且与 $n$ 互质的数的个数），$\boldsymbol{\sigma}_0(n)$ 指 $n$ 的约数个数（ $\boldsymbol{\sigma}_k(n)$ 指 $n$ 的约数的 $k$ 次方和 ）
$\boldsymbol{\epsilon}(n) = [n = 1]$ 和 $\boldsymbol{id}(n) = n$ 以及 $\boldsymbol{id^k} (n) = n^k $ 就是常见的完全积性函数
特别的，我们可以定义一个数论函数 $\boldsymbol{1}(n) = 1$
对于一个积性函数，我们可以进行线性筛。
每一个正整数 $n$ 都有唯一的质因数分解形式 $n = \prod_{i=1}^t p_i^{k_i} $
$$
\boldsymbol{f}(n) = \prod_{i=1}^t \boldsymbol{f}(p_i^{k_i})
$$
另外，$\boldsymbol{\varphi}$ 和 $\boldsymbol{\sigma}_0$ 在素数幂处的值求解非常容易，
$$\boldsymbol{\varphi}(p^k) = p^k – p^{k-1} = p^{k-1}(p-1), \ \boldsymbol{\sigma}_0(p^k) = k + 1$$
因为对于一个质因数的幂次 $p^k$，除了 $p$ 的倍数，其他的数都与它互质
$$
\boldsymbol{\sigma}_ {0} (n) = \prod_{i=1}^t (k_i+1), \ \boldsymbol{\varphi}(n) = \prod_{i=1}^t (p_i^{k_i} – p^{{k_i}-1}_ {i}) = n \prod_{i=1}^t (1 – \frac{1}{p_i})
$$
狄利克雷卷积
定义
定义两个数论函数的狄利克雷卷积 $*$
$$
\begin{aligned}
\boldsymbol{t}(n) &= \boldsymbol{f}(n) * \boldsymbol{g}(n) \\
&= \sum_{i \mid n} \boldsymbol{f}(i) \boldsymbol{g}(\frac{n}{i})
\end{aligned}
$$
性质
- 交换律 $\boldsymbol{f} * \boldsymbol{g} = \boldsymbol{g} * \boldsymbol{f}$
- 结合律 $(\boldsymbol{f} * \boldsymbol{g}) * \boldsymbol{h} = \boldsymbol{f} * (\boldsymbol{g} * \boldsymbol{j})$
- 分配律 $(\boldsymbol{f} + \boldsymbol{g}) * \boldsymbol{h} = \boldsymbol{f} * \boldsymbol{h} + \boldsymbol{g} * \boldsymbol{f}$
单位元
定义单位元 $\boldsymbol{\epsilon}$
$$\boldsymbol{\epsilon}(n) = [n = 1]$$
那么
$$
\boldsymbol{\epsilon} * \boldsymbol{f} = \boldsymbol {f}
$$
逆元
若 $\boldsymbol{f} * \boldsymbol{g} = \boldsymbol{\epsilon}$，则我们称 $\boldsymbol{g}$ 是 $\boldsymbol{f}$ 的逆元，每一个 $\boldsymbol{f}(1) \not = 0$ 的
数论函数都有逆元。
$$
\boldsymbol{g}(n) = \frac{1}{\boldsymbol{f}(1)} ([n=1] – \sum_{i \mid n, i \not = 1} \boldsymbol{f}(i) \boldsymbol{g}(\frac{n}{i}))
$$
证明
$$
\begin{aligned}
\boldsymbol{f} * \boldsymbol{g} &= \sum_{i \mid n} \boldsymbol{f}(i) \boldsymbol{g}(\frac{n}{i}) \\
&= \boldsymbol{f}(1) \boldsymbol{g}(n) + \sum_{i \mid n , i \not = 1} \boldsymbol{f}(i) \boldsymbol{g}(\frac{n}{i}) \\
&= [n=1] – \sum_{i \mid n, i \not = 1} \boldsymbol{f}(i) \boldsymbol{g}(\frac{n}{i}) + \sum_{i \mid n , i \not = 1} \boldsymbol{f}(i) \boldsymbol{g}(\frac{n}{i}) \\
&= [n=1] \\
&= \boldsymbol{\epsilon}
\end{aligned}
$$
卷积的积性
两个积性函数的狄利克雷卷积是积性函数
$$
\begin{aligned}
\boldsymbol{t}(nm) &= \boldsymbol{f}(nm) * \boldsymbol{g}(nm) \\
&= \sum_{d \mid nm} \boldsymbol{f}(d) \boldsymbol{g}(\frac{nm}{d}) \\
&= \sum_{a \mid n, b \mid m} \boldsymbol{f}(ab) \boldsymbol{g}(\frac{nm}{ab}) \\
&= \sum_{a \mid n, b \mid m} \boldsymbol{f} (a) \boldsymbol{f}(b) \boldsymbol{g}(\frac{nm}{a}) \boldsymbol{g}(\frac{nm}{b}) \\
&= \left( \sum_{a \mid n} \boldsymbol{f}(a) \boldsymbol{g}(\frac{nm}{a}) \right) \left( \sum_{b \mid m} \boldsymbol{f}(b) \boldsymbol{g}(\frac{nm}{b}) \right) \\
&= \boldsymbol{t}(n)\boldsymbol{t}(m)
\end{aligned}
$$
积性函数的逆是积性函数
对于一个积性函数，$\boldsymbol{f}(1) = 1$，因为根据积性函数的定义 $\boldsymbol{f}(1) = \boldsymbol{f}(1) \boldsymbol{f}(1)$
使用归纳法证明
- 当 $nm = 1$ 时，$\boldsymbol{g}(1) = 1$，显然成立
- 当 $nm > 1$ 时，假设 $n’m’ < nm$ 时有 $\boldsymbol{g}(n’m’) = \boldsymbol{g}(n’) \boldsymbol{g}(m’)$，
$$
\begin{aligned}
\boldsymbol{g}(nm) &= -\sum_{d \mid nm, d \not = 1} \boldsymbol{f}(d) \boldsymbol{g}(\frac{nm}{d}) \\
&= – \sum_{a \mid n, b \mid m, ab \not = 1} \boldsymbol{f}(ab) \boldsymbol{g}(\frac{nm}{ab}) \\
&= – \sum_{a \mid n, b \mid m, ab \not = 1}
\boldsymbol{f}(a) \boldsymbol{f}(b) \boldsymbol{g}(\frac{n}{a}) \boldsymbol{g}(\frac{m}{b}) \\
&= \boldsymbol{f}(1) \boldsymbol{f}(1) \boldsymbol{g}(n) \boldsymbol{g}(m) – \sum_{a \mid n,b \mid m} \boldsymbol{f}(a) \boldsymbol{f}(b) \boldsymbol{g}(\frac{n}{a}) \boldsymbol{g}(\frac{m}{b}) \\
&= \boldsymbol{f}(1) \boldsymbol{f}(1) \boldsymbol{g}(n) \boldsymbol{g}(m) – \left( \sum_{a \mid n} \boldsymbol{f}(a) \boldsymbol{g}(\frac{n}{a}) \right) \left( \sum_{b \mid m} \boldsymbol{f}(b) \boldsymbol{g}(\frac{m}{b}) \right) \\
&= \boldsymbol{g}(n) \boldsymbol{g}(m) – \boldsymbol{\epsilon}(n) \boldsymbol{\epsilon}(m) \\
&= \boldsymbol{g}(n) \boldsymbol{g}(m)
\end{aligned}
$$
以及一个关于欧拉函数的性质
$$\sum_{d \mid n} \boldsymbol{\varphi}(d) = n$$
所以
$$\boldsymbol{id} = \boldsymbol{\varphi} * \boldsymbol{1} $$
莫比乌斯函数
定义 $\boldsymbol{1}$ 的逆为 $\boldsymbol{\mu}$
令 $n = \prod_{i=1}^t p_i^{k_i}$
$$
\boldsymbol {\mu} (n) =
\begin{cases}
1 & n=1 \\
(-1)^t & \prod_{i=1}^t k_i = 1 \\
0 & otherwise
\end{cases}
$$
因为积性函数的逆也是积性函数，所以 $\boldsymbol{\mu}$ 是积性函数
当 $n$ 为质数的时候，显然 $\boldsymbol{\mu}(n) = -1$
设 $g$ 为 $n$ 的最小质因子，令 $n’ = \frac{n}{g}$，那么 $n$ 就可以通过 $n’ \times g$ 筛去
当 $n’ \ mod \ g = 0$ 时，根据定义，$\boldsymbol{\mu}(n) = – \boldsymbol{\mu}(n’) = 0$，
当 $n’ \ mod \ g \not = 0$ 时，也有 $\boldsymbol{\mu}(n) = – \boldsymbol{\mu}(n’)$
- 若 $\boldsymbol{\mu}(n’) = 0$，显然 $\boldsymbol{\mu}(n) = 0$
- 若 $\boldsymbol{\mu}(n’) \not = 0$
$$
\begin{aligned}
\boldsymbol{\mu}(n) &= (-1)^N \\
&= (-1)^{N-1} \times (-1) \\
&= \boldsymbol{\mu}(n’) \times (-1) \\
&= – \boldsymbol{\mu}(n’)
\end{aligned}
$$
inline void calc(){
mu[1] = 1;
for(register int i=2; i<=n; i++){
if(!isNotPrime[i]){
pri[cnt++] = i;
mu[i] = -1;
}
for(register int j=0; j<cnt; j++){
if(i * pri[j] > n)
break;
isNotPrime[i * pri[j]] = true;
if(i % pri[j] == 0){
mu[i * pri[j]] = 0;
break;
}else{
mu[i * pri[j]] = -mu[i];
}
}
}
}
莫比乌斯反演
那么如果 $\boldsymbol{g} = \boldsymbol{f} * \boldsymbol{1}$，那么 $\boldsymbol{f} = \boldsymbol{f} * \boldsymbol{1} * \boldsymbol{\mu} = \boldsymbol{g} * \boldsymbol{\mu}$
即，若
$$
\boldsymbol{g}(n) = \sum_{d \mid n} \boldsymbol{f} (d)
$$
则
$$
\boldsymbol{f}(n) = \sum_{d \mid n} \boldsymbol{\mu} \left( \frac{n}{d} \right) \boldsymbol{g}(d)
$$
类似的，$\boldsymbol{id^k}$ 的逆为 $\boldsymbol{\mu}(n) n^k$
因此，若
$$
\boldsymbol{g}(n) = \sum_{d \mid n} (\frac{n}{d})^k \boldsymbol{f}(d)
$$
那么
$$
\boldsymbol{f}(n) = \sum_{d \mid n} \boldsymbol{\mu} (\frac{n}{d}) (\frac{n}{d})^k \boldsymbol{g}(d)
$$
因此我们可以得到
$$
\boldsymbol{\varphi}(n) = \sum_{d \mid n} \boldsymbol{\mu}(\frac{n}{d}) d
$$