从积性函数到莫比乌斯反演

今天学长给我们教了数论选讲，把里面的精髓提出来浅谈记录一下。顺便附上机房一位神仙对本文的注解

什么是数论？

摘自 百度：

数论是纯粹数学的分支之一，主要研究整数的性质。整数可以是方程式的解。有些解析函数中包括了一些整数、质数的性质，透过这些函数也可以了解一些数论的问题。

数论被高斯成为“数学皇后”，是一大必不可少的分支。

前置导入

积性函数

积性函数代指一类函数。若函数 $\operatorname{f}$ 满足对于两个互质的数 $a,b$，$\operatorname{f}(a)\times \operatorname{f}(b)=\operatorname{f}(ab)$，则 $\operatorname{f}$ 为积性函数。

简单而言，对于一个函数 $\operatorname{f}(n)$，若 $\forall a,b\in \natnums^{+} \And \gcd(a,b)=1, \operatorname{f}(a)\times \operatorname{f}(b) = \operatorname{f}(ab)$，那么 $\operatorname{f}$ 是一个积性函数。

常见的积性函数有 $\varphi, \mu,\operatorname{id}$ 等等，下面将会提到一部分。

部分数学符号选讲

有高中数学基础的可以直接跳过。

$\prod$ 表示连乘，举例为：$\prod_{i=1}^N x_i$ ，意思是 $x_1\times x_2\times x_3\times \cdots \times x_N$。

$\sum$ 表示累加，举例为：$\sum_{i=1}^N x_i$ ，意思是 $x_1 + x_2 + x_3 + \cdots x_N$。

$\forall$ 表示“所有的”，$\exist$ 表示“存在”，$\And$ 表示“且”。

$\in$ 表示属于，$a\in A$ 表示元素 $a$ 属于集合 $A$。$\natnums^{+}$ 表示正整数集合，$\natnums$ 表示自然数集合（非负整数集合）。

$\left \lfloor \dfrac{a}{b} \right \rfloor$ 表示对 $\dfrac{a}{b}$ 的值向下取整。

$\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公约数，$\operatorname{lcm}(a,b)$ 为最小公倍数。

$\mid$ 表示整除，$a\mid b$ 表示 $b$ 是 $a$ 的倍数，$\nmid$ 表示不整除，$a\nmid b$ 表示 $b$ 不是 $a$ 的倍数。

诸如 $[a=b]$ （即方括号内放一个关系式）的形式的东西表示：若方括号内的式子为真，则该式子值为 $1$，反之则为 $0$。举个例子就可以简单地说明：
$[a<b]=\begin{cases} 1 (a<b) \\ 0 (a\geqslant b)\end{cases}$

其他未在此处出现的符号后文均会有说明。

关于本文

• 后文出现的 $p$ 均表示质数。
• 互质的定义为两个数的最大公约数为 $1$，本文将 $0^0$ 视为 $1$，$1$ 不是质数，也不视为完全平方数（注：一般认为 $0^0$ 没有意义，$1$ 是完全平方数）。
• 如果没有特殊说明，变量范围均为正整数范围内。
• 文章没有网站上的例题（实际上文中例题只有一个且只能展现莫比乌斯反演知识），如有需要自找题目。

欧拉函数选讲

欧拉函数的符号是 $\varphi$，我们记 $\varphi (n)$ 表示在 $[1,n]$ 的正整数中，与 $n$ 互质的数的个数，特别地，$\varphi(1)=1$。

欧拉函数的性质

欧拉函数是一个积性函数，具体地证明过程较为复杂，这里不多讨论。

欧拉函数有一些很美妙的性质。首先，根据定义，结合常识，因为质数与小于它的任何正整数都互质，所以有 $\varphi(p)=p-1$。类似地，对于一个质数的幂 ${p_i}^{k_i}$，因为一共有 ${p_i}^{k_i}$ 个数，其中只有 ${p_i}^{k_{i-1}}$ 个数与其有不为 $1$ 的公因数（也就是 $p_i$ 的倍数个数为那么多），因此我们还可以得出：$\varphi(p^k)=p^k-p^{k-1}$。这个式子做一个简单的变形，就可以得到：$\varphi(p^k)=p^k\times(1-\dfrac{1}{p})$。

