[模板] 狄利克雷卷积与莫比乌斯反演

数论函数

数论函数(或称算术函数)是指定义域为正整数,陪域为复数的函数,即 $\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
$$

参考资料