莫比乌斯函数入门
之前遇到过很多次莫反的题，但是每次做完就忘了，云里雾里，所以写一篇来好好记忆一下，下次再忘了就回来看看。
内容和OIWIKI有很大部分的重叠，但是更偏向结论和做法，同时舍弃了一些看不懂的。
莫比乌斯函数定义:
\[\mu(n)=\begin{cases}
1 & n=1 \\
0 & n含有平方因子(因子中有平方数) \\
(-1)^k & k为n本质不同的质因子个数
\end{cases}
\]
性质
\(\mu(n)\)是积性函数
积性函数
\[设函数为f(ab)，则f(ab) = f(a)\times f(b)，且a⊥b(a，b互质)
\]
性质
\[\sum_{d|n}\mu(d)=\begin{cases}
1 & n=1 \\
0 & n\ne 1 \\
\end{cases}
\]
\(n\)所有的因子的函数和的性质
证明
设
\[n = \prod_{i=1}^{i\leq k}p_i^{c_i}，n' = \prod_{i=1}^{i\leq k}p_i
\]
则
\[\sum_{d|n}\mu(d) = \sum_{d|n'}\mu(d)
\]
解释
容易发现\(n\rq\)的所有\(d\)，\(n\)是都有的，发现
\[d_i = \prod_{p_i\in P}p_i
\]
证明，若
\[d_i\times p_l = \prod_{p_i \in P}p_i \times p_l
\]
若\(p_l\)出现在\(P\)之中，则\(\mu(d_i\times P-l)=0\)
若\(p_l\)不出现在\(P\)之中，\(\mu(d_i\times P-l)\)会在其它情况中被枚举
所以第一个式子是成立的，再者
\[\sum_{d|n\rq}\mu(d) = \sum_{i=0}^{k}C_k^i(-1)^i
\]
根据二项式定理
\[(a+b)^n = \sum_{i=0}^{n}C_n^ia^ib^{n-i}
\]
为上面的式子添加一个\(b=1\)得
\[\sum_{i=0}^{k}C_k^i(-1)^i = (1+(-1))^k = 0
\]
\[\sum_{d|n}\mu(d)=\begin{cases}
1 & n=1 \\
0 & n\ne 1 \\
\end{cases}
\]
利用
因为\(\mu\)是积性函数，所以可以线性筛
void getMu() {
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]] = 1;
if (i % p[j] == 0) {
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];//多一个质因数
}
}
}
补充结论
\[[gcd(i,hj)=1]=\sum_{d|gcd(i,j)}\mu(d)
\]
人话翻译:左边成立，右边为\(1\)，反之为\(0\)
证明:略
\[\varphi(x) = \sum_{d|x} d\mu(\frac{n}{d})
\]
莫比乌斯反演
\[f(x) = \sum_{d|x}g(d) \Longleftrightarrow g(x) = \sum_{d|x} \mu(\frac{x}{d})f(d)
\]
\[f(x) = \sum_{d|x}g(d) \Longleftrightarrow g(x) = \sum_{d|x} \mu(d)f(\frac{x}{d})
\]
这两条就是莫比乌斯反演的结论。
例题
P2522 [HAOI2011] Problem b
原问题相当于询问一个矩阵，用类似于二维前缀和的方式将其拆开，每一部分都是形如：
\[\sum_{i=1}^{i\leq n}\sum_{j=1}^{j \leq m} [gcd(i,j)==k]
\]
的样子，可以化简为：
\[\sum_{i=1}^{i\leq \lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{j \leq \lfloor \frac{m}{k} \rfloor } [gcd(i,j)==1]
\]
由之前的结论可得：
\[\sum_{i=1}^{i\leq \lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{j \leq\lfloor \frac{n}{k} \rfloor} \sum_{d|gcd(i,j)} \mu(d)
\]
我们枚举 \(d\)，再枚举 \(d\) 的倍数 ，可得：
\[\sum_{d=1} \mu(d) \sum_{i=1}^{i\leq \lfloor \frac{n}{k} \rfloor}[d|i]\sum_{j=1}^{j \leq \lfloor \frac{n}{k} \rfloor}[d|j]
\]
后面两部分都可以快速的算出，再得：
\[\sum_{d=1} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor
\]
容易发现现在已经可以 \(O(n)\) 解决单次问题了，但是由多组询问，我们预处理 \(\mu\) 前缀和并使用数论分块优化。 code
..
后面有时间了再更，就当入个门