程序员人生网站导航

算法学习-莫比乌斯反演

栏目：php教程时间：2015-06-06 08:18:51

写在前面

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

莫比乌斯反演公式

$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)

------分隔线----------------------------

上一篇 在Mac下配置php开发环境：Apache+php+MySql

下一篇 hdu 1569 方格取数(2) 网络流最大点权独立集

------分隔线----------------------------