莫比乌斯反演 学习笔记

莫比乌斯反演

• 定义莫比乌斯函数(mu(n))，将(n)唯一分解，得(n=prodlimits_{i=1}^k p_i^{c_i}),则有

[mu(n)=left{egin{aligned}(-1)^k if squarefree \0 ohterwise\end{aligned} ight. ]

特殊的，(mu(1)=1).

(squarefree) 表示对(n)，(forall c_i=1).

形象化的说，当(n)的质因子次数超过(1)时，(mu(n)=0)，当(n)的质因子个数为偶数时,(mu(n)=1)，为奇数时,(mu(n)=-1).

---

性质

1. (mu)是积性函数，即(mu(xy)=mu(x) cdot mu(y),if x perp y).

   证明：代入定义式就好了啦

2. (sumlimits_{d|n} mu(d)= [n=1])

   ([x])为布尔表达式，(x)为真时返回(1)，否则返回(0)

   证明：若(n>1)，不考虑为(0)约数，即考虑(n'=prodlimits_{i=1}^kp_i)的所有因数就可以了，显然，贡献为

   [sum_{i=1}^k (-1)^iinom{k}{i} ]

   利用(inom{m}{n}=inom{m-1}{n}+inom{m-1}{n-1})将后面拆开，发现会消掉就等于(0)啦

3. (varphi(n)=sumlimits_{d|n} mu(d) imes frac{n}{d})

   要用狄利克雷卷积进行证明，窝不会，先咕咕

---

反演

若有定义域均为正整数的函数为(g(x),f(x))满足(g(x)=sumlimits_{d|n}f(d))，则$$f(n)=sum_{d|n}mu(d)g(frac{n}{d})$$

证明:

[sum_{d|n} mu(d)g(frac{n}{d}) ]

[=sum_{d|n}mu(d)sum_{p|frac{n}{d}}f(p) ]

[=sum_{d|n}f(d)sum_{p|frac{n}{d}}mu(p) ]

[=f(n) ]

交换两个求和要自己理解理解，倒数第二步用了性质(1).

---

事实上用这个公式的更多

[ ext{若}g(n)=sum_{n|d}^{upper}f(d), ext{则}f(n)=sum_{n|d}^{upper}mu(frac{d}{n})g(d) ]

证明:

[ ext{设} k=frac{d}{n} ]

[sum_{k=1}^{upper'}mu(k)g(nk) ]

[=sum_{k=1}^{upper'}mu{(k)}sum_{nk|p}^{upper'}f(p) ]

[=sum_{n|p}^{upper'}f(p)sum_{k|{frac{p}{n}}}^{upper'}mu(k) ]

[=f(n) ]

这个求和交换也理解理解

---

• 简单的例子

给定(a,b,d)，求(sumlimits_{i=1}^asumlimits_{j=1}^b[gcd(i,j)=d])

[ ext{设}f(d)=sumlimits_{i=1}^asumlimits_{j=1}^b[gcd(i,j)=d],g(d)=lfloorfrac{a}{d} floorlfloorfrac{b}{d} floor ]

在意义上，(f(d))为(gcd=d)的二元组个数，(g(d))为(gcd)是(d)的倍数的个数

显然有

[g(n)=sum_{n|d}^{min(a,b)}f(d) ]

由第二类反演

[f(n)=sum_{n|d}^{min(a,b)}mu(frac{d}{n})g(d) ]

[=sum_{k=1}^{min(lfloorfrac{a}{n} floor,lfloorfrac{b}{n} floor)}mu(k)g(nk) ]

[=sum_{k=1}^{min(lfloorfrac{a}{n} floor,lfloorfrac{b}{n} floor)}mu(k)lfloorfrac{a}{kn} floorlfloorfrac{b}{kn} floor ]

预处理完(mu)之后，我们就可以利用整除分块把单次的复杂度降到(O(sqrt a + sqrt b))啦