莫比乌斯函数定义

μ(n)={(−1)m0,,p1,p2...pm=1∃k|pk>1

性质1（积性函数）

μ(ab)=μ(a)∗μ(b)|gcd(a,b)=1

性质2

∑d|nμ(d)=0(n>1) 证明: 设 d=Πmi=1aipi 当 ∃k|pk>1 时 μ(d)=0 无需考虑 相当于n分解的因数选或不选求 μ 的和的问题 所以 ∑d|nμ(d)=∑mk=0Ckm(−1)k 根据二项式定理 (a+b)n=∑nk=0Cknakbn−k 把 a=−1,b=1 代入得 ∑d|nμ(d)=(1−1)m=0 特别的 n=1 时原式 =μ(1)=1 证毕

前缀和求法

M(N)=∑ni=1μ(i) =∑ni=1(∑d|iμ(d)−∑d|i,d=iμ(d)) =1−∑ni=1∑d|i,d=iμ(d) =1−∑ni=1(⌊Ni⌋−1)μ(i)

小的线性筛，大的递归(分段)

另外的性质

∑d|nϕ(d)=n 证明: 令 S={rn|r=1,2...n} 则 |S|=n 设 rn 最简形式为 cd 则 |S|=∑d|n[gcd(c,d)=1] 即 |S|=∑d|nϕ(d) 证毕

莫比乌斯反演

若 g(n)=∑d|nf(d) 则 f(n)=∑d|nμ(d)g(nd)

证明: ∑d|nμ(d)∑d′|ndf(d′) =∑dd′|nμ(d)f(d′) =∑d|nf(d)∑d′|ndμ(d′) 由函数性质2可得 当且仅当n/d=1时即n=d时 ∑d′|ndμ(d′)=1 否则 ∑d′|ndμ(d′)=0 所以原式 =f(n)

推论

若 g(n)=∑n|df(d) 则 f(n)=∑n|dμ(dn)g(d) 证明: ∑n|dμ(dn)g(d) = ∑n|dμ(dn)∑d|d′f(d′) = ∑n|d′f(d′)∑n|d|d′μ(dn) = ∑n|d′f(d′)∑k|d′nμ(k) 由函数性质2得d’=n时才有效 = f(n)

例题1

求i=1..n, j=1..m中gcd(i,j)=1的个数 f(k)=∑ni=1∑mj=1[gcd(i,j)=k] g(k)=∑ni=1∑mj=1[k|gcd(i,j)] 则 g(k)=∑k|df(d) f(k)=∑k|dμ(dk)g(d) =∑k|dμ(dk)⌊nd⌋⌊md⌋ =∑⌊min(n,m)k⌋p=1μ(p)⌊⌊nk⌋p⌋⌊⌊mk⌋p⌋ p=dk

扩展

∑ni=1∑mj=1[gcd(i,j)=prime] =∑np=1is[p]∑⌊np⌋i=1∑⌊mp⌋j=1[gcd(i,j)=1] =∑np=1is[p]∑⌊np⌋i=1∑⌊mp⌋j=1∑d|i,d|jμ(d) 注: d|i,d|j等价于d|gcd(i,j) =∑np=1is[p]∑⌊np⌋d=1μ(d)⌊npd⌋⌊mpd⌋ =∑nk=1g(k)⌊nk⌋⌊mk⌋ g(k)=∑p|kis[p]μ(kp) 可知 g(p′k)=∑p|kp′is[p]μ(kp′p) ①当p’|k时 g(p′k)={μ(k)0,p=p′,p!=p′ 所以 g(p′k)=μ(k) ②当 p′/|k 时 g(p′k)=⎧⎩⎨⎪⎪μ(k)−μ(kp),p=p′,p!=p′ p!=p′ 部分的求和就是g(k) 所以 g(p′k)=μ(k)−g(k)