莫比乌斯反演小结
感觉不是很难()
用途
求gcd，lcm，因数个数，因数和有关的求和问题。
前置芝士
莫比乌斯函数
这个自己百度
重要的只有\([n==1]=\sum_{d|n}\mu(d)\)
欧拉函数
同上。
有\(\phi(n)=\sum_{d|n}d\mu(\dfrac{n}{d})\)，证明：
线性筛&整除分块
同上。
规范的写法
\(f(n)=\sum_{d|n}g(d)\)
那么\(g(n)=\sum_{d|n}\mu(d)f(\dfrac{n}{d})\)
这个证明直接硬带即可。
\(\sum_{d|n}\mu(d)f(\dfrac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}g(k)=\sum_{k|n}g(k)\sum_{d|\frac{n}{k}}\mu(d)=\sum_{k|n}g(k)[\dfrac{n}{k}=1]=\sum_{k|n}g(k)[k=n]=g(n)\)
亦可使用狄利克雷卷积证明，这里不展开。
实际的用法
规范写法太麻烦了，实际上我们一般不会真的写出这个过程，只是交换求和顺序而已。
实际上，反演只是简化和式计算的方式而已，这点可以看看具体数学。
举几个例子吧。（不包含杜教筛）
1.\(\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\)
\[\begin{array}{l} \sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\\ =\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}d [gcd(i,j)=1]\\ =\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k|gcd(i,j)}\mu(k)\\ =\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{dk}\rfloor}\\ =\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{dk}\rfloor^2\\ =\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\sum_{d|T}d\ \mu(\frac{T}{d})\\ =\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\phi(T) \end{array} \]其中令\(T=dk\)。
2.\(\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)\)
\[\begin{array}{l} \sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)\\ =\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}dij [gcd(i,j)=1]\\ =\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j\sum_{k|gcd(i,j)}\mu(k)\\ =\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}i\sum_{j=1}^{\lfloor\frac{n}{dk}\rfloor}j\\ =\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2S_{\lfloor\frac{n}{dk}\rfloor}^2\\ =\sum_{T=1}^{n}T\ S_{\lfloor\frac{n}{T}\rfloor}^2\sum_{k|T}k\ \mu(k)\\ \end{array} \]其中\(S_i=\sum_{i=1}^{n}i\)。
注意别漏了\(k^2\)。
令\(f(n)=\sum_{k|n}k\mu(k)\)
可以直接\(O(nlogn)\)枚举倍数，但是此类积性函数的积也可以直接筛出。
有时候需要辅助数组。使用辅助数组甚至可以筛出某些非积性函数。
3.\(\sum_{i=1}^{n}\sum_{j=1}^{n}d(ij)\)
首先有引理\(d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\)。
简单证明：
设 \(p_k(k\in[1,n])\)为 \(ij\) 的质因子。
设\(i=\prod_{k=1}^{n}p_k^{a_k}，j=\prod_{k=1}^{n}p_k^{b_k}\)
那么对于任意\(u|ij\)，有\(u=\prod_{k=1}^{n}p_k^{c_k}\ (p_i\in prime，a_k,b_k,c_k\in N，c_k\leq a_k+b_k)\)
设\(s_1,s_2\)分别为\(u\)对应的\(x,y\)，初始为1。
对于质因子\(p_k\)，若\(c_k\leq a_k\)，则\(s_1\)乘上\(p_k^{a_k}\)，否则\(s_2\)乘上\(p_k^{c_k-a_k}\)。
注意到\(s_1,s_2\)始终互质，且我们对u和x,y建立了一一映射，证毕。
其中\(f(n)=\sum_{i=1}^{n}\lfloor\dfrac{n}{i}\rfloor\)。