莫比乌斯 Möbius 数论函数

学习记录
, ,

一、什么是数论函数

定义 $f(n)$ 为数论函数，当其定义域和值域 $D,I\in\mathbb Z$。
这样的函数有很多很好的性质，比如可以写成一个无穷向量，可以用来卷积等等。

二、迪利克雷卷积

如果将两个函数写成向量形式，我们就可以定义一个新的符号 $*$。

定义 $(f*g)(n)=\displaystyle\sum_{d|n}f(d)\cdot g(\frac n d)$

这里的 $(f*g)$ 就是一个新的向量，也是一个新的函数。

我们也可以定义另外一个符号 $\hat * $（叫做倍数迪利克雷卷积），有 $(f\hat{*} g)(n)= \displaystyle\sum_{n|d}f(d)\cdot g(\frac d n)$，但是这个不常用。

三、基础函数

在迪利克雷卷积运算体系下，有这么一些运算定律：

  1. 存在唯一单位元 $\epsilon(n)$ 满足任意一个数论函数 $f(n)$ 都有 $f=f*\epsilon$
  2. 存在唯一逆元 $\mu(n)$ 满足任意一个数论函数 $f(n)$ 都有 $f^{-1}=f*\mu$。
  3. 满足交换律和结合律。

现在给出一些基础数论函数的定义：

名称 定义
1. 单位元函数 $\epsilon(n)=[n=1]$，其中 $[\text{condition}]$ 表示 $\begin{cases} 1 &\text{if condition} \\ 0 &\text{otherwise} \end{cases}$，下同。
2. 常函数 $I(n)=1$
3. 约数函数 $\tau(n)=\sum\limits_{d|n}1$。
4. 约数和函数 $\sigma(n)=\sum\limits_{d|n}d$ 。
5. 下标函数 $\text{id}(n)=n$。
6. 莫比乌斯函数 $\mu(n) = \begin{cases} 1 &\text{if}\;n=1 \\ 0 &\text{if}\;\exists p \in \text{primes},\;p^2|n \\ (-1)^k &\text{otherwise}\quad(k\text{ 表示 }n\text{ 的质因子个数}) \end{cases} $
7. 欧拉函数 $\displaystyle\varphi(n)=\sum_{i=1}^k(a_i+1)\qquad\text{where}\;n=\displaystyle\prod_{i=1}^k {p_i}^{a_i}\,\text{and}\,p_i\in\text{primes}$

现在来看这些基础函数的关系。

$$
\def\id{\text{id}}
\begin{align}
\epsilon&=I*\mu \impliedby \sum_{d|n} \mu(d) = 0 \implies \mu(n) = -\sum_{d|n\,\land\,d\neq n}\mu(d) \\
I=\tau*\mu \iff \tau&=I * I \\
\id=\sigma*\mu \iff \sigma&=I*\id \\
\varphi=\id*\mu \iff \id&=I*\varphi \impliedby \sum_{d|n} \varphi(d)=n \impliedby
\begin{cases}
\text{Denote } S_d=\{k:k\in [1,n]\cap\mathbb Z, \gcd(k,n)=d\} \\
\text{So } \bigcap_{d=1}^n S_d = \varnothing \text{ and } \bigcup_{d=1}^n S_d = [1,n] \cap \mathbb Z \\
\text{Also } |S_d| = \varphi(\dfrac n d) \\
\text{Therefore } n = \displaystyle\sum_{d|n} |S_d| = \sum_{d|n} \varphi(\frac n d) = \sum_{d|n} \varphi(d)
\end{cases} \\
\end{align}
$$

根据定义，有两种求 $\mu$ 的方法。

方法一：根据定义 线性 $\mathcal O(n)$ 
1
2
3
4
5
6
7
8
9
mu[i] = 1, np[i] = true;
for (int i = 2; i <= n; i++) {
    if (!np[i]) p[++p[0]] = i, mu[i] = -1;
    for (int j = 1; j <= p[0] && i * p[j] <= n; j++) {
        np[i * p[j]] = true;
        if (i % p[j] == 0) { mu[i * p[j]] = 0; break; }
        mu[i * p[j]] = -mu[i];
    }
}

