莫比乌斯函数和反演

首先根据算术基本定理，得到

\[ N=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n} \]

定义

莫比乌斯函数为

\[\mu(N)= \left\{\begin{matrix} 0 \qquad \exists \ i \in [1,n] \ c_i>1 \\ 1 \qquad n为偶数(这里的偶数定义包括0) \qquad \forall \ i \in [1,n] \ c_i=1 \\ -1 \qquad n为奇数 \qquad \forall \ i \in [1,n] \ c_i=1 \\ \end{matrix}\right. \]

简单来说，当N包含两个相同质因子时，莫比乌斯函数值就是0，比如12=223
当N包含的质因子两两不同时。若N有偶数个，则莫比乌斯函数值为1，反之为1。

若是求单个数的莫比乌斯函数，直接质因数分解。
要求1~n的莫比乌斯函数值，可以用埃氏筛和欧拉筛

埃氏筛
inline void mobius() {
	rep(i, 1, n) {
		mu[i] = 1;
		v[i] = 0;
	}
	rep(i,2,n){
		if(v[i]) continue;
		mu[i]=-1;///iê??êêy￡??êòò×ó??óD±?éíò???  
		for(register int j(2*i);j<=n;j+=i){
			v[j]=1;
			if((j/i)%i==0) mu[j]=0;//j?ü??3y?êêyi^2 
			else mu[j]*=-1
		}
	}
}
欧拉筛
inline void  Euler_mobius(int N) {
	mu[1] = 1;
	for(register int i(2); i < N; ++i) {
		if(!v[i]) {
			v[i] = 1;
			mu[i] = -1;
			prime[++cnt] = i;
		}
		rep(j, 1, cnt) {
			if(1ll * prime[j]*i > N || prime[j] > i) break;

			v[i * prime[j]] = prime[j];

			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			} else mu[i * prime[j]] = -mu[i];
		}
	}
}

性质
1.对于任意正整数n有

\[\sum_{d \backslash N} \mu(d)=[n=1] （中括号的表达式是艾佛森约定，可以自己百度下） \]

证明:
当n=1,显然成立
当n>1,在n的所有因子中,莫比乌斯值不为零的只有所有质因子个数都为1，其中质因数为r个的因子数量有\(\binom{N}{r}\)
那么有

\[\sum_{d \backslash N} \mu(d)= \binom{n}{0} -\binom{n}{1}+\binom{n}{2}\cdots (-1)^n \binom{n}{n}=\sum_{i=0}^n (-1)^i \binom{n}{i} \]

至于正负号的，是容斥系数

根据二项式定理

\[(x+y)^n=\sum_{i=0}^n \binom{n}{i} x^i y^{n-i} \]

令x=-1，y=1
有

\[\sum_{i=0}^n (-1)^i \binom{n}{i} =0 \]

证毕

2.对于任意正整数n有

\[ \sum_{d \backslash N} \frac{ \mu(d)} {d} = \frac{\varphi(N)}{N} \]

证明:
令\(F(N)=N ,f(N)=\varphi(N)\)，代入莫比乌斯反演公式即可
证毕

狄利克雷卷积

莫比乌斯反演

设\(F(N)和f(N)\)是定义在非负整数集合上的两个函数,且有

\[ F(N)=\sum_{d \backslash N} f(N) \]

我们可以有

\[\begin{align} F(1)&=f(1) \\ F(2)&=f(1)+f(2) \\ F(3)&=f(1)+f(3) \\ F(4)&=f(1)+f(2)+f(4) \\ F(5)&=f(1)+f(5) \\ F(6)&=f(1)+f(2)+f(3)+f(6) \\ F(7)&=f(1)+f(7) \\ F(8)&=f(1)+f(2)+f(4)+f(8) \\ \end{align} \]

于是我们有

\[\begin{align} f(1)&=F(1) \\ f(2)&=F(2)-F(1) \\ f(3)&=F(3)-F(1) \\ f(4)&=F(4)-F(2) \\ f(5)&=F(5)-F(1) \\ f(6)&=F(6)-F(3)-F(2)+F(1) \\ f(7)&=F(7)-F(1) \\ f(8)&=F(8)-F(4) \\ \end{align} \]

于是很容易通过观察得到

\[\begin{align} F(N)&=\sum_{d \backslash N} f(N) \\ \Downarrow \\ f(N)&=\sum_{d \backslash N}\mu(d)F(\frac{N}{d}) \end{align} \]

*证明

\[1.从定义出发，一直推和式（推得要吐血，手上的资料要么有错要么看不懂，这需要和式基础十分牢固，大概跟做高考题那么牢固才推荐这个方法。） 2.狄利克雷卷积证明(这个比较漂亮) **证明** 证毕 莫比乌斯反演还有第二种形式 \]

\begin{align}
F(n)&= \sum_{n \backslash d} f(d) \
\Downarrow \
f(n)&=\sum_{n \backslash d} \mu(\frac{d}{n}) F(d) \
\end{align}

\[**证明** \]

\[证毕\]