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

### 数论函数

$$(\boldsymbol{f} + \boldsymbol{g})(n) = \boldsymbol{f}(n) + \boldsymbol{g}(n)$$

$$(x \boldsymbol{f})(n) = x \boldsymbol{f}(n)$$

### 积性函数

$$\boldsymbol{f}(nm) = \boldsymbol{f}(n) \boldsymbol{f}(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{f}(n) = \prod_{i=1}^t \boldsymbol{f}(p_i^{k_i})$$

$$\boldsymbol{\varphi}(p^k) = p^k – p^{k-1} = p^{k-1}(p-1), \ \boldsymbol{\sigma}_0(p^k) = k + 1$$

$$\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}(n) = [n = 1]$$

$$\boldsymbol{\epsilon} * \boldsymbol{f} = \boldsymbol {f}$$

#### 逆元

$$\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}

• 当 $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 {\mu} (n) = \begin{cases} 1 & n=1 \\ (-1)^t & \prod_{i=1}^t k_i = 1 \\ 0 & otherwise \end{cases}$$

• 若 $\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}(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{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$$