莫比乌斯反演理解

学了下莫比乌斯反演，实质上mu函数是从容斥原理推出来的

详细的原理解读+例子讲解可以看博客 https://www.cnblogs.com/chenyang920/p/4811995.html

首先要了解狄利克雷卷积公式

　　 $(f * g) (n) = \sum_{d | n} f (d) * g (\frac{n}{d})$

一些常用的数论函数（积性函数）：

　　第一个是狄利克雷单位元，相当于常数1(可以参考线性代数里的单位矩阵)

　　1(n) = 1 是单位函数

　　Id(n) = n 是不变函数

关于一些性质和公式 https://www.cnblogs.com/Mychael/p/8744633.html

莫比乌斯反演

　(1)　 $F(n)=sum_{d|n}f(d)$ ====》 $f(n)=sum_{d|n}mu(d)F(frac{n}{d})$ 　　

$(f * g) (n) = \sum_{d | n} f (d) * g (\frac{n}{d})$

莫比乌斯的逆元：单位函数：u(n) * 1(n) = € (n)

证明 1：F(n)=(f*1)(n) ==> (F*u)(n) = (f*1*u)(n) = f(n) ==> $f(n)=sum_{d|n}mu(d)F(frac{n}{d})$

另外还有一种证明方法，个人认为更加直接硬核

其中第三个等号那里用了一下置换法

引理：∑d|n u(d）= € (n)

$(f * g) (n) = \sum_{d | n} f (d) * g (\frac{n}{d})$

然后推广到n=p1p2p3p4...pk,即n没有平方因子的情况

　　第一项g(n)的系数必定是1

　　g(n/pi)的系数必定是 -1=u(pi)

　　g(n/(pi*pj))的系数必定是 1=u(pi*pj)　　

　　利用容斥原理推导公式，依次类推，当u(n)，n为没有平方因子的数，k为n的质因子个数，u(n)=(-1)^n

再推广到有平方因子的情况

　　我们只考虑平方因子在的情况

　　g(n/(pi*pi))的系数是 0=u(pi*pi)

　　g(n/(pi*pi*pj))的系数是 0=u(pi*pi*pj)

　　根据容斥原理推导公式，当u(n),n有平方因子，则u(n)=0

关于莫比乌斯函数的两条性质

用二项式定理可证，实质还是容斥原理(莫比乌斯函数的逆元是单位函数也是这么来的)

不知道什么东西。。