下面我们来证明另一个性质：$\varphi(n)=n\times \prod(1-\dfrac{1}{p_i})$：显然对于任何一个 $n$，一定可以将其拆分为 $\prod{p_i}^{k_i}$ 的形式。考虑将这些东西全部乘起来，由于 ${p_1}^{k_1},{p_2}^{k^2},{p_3}^{k_3}\cdots$ 一定互质，又因为欧拉函数是积性函数，因此这些东西乘起来就是 $\varphi(n)$。因此有：

$\varphi(n)=\prod \varphi({p_i}^{k_i})$

$\varphi(n)=\prod [{p_i}^{k_i}\times (1-\dfrac{1}{p_i})]$

因为 $\prod [{p_i}^{k_i}\times (1-\dfrac{1}{p_i})]=\prod {p_i}^{k_i} \times \prod(1-\dfrac{1}{p_i})$，而前文提到 $\prod {p_i}^{k_i}=n$，因此最终得到：

$\varphi(n)=n\times \prod(1-\dfrac{1}{p_i})$

当然除此之外还有许多有趣的性质。如果你尝试算一算一个数 $n$ 的所有因数的欧拉函数值，就会发现它们加起来恰好等于 $n$。翻译成数学语言如下：$\sum_{d\mid n} \varphi(d)=n$。

一个简单的证明方法，就是你写下分母为 $n$ 的所有分数 $\dfrac{a}{n} (1\leqslant a\leqslant n)$：$\dfrac{1}{n},\dfrac{2}{n},\dfrac{3}{n},\cdots\dfrac{n}{n}$，然后给每个数约个分，约分后的分数中，分母就是所有 $n$ 的因数，分子就是所有与分母互质的数。它们一共有 $n$ 个，因此得证。

如果无法理解的话，可以以 $n=6$ 举个例子：$\frac{1}{6},\frac{2}{6},\frac{3}{6},\frac{4}{6},\frac{5}{6},\frac{6}{6}$，约分之后变成 $\frac{1}{6},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{5}{6},\frac{1}{1}$。分子就是所有与其分母互质的数，分母就是 $n$ 的所有约数。而显然这里一共有 $6$ 个数，因此 $\sum_{d\mid 6} \varphi(d)=6$。

欧拉函数和一个数有几个和它互质的数有关，如果给定一个 $n$，并统计出了 $[1,n]$ 之间所有与 $n$ 互质的数有哪些，你就会发现这些数字的和恰好等于 $\dfrac{n\times\varphi(n)}{2}$。这里还需要引入一个定理：

对于任意正整数 $i,n (i<n)$，若 $\gcd(i,n)=1$，则有 $\gcd(n-i,n)=1$。

因此我们列出 $n$ 的所有约数的时候，一定是最小的和最大的加起来为 $n$，第二小的和第二大的加起来为 $n$，第三小的和第三大的加起来为 $n$……一共有 $\dfrac{\varphi(n)}{2}$ 个这样的数对，每对的和为 $n$，因此总的和为 $\dfrac{n\times\varphi(n)}{2}$。

因此欧拉函数的常用性质有：

• 是积性函数。对于互质的两个数 $a,b$，有 $\varphi(a)\times\varphi(b)=\varphi(ab)$。
• 对于质数 $p$，$\varphi(p)=p-1$。
• 对于质数 $p$，$\varphi(p^k)=p^k-p^{k-1}=p^k\times(1-\dfrac{1}{p})$。
• 记 $n=\prod{p_i}^{k_i}$，其中 $p_i$ 为质数，$k_i\in\natnums^{+}$，有 $\varphi(n)=n\times \prod(1-\dfrac{1}{p_i})$。
• $\sum_{d\mid n} \varphi(d)=n$。
• $[1,n]$ 中所有与 $n$ 互质的数之和为 $\dfrac{n\times\varphi(n)}{2}$。

此外还有一些不常用的性质，例如：