其实这里面的 mu[i * p[j]] = 0 可以去掉因为初始化就是 $0$。

方法二：根据递归式 对数 $\mathcal O(n \log n)$ 
1
2
3
4
mu[1] = 1;
for (int i = 1; i <= (n >> 1); i++)
    for (int j = i << 1; j <= n; j += i)
        mu[j] -= mu[i];

四、反演函数

  1. 嵌入式反演。对于函数 $f(n)=[n=m]$，其中 $m$ 为常数，那么有 $\displaystyle f(n)=[m|n] \cdot \sum_{d|\frac n m} \mu(d)$。
  2. 因数反演。对于函数 $\displaystyle f(n)=\sum_{d|n}g(d)$，有 $f=g* I$，那么 $g=f*\mu$，即 $\displaystyle g(n)=\sum_{d|n}\mu(d)\cdot f(\frac n d)$。
  3. 倍数反演。对于函数 $\displaystyle f(n)=\sum_{n|d}g(d)$，有 $f=g\,\hat* \,I$，那么 $g=f\,\hat * \,\mu$，即 $\displaystyle g(n)=\sum_{n|d}\mu(d) \cdot f(\frac n d)$。

五、实例演练

  1. 求 $\displaystyle \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]$ $ \qquad\text{Single: } \mathcal O(\sqrt n) \quad\text{pre: } \mathcal O(n) $

    • 嵌入式反演经典题目。

    可以使用 $\displaystyle[\gcd(i,j)=1] = \sum_{d|\gcd(i,j)} \mu(d) = \sum_{d|i\,\land\,d|j} \mu(d)$。将这个式子带入原式，套路性的将 $d$ 的枚举顺序提前。
    可以这样想，计算每一个 $\mu(d)$ 在求和式子里头被算了多少次，深度思考易转换为 $\displaystyle \sum_{d=1}^n\mu(d)\cdot\sum_{\begin{aligned}d|i &\land i\leqslant n, \\ d|j &\land j\leqslant n\end{aligned}}1$。发现这个求和式子就是 $\lfloor\dfrac n d\rfloor \cdot \lfloor\dfrac m d\rfloor$。于是放回去就得到了如下等式：
    $$ \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1] \;=\; \sum_{d=1}^n\mu(d)\cdot\lfloor\dfrac n d\rfloor \cdot \lfloor\dfrac m d\rfloor $$
    这个等式可以被 $\mathcal O(n)$ 计算，但是我们要的是 $\mathcal O(\sqrt n)$ 的时间复杂度。

    • 整除分块

    就是普通的整除分块，考虑使用 $\displaystyle\mu_{\text{sum}}(n)=\sum_{i=1}^n \mu(i)$ 加速计算。发现 $\lfloor\dfrac n d\rfloor$ 和 $\lfloor\dfrac m d\rfloor$ 存在大量重复，使用整除分块将其提取公因式，然后再乘上 $\mu$ 的前缀和就可以了。

    1
    2
    3
    4
    5
    6
    if (n > m) n^=m^=n^=m;
    long long ans = 0;
    for (int l = 1, r, x, y; l <= n; l = r + 1) {
        r = min(n / (x = n / l), m / (y = m / l));
        ans += (musum[r] - musum[l-1]) * x * y;
    }

  2. 求 $\displaystyle \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=p]$ $ \qquad\text{Single: } \mathcal O(\sqrt n) \quad\text{pre: } \mathcal O(\displaystyle\sum_{p \in P} \lfloor \frac n d \rfloor) $
    $$ \begin{aligned}
    &\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j) \in P]
    \\ =&\sum_{p \in P}\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=p]
    \\ =&\sum_{p \in P}\sum_{i=1}^n\sum_{j=1}^m [p | i \,\land\, p | j]\cdot\sum_{d|\frac i p\,\land\,d|\frac j p} \mu(d)
    \\ =&\sum_{p \in P}\sum_{d=1}^{\lfloor \frac n p \rfloor}\mu(d)\cdot\lfloor \frac{n}{p\cdot d} \rfloor\cdot\lfloor \frac{m}{p\cdot d} \rfloor
    \\ =&\sum_{pd=1}^n\lfloor \frac{n}{pd} \rfloor\cdot\lfloor \frac{m}{pd} \rfloor\cdot \sum_{p \in P}\mu(\frac{pd}{p})
    \end{aligned}
    $$
    这里涵盖了两个部分，前半是求解 $\gcd$ 为 $p$ 的时候最后的卷积式子，后半是将 $pd$ 套路性提取出来，然后就可以预处理一个因数卷积的式子。

  3. 求 $\displaystyle\prod_{i=1}^n\prod_{j=1}^m f_{\gcd(i,j)}$
    $$
    \begin{aligned}
    &\prod_{i=1}^n\prod_{j=1}^m f_{\gcd(i,j)}
    \\ =&\prod_{d=1}^n {f_d}^{\displaystyle\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]}
    \\ =&\prod_{d=1}^n {f_d}^{\displaystyle\sum_{i=1}^n\sum_{j=1}^m[d|i]\cdot[d|j]\cdot\sum_{k|\frac n d \,\land\, k|\frac m d} \mu(k) \cdot \lfloor \frac{n}{k\cdot d} \rfloor \cdot \lfloor \frac{m}{k\cdot d} \rfloor}
    \\ =&\prod_{kd=1}^n (\prod_{d|kd} {f_d}^{\dfrac{kd}{k}})^{\displaystyle\lfloor \frac{n}{kd}\rfloor\lfloor \frac{m}{kd}\rfloor}
    \end{aligned}
    $$
    对于连乘 $\prod$ 我们想要求和式子，就可以将其中底数提出来枚举，然后对其指数卷积。同样套路性地提出来其中的 $kd$ 进行枚举，得到其中可以被预处理的关于 $kd$ 的因数卷积式子。

  4. 求 $\displaystyle\sum_{i=1}^n\sum_{j=1}^m \gcd(i,j)$
    $$
    \begin{aligned}
    &\sum_{i=1}^n\sum_{j=1}^m \gcd(i,j)
    \\ =&\sum_{i=1}^n\sum_{j=1}^m \sum_{d\,|\gcd(i,j)}\varphi(d)
    \\ =&\sum_{i=1}^n\sum_{j=1}^m \sum_{d|i\,\land\,d|j}\varphi(d)
    \\ =&\sum_{d=1}^n\varphi(d) \cdot \lfloor \frac n d \rfloor \cdot \lfloor \frac m d \rfloor
    \end{aligned}
    $$
    只需要用一下 $n=\sum\limits_{d|n}\varphi(d)$ 就可以了。

  5. 求 $\displaystyle\sum_{i=1}^n\sum_{j=1}^m \sigma(\gcd(i,j))$
    $$
    \begin{aligned}
    &\displaystyle\sum_{i=1}^n\sum_{j=1}^m \sigma(\gcd(i,j))
    \\ =&\sum_{d=1}^n\sigma(d)\cdot\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]
    \\ =&\sum_{d=1}^n\sigma(d)\cdot\sum_{k=1}^{\lfloor \frac n d \rfloor}\mu(k)\cdot\lfloor \frac{n}{k \cdot d} \rfloor\cdot\lfloor \frac{m}{k \cdot d} \rfloor
    \\ =&\sum_{kd=1}^n\lfloor \frac{n}{k \cdot d} \rfloor\cdot\lfloor \frac{m}{k \cdot d} \rfloor\cdot \sum_{d|kd}\sigma(d)\cdot\mu(\frac{kd}{d})
    \end{aligned}
    $$
    洛谷 P3312 有一个很有意思的点，就是你要根据一个给定的 $a$ 动态维护后面那个东西 $\sum\limits_{d|kd}\sigma(d)\mu(\frac{kd}{d}) $，使得只有 $\sigma(d) \leqslant a$ 的点才有贡献。那么这里因为最终肯定是要计算前缀和的，自然而然想到使用树状数组，所以每次加进来一个 $\sigma(d)$ 直接暴力往后跳就可以了。一共会枚举 $\mathcal O(n \log n)$ 个倍数，每次修改是 $\mathcal O(\log n)$ 的，总共修改就是 $\mathcal O(n \log^2 n)$ 的，可以看作初始化的时间复杂度，然后每次查询是 $\mathcal O(\sqrt n \log n)$ 的。