莫比乌斯筛和莫比乌斯反演证明

自己推了一下莫比乌斯反演
这种公式类的还是需要自己推过，但以免遗忘，特写此文
莫比乌斯函数求法(线性筛)：

void init(){mu[1] = 1;for (int i=2;i<maxm;++i){if(!st[i]) prime[cnt++] = i,mu[i] = -1;for(int j = 0;prime[j] * i<maxm;++j){st[prime[j]*i] = true;if (i%prime[j] == 0)break;mu[prime[j]*i] = -mu[i];}}for(int i=1;i<maxm;++i) sum[i] = sum[i-1] +mu[i];
}

当满足$F(n)$ $=$ ∑ d ∣ n f ( d ) \sum_{d|n}f(d) ∑d∣n​f(d)时
莫比乌斯反演公式：
$f(n)$ $=$ ∑ d ∣ n d ( n ) F ( n / d ) \sum_{d|n}d(n)F(n/d) ∑d∣n​d(n)F(n/d)
将$F(n/d)$用原公式代替得：
∑ d ∣ n d ( n ) F ( n / d ) \sum_{d|n}d(n)F(n/d) ∑d∣n​d(n)F(n/d) $=$ ∑ d ∣ n u ( d ) \sum_{d|n}u(d) ∑d∣n​u(d) ∑ k ∣ n / d f ( k ) \sum_{k|n/d}f(k) ∑k∣n/d​f(k)
由于$k$和$d$都是$n$的因子(这个可以自己代个常数n，一目了然)： ∑ d ∣ n d ( n ) F ( n / d ) \sum_{d|n}d(n)F(n/d) ∑d∣n​d(n)F(n/d) $=$ ∑ k / n f ( k ) \sum_{k/n}f(k) ∑k/n​f(k) ∑ d ∣ n / k u ( d ) \sum_{d|n/k}u(d) ∑d∣n/k​u(d)
最后由于莫比乌斯函数的性质，只有当$n/k=1$时 ∑ d ∣ n / k u ( d ) \sum_{d|n/k}u(d) ∑d∣n/k​u(d) 才为1，其他都为0，所以$n=k$， ∑ d ∣ n d ( n ) F ( n / d ) \sum_{d|n}d(n)F(n/d) ∑d∣n​d(n)F(n/d) $=$ ∑ 1 f ( n ) \sum_{1}f(n) ∑1​f(n) $=$ $f(n)$

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！