参考资料
定义
[f(n)=sum_{d|n}g(d) Rightarrow g(n)=sum_{d|n} mu(d)f(frac{n}{d}).
]
更常用的：$$f(n)=sum_{n|d}g(d) Rightarrow g(n)=sum_{n|d} mu(frac{d}{n})f(d).$$
其中 (mu(n)) 是莫比乌斯函数，它的定义是：
- (mu(n)=1) 当 (n=1)。
- (n=p_1p_2p_3 cdots p_k)，其中 (p_i) 互不相同，则 (mu(n)=(-1)^k)。
- 其它情况，(mu(n)=0)。
常用性质
- 对任意正整数 (n) 有：[sum_{d|n}mu(d)=egin{cases} 1 & n=1 \ 0 & n>1end{cases}. ]
- （很少用）对任意正整数 (n) 有：[sum_{d|n}frac{mu(d)}{d}=frac{varphi(n)}{n}. ]
证明
对性质1的证明
(n=1) 时答案显然。
(n > 1) 时，设 (n=p_1^{a_1}p_2^{a_2} ldots p_k^{a_k})，在 (n) 的所有因子中，若 (mu) 不为0，这些因子的质因子次数为1或0。则
[sum_{d|n}mu(d)=C_k^0-C_k^1+C_k^2+cdots+(-1)^kC_k^k=sum_{i=0}^k(-1)^iC_k^i.
]
二项式定理，((x+y)^n=sum_{i=0}^nC_n^ix^iy^{n-i})。令(x=-1,y=1)，证毕。
对定义1的证明
欲证 (g(n)=sum_{d|n} mu(d)f(frac{n}{d}))。
有
[egin{align} sum_{d|n} mu(d)f(frac{n}{d}) &= sum_{d|n}(mu(d) cdot sum_{e|frac{n}{d}}g(e)) \&= sum_{d|n}sum_{e|frac{n}{d}}(mu(d) cdot g(e)) .end{align}
]
分别根据定义和分配律。
可以发现，这是所有满足 ((de)|n) 的 (mu(d) cdot g(e)) 之和。
所以可以交换sum，变成
[egin{align} sum_{d|n} mu(d)f(frac{n}{d}) &= sum_{e|n}sum_{d|frac{n}{e}}(mu(d) cdot g(e)) \ &= sum_{e|n}(g(e) cdot sum_{d|frac{n}{e}}mu(d))end{align}
]
最后一个根据分配律逆定律得来。
只有当 (n/e=1) 也就是 (e=n) 的时候 (sum_{d|frac{n}{e}}mu(d))才为1，其余时候都为0。
于是 (sum_{d|n} mu(d)f(frac{n}{d}) = g(n))。证毕。
对定义2的证明
欲证 (g(n)=sum_{n|d} mu(frac{d}{n})f(d))。
记(k=d/n)。 以下证明省略 (k) 的上届（视题而定）。
[egin{align} sum_{n|d} mu(frac{d}{n})f(d) &=sum_{k=1}mu(k)f(nk) \ &= sum_{k=1}(mu(k)sum_{nk|t}g(t)) \ &= sum_{n|t}(g(t)sum_{k|frac{t}{n}}mu(k)). end{align}
]
只有当 (t/n=1) 也就是 (t=n) 的时候 (sum_{k|frac{t}{n}}mu(k))才为1，其余时候都为0。
于是 (sum_{n|d} mu(frac{d}{n})f(d)=g(n))。证毕。
实用意义
主要是用于当 (g(x)) 比较不好搞但是其“倍数和”或者是“约数和” (f(x)) 比较好搞的时候。
一些代码
线性筛莫比乌斯函数
void shai(){
memset(isp, true, sizeof(isp));
isp[0] = isp[1] = false;
mu[1] = 1;
for(int i=2; i<=100000; i++){
if(isp[i]) pri[++cnt] = i, mu[i] = -1;
for(int j=1; j<=cnt; j++){
if(i*pri[j]>100000) break;
isp[i*pri[j]] = false;
if(i%pri[j]==0){
mu[i*pri[j]] = 0;
break;
}
mu[i*pri[j]] = -mu[i];
}
}
}
例题
hdu 1695