首先根据算术基本定理，得到
[ N=p_1^{c_1}p_2^{c_2}cdots p_n^{c_n}
]
定义
莫比乌斯函数为
[mu(N)=
left{egin{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}
ight.
]
简单来说，当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ÊÇÖÊÊý£¬ÖÊÒò×ÓÖ»Óб¾ÉíÒ»¸ö
for(register int j(2*i);j<=n;j+=i){
v[j]=1;
if((j/i)%i==0) mu[j]=0;//jÄÜÕû³ýÖÊÊýi^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 ackslash N} mu(d)=[n=1] （中括号的表达式是艾佛森约定，可以自己百度下）
]
证明:
当n=1,显然成立
当n>1,在n的所有因子中,莫比乌斯值不为零的只有所有质因子个数都为1，其中质因数为r个的因子数量有(inom{N}{r})
那么有
[sum_{d ackslash N} mu(d)= inom{n}{0} -inom{n}{1}+inom{n}{2}cdots (-1)^n inom{n}{n}=sum_{i=0}^n (-1)^i inom{n}{i}
]
至于正负号的，是容斥系数
根据二项式定理
[(x+y)^n=sum_{i=0}^n inom{n}{i} x^i y^{n-i}
]
令x=-1，y=1
有
[sum_{i=0}^n (-1)^i inom{n}{i} =0
]
证毕
2.对于任意正整数n有
[ sum_{d ackslash N} frac{ mu(d)} {d} = frac{varphi(N)}{N}
]
证明:
令(F(N)=N ,f(N)=varphi(N))，代入莫比乌斯反演公式即可
证毕
狄利克雷卷积
莫比乌斯反演
设(F(N)和f(N))是定义在非负整数集合上的两个函数,且有
[ F(N)=sum_{d ackslash N} f(N)
]
我们可以有
[egin{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}
]
于是我们有
[egin{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}
]
于是很容易通过观察得到
[egin{align}
F(N)&=sum_{d ackslash N} f(N) \
Downarrow \
f(N)&=sum_{d ackslash
N}mu(d)F(frac{N}{d})
end{align}
]
*证明
[1.从定义出发，一直推和式（推得要吐血，手上的资料要么有错要么看不懂，这需要和式基础十分牢固，大概跟做高考题那么牢固才推荐这个方法。）
2.狄利克雷卷积证明(这个比较漂亮)
**证明**
证毕
莫比乌斯反演还有第二种形式
]
egin{align}
F(n)&= sum_{n ackslash d} f(d)
Downarrow
f(n)&=sum_{n ackslash d} mu(frac{d}{n}) F(d)
end{align}
[**证明**
]
[证毕]