莫比乌斯反演

由函数 $f$ 定义一个函数 $g$：

$$g(n)=\sum_{d\mid n}f(d)\quad\big(\text{或}\quad g(n)=\sum_{n\mid d}f(d)\big)$$

已知 $g(n)$，即可用莫比乌斯反演推出 $f(n)$.

$n$ 的莫比乌斯函数记为 $\mu(n)$：

$$\mu(n)=\begin{cases} 0 & n \ 有平方因数 \\ 1 & n \ 无平方因数，且有偶数个质因数 \\ -1 & n \ 无平方因数，且有奇数个质因数 \end{cases}$$

特别地，$μ(1)=1$.

$$\sum_{d\mid n}μ(d) = \left\lfloor\frac{1}{n}\right\rfloor = \begin{cases} 1 & n=1\\ 0 & n>1 \end{cases}$$

证

设 $n$ 有 $k$ 个质因子 $p_1,p_2,\cdots,p_k$，则：

$$\begin{aligned} \sum_{d\mid n}μ(d) = \ &μ(1)+μ(p_1)+μ(p_2)+\cdots+μ(p_k)+μ(p_1p_2)+\cdots+μ(p_1p_2\cdots p_k)\\ = \ &{k\choose 0}+{k\choose 1}(-1)+{k\choose 2}(-1)^2+\cdots+{k\choose k}(-1)^k\\ = \ &\sum_{i=0}^k{k\choose i}(-1)^i \end{aligned}$$

由 二项式定理 得：

$$\sum_{i=0}^k{k\choose i}(-1)^i=(1-1)^k=\begin{cases}1&k=1\\0&k>1\end{cases}$$

当且仅当 $n=1$ 时，$k=1$. 因此：

$$\sum_{d\mid n}μ(d)=\begin{cases}1&n=1\\0&n>1\end{cases}$$

$$\sum_{d\mid gcd(n,m)}μ(d)= \begin{cases} 1 & n,m \ 互质\\ 0 & n,m \ 不互质 \end{cases}$$

证

根据 性质 1 自证.

$$\displaystyleμ(nm)=\begin{cases}μ(n)\cdotμ(m)&n,m \ 互质\\0&n,m \ 不互质\end{cases}$$

证

读者自证.

基于质数的 线性筛法 求 $μ(1)\simμ(n)$.

const int N = 1e6;
vector<int> prime;
int miu[N];
bool isPrime[N];

void getMiu(int n) {
    miu[1] = 1;
    memset(isPrime, true, sizeof isPrime);
    for (int i = 2; i <= n; i ++) {
        if (isPrime[i])
            prime.push_back(i), miu[i] = -1;
        for (int j = 0; j < prime.size(); j ++) {
            if (i * prime[j] > n)
                break;
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
              miu[i * prime[j]] = 0;
              break;
            } else {
              miu[i * prime[j]] = miu[i] * miu[prime[j]];
            }
        }
    }
}

函数 $f(x)$ 和 $g(x)$ 的狄利克雷卷积 $h(x)$ 定义为：

$$h(x)=\sum_{d|x}f(d)g\!\left(\frac{x}{d}\right)=\sum_{ab=x}f(a)g(b)$$

简记为：

$$h=f*g$$

• 交换律：$f* g=g*f$.

• 结合律：$(f* g)*h=f *(g *h)$.

• 分配律：$(f+g)*h=f *h+g *h$.

• 等式的性质：$f=g\eq f* h=g*h,h(1)\not=0$.

• 单位元：即单位函数 $ε$，满足 $f*ε=f$.

$$ε(n)=\begin{cases}1&n=1\\0&n>1\end{cases}$$

值为常数的函数，如 $f(n)=C$，在狄利克雷卷积中简记为 $C$.

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

$$ε(n)=\sum_{d\mid n}μ(d)\quad ( 或 \quad\normalsize 1*μ=ε)$$

证

由 $μ$ 函数的 性质 1 得：

$$\sum_{d\mid n}μ(d)=\begin{cases}1&n=1\\0&n>1\end{cases}=ε(n)$$

$$∴1*μ=ε$$

$$f(n)=\sum_{d\mid n}g(d)\Longrightarrow g(n)=\sum_{d\mid n}μ(d)f\!\left(\frac{n}{d}\right)$$

证

原式可简记为：

$$f=g*1\Longrightarrow g=μ *f$$

由 重要结论 得：

$$f=g* 1\Longrightarrow f* μ=g* (1 *μ)=g *ε=g$$

即证.

$$f(n)=\sum_{n\mid d}g(d)\Longrightarrow g(n)=\sum_{n\mid d}μ\!\left(\frac{d}{n}\right)f(d)$$

证

$$\begin{aligned} & \sum_{n\mid d}μ\!\left(\frac{d}{n}\right)f(d)\\ = \ &\sum_{k=1}^{+∞}μ(k)f(kn)&&\quad 设 \ k=\frac{d}{n}，代入\\ = \ &\sum_{k=1}^{+∞}μ(k)\sum_{kn\mid d}g(d)&&\quad 将 \ f(n)=\sum_{n\mid d}g(d) \ 代入\\ = \ &\sum_{n\mid d}g(d)\sum_{k\mid\frac{d}{n}}μ(k)\\ = \ &\sum_{n\mid d}g(d)ε\!\left(\frac{d}{n}\right)&&\quad 套用 \ 重要结论\\ = \ &g(n) \end{aligned}$$