积性函数

定义

若 $\gcd(x,y) = 1$ 且 $f(xy) = f(x) f(y)$，则 $f(n)$ 为积性函数。

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数：

$$ \begin{align*} h(x) & = f(x^p) \\ h(x) & = f^p(x) \\ h(x) & = f(x)g(x) \\ h(x) & = \sum_{d \mid x} f(d)g(\frac{x}{d}) \\ \end{align*} $$

例子

$$ \begin{array}{} \text{约数个数函数} & d(n)=\sum_{d\mid n}1 \\ \text{约数和函数} & \sigma(n)=\sum_{d\mid n}d \\ \text{约数}\ k\ \text{次幂函数} & \sigma_k(n)=\sum_{d\mid n}d^k \\ \text{欧拉函数} & \varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1] \\ \text{莫比乌斯函数}& \mu(n)= \begin{cases} 1 & n=1 \\ (-1)^k & c_{1,2,\cdots,k}=1\quad(n=\prod_{i=1}^k {p_i}^{c_i}) \\ 0 & c_i>1 \end{cases} \end{array} $$

Dirichlet 卷积

定义

定义两个数论函数 $f,g$ 的 $\text{Dirichlet}$ 卷积为

$$ (f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d}) $$

性质

$\text{Dirichlet}$ 卷积满足交换律、结合律、分配律。

其中 $\varepsilon$ 为 $\text{Dirichlet}$ 卷积的单位元（任何函数卷 $\varepsilon$ 都为其本身）

例子

$$ \begin{align*} \varepsilon=\mu\ast 1 & \Leftrightarrow\varepsilon(n)=\sum_{d\mid n}\mu(d) \\ d=1\ast 1 & \Leftrightarrow d(n)=\sum_{d\mid n}1 \\ \sigma=d\ast 1 & \Leftrightarrow\varepsilon(n)=\sum_{d\mid n}d \\ \varphi=\mu\ast\operatorname{ID} & \Leftrightarrow\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \\ \end{align*} $$

莫比乌斯函数

定义

$\mu$ 为莫比乌斯函数

性质

莫比乌斯函数不但是积性函数，还有如下性质：

$$ \mu(n)= \begin{cases} 1 & n=1 \\ 0 & n\ \text{含有平方因子} \\ (-1)^k & k\ \text{为}\ n\ \text{的本质不同质因子个数} \\ \end{cases} $$

证明

$$ \varepsilon(n)= \begin{cases} 1 & n=1 \\ 0 & n\neq 1 \\ \end{cases} $$

其中 $\varepsilon(n)=\sum_{d\mid n}\mu(d)$ 即 $\varepsilon=\mu\ast 1$

设

$$ n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i $$

那么

$$ \sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k C_k^i\cdot(-1)^k $$

根据二项式定理，易知该式子的值在 $k=0$ 即 $n=1$ 时值为 $1$ 否则为 $0$，这也同时证明了 $\sum_{d\mid n}\mu(d)=[n=1]$

反演结论：$[gcd(i,j)=1]\Leftrightarrow\sum_{d\mid\gcd(i,j)}\mu(d)$

• 直接推导：如果 $\gcd(i,j)=1$，那么意味着上述结论中的 $n=1$，也就是式子的值是 $1$。反之不满足 $[\gcd(i,j)=1] $，值即为 $0$
• 利用 $\varepsilon$ 函数：根据上一结论，$[\gcd(i,j)=1]\Rightarrow\varepsilon(\gcd(i,j))$，将 $\varepsilon$ 展开即可。

线性筛

由于 $\mu$ 函数为积性函数，因此可以线性筛莫比乌斯函数（线性筛基本可以求所有的积性函数，尽管方法不尽相同）。

代码：

void sieve() {
    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]] = true;
            if (i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}

扩展结论

$$ \varphi\ast 1=\operatorname{ID}\quad\operatorname{ID}\ \text{即}\ f(x)=x $$

将 $n$ 分解质因数：$n=\prod_{i=1}^k {p_i}^{c_i}$

首先，因为 $\varphi$ 是积性函数，故只要证明当 $n'=p^c$ 时 $\varphi\ast 1=\sum_{d\mid n'}\varphi(\frac{n'}{d})=\operatorname{ID}$ 成立即可。

因为 $p$ 是质数，于是 $d=p^0,p^1,p^2,\cdots,p^c$

易知如下过程：

$$ \begin{align*} \varphi\ast 1 & =\sum_{d\mid n}\varphi(\frac{n}{d}) \\ & =\sum_{i=0}^c\varphi(p^i) \\ & =1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1) \\ & =p^c \\ & =\operatorname{ID} \\ \end{align*} $$

该式子两侧同时卷 $\mu$ 可得 $\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})$

莫比乌斯反演

公式

设 $f(n),g(n)$ 为两个数论函数。

如果有

$$ f(n)=\sum_{d\mid n}g(d) $$

那么有

$$ g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d}) $$

证明

暴力计算

$$ \sum_{d\mid n}\mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}g(k)=\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}\mu(d)=g(n) $$

用 $\sum_{d\mid n}g(d)$ 来替换 $f(\frac{n}{d})$，再变换求和顺序。最后一步转为的依据：$\sum_{d\mid n}\mu(d)=[n=1]$，因此在 $\frac{n}{k}=1$ 时第二个和式的值才为 $1$。此时 $n=k$，故原式等价于 $\sum_{k\mid n}[n=k]\cdot g(k)=g(n)$

运用卷积

原问题即为：已知 $f=g\ast 1$，证明 $g=f\ast\mu$

易知如下转化：$f\ast\mu=g\ast 1\ast\mu\Rightarrow f\ast\mu=g$（其中 $1\ast\mu=\varepsilon$）

习题