算法学习-莫比乌斯反演

发布时间：2020-12-13 20:43:07 所属栏目：PHP教程来源：网络整理

导读：写在前面必须把更多的精力放在文化课上了,所以这段时间的学习和数学相干的比较多,希望可以对文化课有帮助. 莫比乌斯反演公式 g ( n ) = ∑ d | n f ( d ) ? f ( n ) = ∑ d | n μ ( d ) g ( n d ) 基础知识 μ 函数 f ( n ) = ? ? ? 1 , ( ? 1 ) k , 0 , n

写在前面

必须把更多的精力放在文化课上了,所以这段时间的学习和数学相干的比较多,希望可以对文化课有帮助.

莫比乌斯反演公式

$g (n) = \sum d | n f (d) ? f (n) = \sum d | n μ (d) g (n d)$ $g(n)=sum_{d|n}f(d)Rightarrow f(n)=sum_{d|n}mu(d)g(frac n d)$

基础知识

$mu$ 函数
$f (n) = ? ? ? 1, (? 1) k, 0, n = 1 n = p 1 ? p 2 ? . . . ? p k n = o t h e r s$ $f(n) = egin{cases} 1,& n=1 (⑴)^k,& n=p_1*p_2*...*p_k 0,&n=others end{cases}$
$mu$ 函数是积性函数,由于当 n 是质数时 $mu(n)=(⑴)^1=⑴$ ,所以可以通过筛法求出 $mu$ 函数.

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)=sum_{d|n}f(d)$
求证 $f(n)=sum_{d|n}mu(d)g(frac n d)$
证明
$f (n) = \sum d | n μ (d) g (n d) = \sum d | n μ (d) \sum k | n d f (k) = \sum d | n \sum k | n d f (k) ? μ (d)$ $f(n)=sum_{d|n}mu(d)g(frac n d)=sum_{d|n}mu(d)sum_{k |frac n d}f(k)=sum_{d|n}sum_{k|frac n d}f(k)*mu(d)$
然后的1步让我很头疼,要把 $f(k)$ 提出来,统计 $f(k)$ 所乘的 $mu(d)$ 的和.
仔细视察, $k$ 的取值范围就是 $n$ 的所有因子. 如果 $f(k)$ 要和 $mu(d)$ 相乘,那末满足的关系是 $k|frac n d$ ,也就是 $k*m=frac n d$ ,变换1下情势就得到 $d*m=frac n k$ ,即 $d|frac n k$ . 也就是 f(k)（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!