• 若 $2\nmid n$，$\varphi(2\times n)=\varphi(n)$。
• 若质数 $p$ 满足 $p\mid n,p^2\mid n$，则 $\varphi(n)=\varphi(\frac{n}{p})\times p$。
• 若质数 $p$ 满足 $p\mid n,p^2\nmid n$，则 $\varphi(n)=\varphi(\frac{n}{p})\times(p-1)$。

不过第二个和第三个是线性筛求欧拉函数需要的式子，值得注意。

欧拉函数的运用延伸

我们常常遇到对一个答案取模运算的问题。如果计算中又出现了除法，我们就不得不进行求逆元的操作。通常我们会使用费马小定理。而费马小定理，其实就是欧拉定理的一种特殊形式。

对于互质的两个数 $a,m$，有 $a^{\varphi(m)}\equiv 1\pmod{m}$。（欧拉定理）

特别地，若 $m$ 为质数（记为 $p$），有 $a^{p-1}\equiv 1\pmod{p}$。（费马小定理）

对于求一个数的欧拉函数，显然只要分解其质因数，套用性质求解即可，当这个 $n$ 较大时显然瓶颈在分解质因数，因此认为其复杂度为 $\operatorname{O}(\sqrt{n})$ 的。但是如果我需要求 $[1,n]$ 的欧拉函数，显然 $\operatorname{O}(n\sqrt{n})$ 的做法过于暴力而不可取。

类比线性筛素数的做法，运用性质，可以得出如下的代码：

inline void GetPhi(int n){ // 求 [1,n] 的欧拉函数，顺便筛素数
    memset(isPrime, 1, sizeof(isPrime));
    // isPrime 是 bool，所以可以直接用 1 memset
    isPrime[1] = 0, phi[1] = 1;//1不是素数，phi(1)=1
    for(register int i = 2; i <= n; ++i){
        if(isPrime[i]){// 是质数
            Prime[++cnt] = i, // prime 统计质数，cnt 为质数个数
            phi[i] = i - 1;
        }
        for(register int j = 1; j <= cnt && i * Prime[j] <= n; ++j){
            // i*Prime[j] 不必超上限 n
            isPrime[ i * Prime[j] ] = 0;
            if(i % Prime[j] == 0){ // i中也含有Prime[j]这个因子
                phi[ i * Prime[j] ] = phi[i] * Prime[j]; 
                break; 
            }
            else phi[ i * Prime[j] ] = phi[i] * (Prime[j] - 1);
        }
    }
}

莫比乌斯函数选讲

莫比乌斯函数的符号是 $\mu$。$\mu(n)$ 的值计算方法如下：若 $\mu(n)$ 存在一个不为 $1$ 的完全平方数的因子，则 $\mu(n)=0$，否则，记 $\mu(n)$ 有 $m$ 个不同的质因子，则 $\mu(n)=(-1)^m$。

莫比乌斯函数的性质

莫比乌斯函数是积性函数，简单做一个其积性的证明：

对于互质的两个数 $a,b$，若其任意一个有完全平方数的因子，则它们一定满足以下两个中至少一个： $\mu(a)=0$，$\mu(b)=0$ 。显然 $a\times b$ 一定也含有完全平方数因子，因此 $\mu(a\times b)=0=\mu(a)\times\mu(b)$。特别地，$\mu(1)=1$。

若其有公共的质因子，则不满足 $a,b$ 互质的条件，情况不成立。则将 $a,b$ 含有的质因子个数表示为 $m_a,m_b$，则 $m_a+m_b$ 是 $a\times b$ 的因子个数。枚举 $m_a,m_b$ 的奇偶性验证即可。

除此之外，如果你求出 $n$ 的所有因子的莫比乌斯函数值，你会发现当 $n=1$ 时，它们的和为 $1$，否则为 $0$。转化为数学语言可以大概写成如下式子：$\sum_{d\mid n} \mu(d)=[n=1]$。

显然我们可以不用考虑那些 $\mu$ 值为 $0$ 的数。因此对于有 $k$ 个质因数的数字 $n$，由其中 $r$ 个质因数相乘可以得到的因数个数，就是 $\mu$ 值不为 $0$ 的因数个数。从 $k$ 个数选 $r$ 个，明显是组合数，一共有 $C_k^r$ 个。

考虑到 $r$ 的奇偶性决定这些因子的 $\mu$ 值的正负。根据定义可以得出：

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

