莫比乌斯反演-白红宇的个人博客

莫比乌斯反演

发布日期：2021-05-06 03:47:18 浏览次数：29 分类：原创文章

本文共 476 字，大约阅读时间需要 1 分钟。

首先莫比乌斯函数有个性质

证明：
①

n=1 时，不做多余说明。。。
②

n>1 ,根据唯一分解定理，可以分解

n=∏ki=1paii
对于那些含平方因子也就是存在

ai 不为1的数，它的函数值为0，对答案没有任何贡献。
所以我们来看看那些是互异素数乘积的数，每一个成为它约数的数是什么样的情况。
（1）若

d 中有0个质因子(

d=1 )，其函数值为1，这样的数有

C0k 个
（2）若有1个质因子，其函数值为-1，这样的数有

C1k 个
（3）若有2个质因子，其函数值为1，这样的数有

C2k 个

所以最后我们发现

∑d|nμ(d)=C0k−C1k+C2k−...+(−1)kCkk=∑ki=0(−1)iCik
怎么证明后面那个和式值为0？
二项式定理
(a+b)n=∑ni=0Cinaibn−i
令上面的 n=k,a=−1,b=1
得 ∑ki=0(−1)iCik=(−1+1)k =0.
该性质得证。

证明：

最后一个式子是由莫比乌斯函数的性质的出来的。。。

这就是莫比乌斯反演可以简化运算

上一篇：BZOJ1101: [POI2007]Zap 莫比乌斯反演

下一篇：BZOJ1803: Spoj1487 Query on a tree III

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！