莫比乌斯函数/反演

前置

数论函数：定义域为正整数的函数。

积性函数： $\forall (a,b)=1,f(a\cdot b)=f(a)\cdot f(b),f$ 为数论函数。

莫比乌斯函数与欧拉函数都为积性函数。

迪利克雷卷积：

$(f*g)(x)=\sum_{d|x}f(d)\cdot g(\frac{x}{d})$

迪利克雷卷积的单位元：

$e(n)= [n=1]=\begin{cases} 1, & \text {$n=1$} \\ 0, & \text{$n\neq 1$} \end{cases}$

对于任意 $f$ 有：

$e*f=\sum_{d|x}e(d)f(\frac{x}{d})=f$

莫比乌斯函数

$\mu(n)=\begin{cases} (-1)^k,&n=p_1\cdot p_2\cdots p_k \bigwedge p_1\neq p_2\neq\cdots\neq p_k\\ 0,&\text{else} \end{cases}$

性质

$e(n)=\sum_{d|n}\mu(d)=\mu*1$

证明：

设 $n=\sum_{i=1}^k{p_i^{q_i}},n'=\sum_{i=1}^kp_i$ ，可以用 $n'$ 代替 $n$ ，因为 $n$ 中重复的质因子即使被选入 $d$ 中，也只会使 $\mu(d)=0$ ，对 $\sum_{d|n}\mu(d)$ 没有贡献，故以下用 $n'$ 代替 $n$ 。

从 $k$ 个质因数中选择 $i$ 个组成因数 $d$ ，有 $C_k^i$ 种选择，则

$\left. \begin{array}{l} \sum_{d|n}\mu(d)\\ =\sum_{i=0}^kC_k^i(-1)^i\\ =\sum_{i=0}^kC_k^i\cdot(-1)^i\cdot 1^{k-i}\\ =(-1+1)^k\\ =0^k\\ =\begin{cases} 1,&k=0\\ 0,&k\neq 0\\ \end{cases} \end{array} \right.$

$k=0$ 表明 $n$ 没有质因数，那么 $n=1$ 。

$\therefore \sum_{d|n}\mu(d)=e(n)=[n=1]$

求解莫比乌斯函数

莫比乌斯函数是积性函数，所以可以用线性筛求解。

void getMu() {
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!flg[i]) p[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
      flg[i * p[j]] = 1;	//筛素数
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;	//有多个相同的素因子
        break;
      }
      mu[i * p[j]] = -mu[i];	//素因子个数+1
    }
  }
}

莫比乌斯反演

形式1

$f(n)=\sum_{d|n}g(d)\\ \implies g(n)=(f*\mu)(n)=\sum_{d|n}f(d)\cdot\mu(\frac{n}{d})$

证明：

$\left. \begin{array}{l} f(n)=\sum_{d|n}g(d)\\ \implies f=g*1\\ \implies f*\mu=g*1*\mu=g*e=g\\ \therefore g(n)=(f*\mu)(n)=\sum_{d|n}f(d)\mu(\frac{n}{d}) \end{array} \right.$

形式2

$f(d)=\sum_{d|n}g(n)\\ \implies g(d)=\sum_{d|n}f(n)\cdot \mu(\frac{n}{d})$

证明：

$\left. \begin{array}{l} \sum_{d|n}f(n)\mu(\frac{n}{d})\\ =\sum_{k=1}^\infty\mu(k)f(dk)\\ =\sum_{k=1}^\infty\mu(k)\sum_{dk|t}g(t)\\ =\sum_{d|t}f(t)\sum_{k|\frac{t}{d}}\mu(k)\\ =\sum_{d|t}f(t)[\frac{t}{d}=1]\\ =f(d)\\ \end{array} \right.$