根据二项式定理，有：$(x+y)^k=\sum_{i=0}^k C_k^i\times x^i\times y^{k-i}$。（注意这里的 $k$ 不是前面假设的 $k$ 个数）将 $x=-1,y=1$ 代入：

$0^k=\sum_{i=0}^k C_k^1\times (-1)^i\times 1^{k-i}=\sum_{i=0}^{k} (-1)^i \times C_k^i$

当 $n=1$ 时，$k=n-1=0$，有原式值为 $0^0=1$，否则原式值为 $0$。证毕。

以上就是莫比乌斯函数常用的一些性质。实际上还有部分性质，但是涉及到了后文写的内容，所以在这里姑且放着不提。

莫比乌斯函数的运用延伸

因为莫比乌斯函数一般都会用于莫比乌斯反演，也是后面提到的内容。因此这里只能简单提一下莫比乌斯函数的计算。同于欧拉函数，对于一个数 $n$，计算 $\mu(n)$ 只需要将其分解质因数，然后根据定义简单判断即可，单个数的计算是 $\operatorname{O}(\sqrt{n})$ 的。重点来看多个数的情况。

发现莫比乌斯函数的线性递推依然可以建设在线性筛的基础上。所以有如下代码：

void GetMu(int n){ // 求 [1,n] 的莫比乌斯函数，顺便筛素数
    memset(isPrime, 1, sizeof(isPrime));
    // isPrime 是 bool，所以可以直接用 1 memset
    isPrime[1] = 0, mu[1] = 1;//1不是素数，mu(1)=1
    for(register int i = 2; i <= n; ++i){
        if(isPrime[i]){// 是质数
            Prime[++cnt] = i, // prime 统计质数，cnt 为质数个数
            mu[i] = -1;
        }
        for(register int j = 1; j <= cnt && i * Prime[j] <= n; ++j){
            // i*Prime[j] 不必超上限 n
            isPrime[ i * Prime[j] ] = 0;
            if(i % Prime[j] == 0){ // i中也含有Prime[j]这个因子
                mu[i*prime[j]]=0;
                break;  // 这里不要更新 mu 值！！
            }
            else mu[ i * Prime[j] ] = mu[i] * (-1);
        }
    }
}

狄利克雷卷积与莫比乌斯反演

对于两个函数 $\operatorname{f},\operatorname{g}$，以及某个函数 $\operatorname{h}$，若对于 $\forall n\in \natnums^{+}$，有 $\operatorname{h}(n)=\sum_{d\mid n} \operatorname{f}(d)\times \operatorname{g}(\dfrac{n}{d})$，则记作 $\operatorname{f}\ast\operatorname{g}=\operatorname{h}$。其中 $\operatorname{h}$ 是 $\operatorname{f}$ 和 $\operatorname{g}$ 的狄利克雷卷积。

狄利克雷卷积

狄利克雷卷积满足交换律、结合律、分配律。（分配律即 $(\operatorname{f}+\operatorname{g})\ast\operatorname{h}=\operatorname{f}\ast\operatorname{h}+\operatorname{g}\ast\operatorname{h}$）。

此外还有一个重要的性质：两个积性函数的狄利克雷卷积也是积性函数。

专门出现一种称为“单位元”的函数 $\varepsilon$。“单位元”函数为 $\varepsilon=[n=1]$。对于任意函数 $\operatorname{f}$，有 $\operatorname{f}\ast\varepsilon=\operatorname{f}$。

除此之外，狄利克雷卷积和欧拉函数、莫比乌斯函数都有一些相关的性质。假设我们定义一个函数 $1$，对于任何一个数 $n$，有 $1(n)=1$。还有一种函数 $\operatorname{id}$，对于任何一个数 $n$，$\operatorname{id}(n)=n$。

先来探究 $1$ 函数的性质，容易发现若卷积的一个函数是 $1$（不妨设为 $\operatorname{g}$ 的那个函数），意味着 $\operatorname{f}$ 乘上的数都是 $1$，也就是它本身，因此有：

$\operatorname{f}\ast 1=\sum_{d\mid n} \operatorname{f}(d)$

