11 莫比乌斯函数
尝试按照《具体数学》的顺序引入莫比乌斯反演。
11.1 引入
莫比乌斯函数 \(\mu(m)\) 是根据 19 世纪的数学家奥古斯特·莫比乌斯命名的，他还发现了著名的莫比乌斯带，\(\mu(m)\) 对所有整数 \(m \ge 1\) 由等式
\[\sum_{d \mid m} \mu(d) = [m=1] \]来定义。
这个式子实际上是一个递归式，左边的 \(\mu(m)\) 和某些满足 \(d \lt m\) 的 \(\mu(d)\) 的值组成的和式。我们有相继带入前面 \(m\)，从而得到前面的值：\(1,-1,-1,0,-1,1,-1,0,0,1,-1,0,\cdots\)。
在 1857 年，Richard Dedekind 和 Joseph Liouville 注意到了如下重要的 “反演原理”。
\[g(m) = \sum_{d \mid m} f(d) \Longleftrightarrow f(m) = \sum_{d \mid m} \mu(d) g(\frac m d) \]这就是我们熟知的 莫比乌斯反演。
发现这个东西的证明是容易的：如果 \(g(m) = \sum_{d \mid m} f(d)\)，那么
\[\begin{aligned} \sum_{d \mid m} \mu(d) g(\frac m d) & = \sum_{d \mid m} \mu (\frac m d) g(d) \\ & = \sum_{d \mid m} \mu(\frac m d) \sum_{k \mid d} f(k) \\ & = \sum_{k \mid m} \sum_{d \mid \frac m k} \mu(\frac m {kd}) f(k) \\ & = \sum_{k \mid m} \sum_{d \mid \frac m k} \mu(d) f(k) \\ & = \sum_{k \mid m} \left[ \frac m k =1 \right] f(k) \\ & = f(m) \end{aligned} \]反之，如果 \(f(m) = \sum_{d \mid m} \mu(d) g(\frac m d)\)，则
\[\begin{aligned} \sum_{d \mid m} f(d) & = \sum_{d \mid m} \sum_{k \mid d} \mu(k) g(\frac d k) \\ & = \sum_{d \mid m} \sum_{k \mid d} \mu(\frac d k) g(k) \\ & = \sum_{k \mid m} \sum_{d \mid {\frac m k}} \mu(d) g(k) \\ & = \sum_{k \mid m} \left[ \frac m k =1 \right] g(k) \\ & = g(m) \end{aligned} \]于是我们在这里就证明了 莫比乌斯反演。
而莫比乌斯反演还可以被表示成
\[g = f * 1 \Longleftrightarrow f = g * \mu \]现在回到最开始的那个式子，发现其实就是 \(\mu * 1 = \epsilon\)，由于我们之前证明的 积性函数的逆元也是积性函数，可以知道 \(\mu\) 必是积性函数。这样一来，只要我们计算出 \(\mu(p^k)\) 就能算出 \(\mu(m)\)。
当 \(m = p^k\) 时，根据最初的式子，我们知道对于所有 \(k \ge 1\)，都有
\[\mu(1) + \mu(p) + \mu(p^2) + \cdots + \mu(p^k) =0 \]由此推出
\[\mu(p) = -1 ; \quad \mu(p^k) =0,k \gt 1 \]于是，我们就推出了 \(\mu\) 的定义式
\[\mu(m) = \begin{cases} 1 & m=1 \\ 0 & m 含有平方因子 \\ (-1)^k & k 为 m 的本质不同质因子个数，即 \omega (m) \end{cases} \]如果我们把之前的欧拉反演视作 \(\varphi (m)\) 的递归式，就能应用莫比乌斯反演得到
\[\varphi (m) = \sum_{d \mid m} \mu(d) \frac m d \]也就是 \(\mu * \text{id} = \varphi\)，也对狄利克雷卷积逆元有了另一个方面的解释。
接下来我们尝试用容斥的角度来理解莫比乌斯函数。
设 \(g(n) = \sum_{n \mid d} f(d)\)，即 \(g(n)\) 是 \(f\) 在所有 \(n\) 的倍数处的取值和。现在已知 \(g\)，要求 \(f(1)\)。则 \(f(1)\) 等于 \(f\) 在 \(1\) 的倍数处的取值和，减去在质数处的取值和，但是多减去了在两个不同质数乘积处的取值和，一次要加上这些值，但是多加了在三个不同质数乘积处的取值和，以此类推。因此，若 \(n\) 为 \(k\) 个不同质数的乘积，则 \(f(1)\) 会收到 \(g(n)\) 系数为 \((-1)^k\) 的贡献，如下图。
就是对 \(\mathbb N\) 作容斥，得到贡献系数 \(\mu\)。
11.2 线性筛莫比乌斯函数
根据定义是，线性筛莫比乌斯函数是非常容易的。
mu[1]=1;
for(int i=2;i<=maxn;i++){
if(!vis[i]) p[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*p[j]<=maxn;j++){
vis[i*p[j]]=true;
if(i%p[j]==0) break;
mu[i*p[j]]=-mu[i];
}
}
11.3 常见技巧
对于 莫比乌斯反演，我们常常用式子
\[[\gcd(i,j) = 1] = \sum_{d \mid \gcd(i,j)} \mu(d) \]它把 \(\gcd(i,j)\) 带入了 \(n\)，还将 \(i,j\) 互质的条件转化为枚举 \(\gcd(i,j)\) 的约数 \(d\)，然后对 \(\mu(d)\) 求和。在 \(i,j\) 同样需要枚举的时候，可以先枚举 \(d\) 并计算合法的 \((i,j)\) 对数，这样 \(i,j\) 合法当且仅当 \(d \mid i,d \mid j\)，就把 \(i,j\) 独立开了。
于是我们就可以这样解决下面的式子：
\[\begin{aligned} \sum_{i=1}^n \sum_{j=1}^m \left[ \gcd(i,j) =1 \right] & = \sum_{i=1}^n \sum_{j=1}^m \sum_{d \mid \gcd(i,j)} \mu(d) \\ & = \sum_{d =1}^{\min(n,m)} \mu(d) \sum_{i=1}^n \sum_{j=1}^m \left[ d \mid i \land d \mid j \right] \\ & = \sum_{d=1}^{min(n,m)} \mu(d) \left \lfloor \frac n d \right \rfloor \left \lfloor \frac m d \right \rfloor \end{aligned} \]相当于对最大公约数为 \(d\) 的倍数进行了容斥：加上最大公约数为 \(1\) 的倍数的对数，减去最大公约数为 \(p_i\) 的倍数的对数，加上最大公约数为 \(p_ip_j(i \neq j)\) 的倍数的对数，以此类推。得到每个 \(d\) 的贡献系数就是莫比乌斯函数。
而这个式子是非常容易用整除分块完成。
$$ d(ij) = \sum_{x \mid i} \sum_{y \mid j} \left [ x \bot y \right] $$ 考虑单个质因子 $p$，再用中国剩余定理和并。设 $a = v_p(i)$ 即 $i$ 中含有质因子 $p$ 的数量，$b = v_p(j)$，则 $v_p(ij)= a+b$。对于 $ij$ 的约数 $d$，若 $v_p(d) \le a$，则令其对应 $v_p(x) = v_p(d),v_p(y)=0$，即所有都算在 $x$ 上面；若 $v_p(d) \gt a$，则令其对应 $v_p(x)=0,v_p(y) = v_p(d) -a$。容易发现这样会形成双射，因此可证得这一结论。
11.4 例题
接下来，我们来将一些例题，由于比较多，所以单独提出来了。部分例题会用到上面的常见技巧。
前面的一些例题中有些写得比较简略，有些可能是
标签：lf,frac,Theory,sum,Number,rf,prod,gcd From： https://www.cnblogs.com/H-W-Y/p/18203764/NumberTheory4