前端之家收集整理的这篇文章主要介绍了
算法学习-莫比乌斯反演，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
写在前面
- 必须把更多的精力放在文化课上了,所以这段时间的学习和数学相干的比较多,希望可以对文化课有帮助.
莫比乌斯反演公式
基础知识
- μ函数
f(n)=???1,(?1)k,0,@H_235_301@n=1n=p1?p2?...?pkn=ot@H_290_403@hers
- μ 函数是积性函数,由于当 n 是质数时 μ(n)=(?1)1=@H_399_502@?1,所以可以通过筛法求出 μ 函数.
mu[1] = 1;
for(i = 2; i <= n; i++) {
if(!vis[i]) {
prime[++c] = i;
mu[i] = -1;
}
for(j = 1; prime[j] * i <= n; j++) {
vis[prime[j] * i] = 1;
if(i % prime[j] == 0) {
mu[prime[j] * i] = 0;
break;
}
mu[prime[j] * i] = -mu[i];
}
}
莫比乌斯反演的证明
- 可以从后向前证明.
- 已知 g(n)=∑d|nf(d)
- 求证 f(n)=∑d|nμ(d)g(nd)
- 证明
f(n)=∑d|nμ(d)g(nd)=∑d|nμ(d)∑k|ndf(k)=∑d@H_502_993@|n∑k|ndf(k)?μ(d)
然后的1步让我很头疼,要把 f@H_301_1106@(k) 提出来,统计 f(k) 所乘的 μ(d)的和.
仔细视察,@H_502_1192@k 的取值范围就是 n 的所有因子. 如果 f(k) 要和 μ(d) 相乘,那末满足的关系是 k@H_721_1301@|nd,也就是 k?m=nd,变换1下情势就得到 d?m=nk,即 d|nk. 也就是 f(k)