右边这一块已经见到过很多次了，结合欧拉函数和莫比乌斯函数的性质，可以得出：

$\mu\ast 1=\sum_{d\mid n} \mu(d)=\varepsilon=[n=1]$

$\varphi\ast 1=\operatorname{id}$

将第二个等式左右两边同时乘上一个 $\mu$，有：$\varphi\ast 1\ast\mu=\operatorname{id}\ast\mu$，将第一个等式代入，得到 $\varphi\ast\varepsilon=\operatorname{id}\ast\mu$，又因为单位元矩阵乘任何函数，函数不变。因此得到一个重要的结论，印证着 $\varphi,\mu,\operatorname{id}$ 的关系：

$\mu\ast\operatorname{id}=\varphi$

同时简单变形还可以得到欧拉函数和莫比乌斯函数两者的关系：

$\varphi(n)=\sum_{d\mid n} \mu(d)\times\dfrac{n}{d}$

莫比乌斯反演

在狄利克雷卷积的基础上，接着来探究这样一个性质：

记函数 $\operatorname{F},\operatorname{f}$ 满足 $\operatorname{F}(n)=\sum_{d\mid n} \operatorname{f}(d)$，则有 $\operatorname{F}\ast\mu=\operatorname{f}$。

推导过程也相对简单，因为 $\operatorname{F}(n)=\sum_{d\mid n}\operatorname{f}(d)$，得到 $\operatorname{F}=1\ast\operatorname{f}$。等式两边同时乘上一个 $\mu$，有 $\operatorname{F}\ast\mu=1\ast\mu\ast\operatorname{f}=\varepsilon\ast\operatorname{f}=\operatorname{f}$。

因此可以得出莫比乌斯反演的式子：

$\operatorname{F}(n)=\sum_{d\mid n} \operatorname{f}(d)\Rightarrow\operatorname{f}(n)=\sum_{d\mid n}\operatorname{F}(d)\ast\mu(\dfrac{n}{d})$

$\operatorname{F}(n)=\sum_{n\mid d} \operatorname{f}(d)\Rightarrow\operatorname{f}(n)=\sum_{n\mid d}\operatorname{F}(d)\ast\mu(\dfrac{d}{n})$

莫比乌斯反演有什么用呢？事实上它的作用就是化简我们的推导式子，可以让一个本来不是很容易求解的函数，转换到一个容易求解的函数上进行运算。最后放上一道用上了莫比乌斯反演性质优化算法的例题作为烂尾：

例题：给定 $n,m,k$，求有多少个数对 $(x,y)$，满足 $1\leqslant x\leqslant n,1\leqslant y\leqslant m$，且 $\gcd(x,y)=k$。

不难得出我们需要求的结果其实就是 $\sum_{i=1}^{n}\sum_{j=1}^{m} [\gcd(i,j)=k]$。

求一对数的最大公约数为 $k$ 的相对难处理，我们可以将其转化为求最大公约数为 $1$的情况。如果一对数 $(i,j)$，其中 $i\leqslant\left \lfloor \dfrac{n}{k} \right \rfloor,j\leqslant\left \lfloor \dfrac{m}{k} \right \rfloor$，且 $\gcd(i,j)=1$，不难得出 $i\times k\leqslant n,j\times k\leqslant m$，且有 $\gcd(i,j)=k$。

进一步利用莫比乌斯反演的性质：$\sum_{d\mid n} \mu(d)=[n=1]$，所以总的答案转化为：

$\begin{aligned} Ans & =\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor} [\gcd(i,j)=1] \\ & =\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}\sum_{d\mid\gcd(i,j)} \mu(d) \\ & =\sum_{d=1}^{\left \lfloor \frac{\min(n,m)}{k} \right \rfloor}\left \lfloor \frac{n}{kd} \right \rfloor\left \lfloor \frac{m}{kd} \right \rfloor \mu(d) \end{aligned}$

这样就可以 $\operatorname{O}(n)$ 地求解这个问题了，不难发现如果不用上莫比乌斯反演或其性质，即使 $\gcd$ 可以 $\operatorname{O}(1)$ 算出来，整体复杂度也是 $\operatorname{O}(n^3)$ 的，整体优化十分可观。