360建设网站免费下载,2003配置网站与2008的区别,玉林做网站,专门做电子书的网站对于两个定义域为整数的函数F(x)和f(x); 若有: 然后F(x)可以快速求出#xff1b; 如何用F求解f呢#xff1f; 莫比乌斯反演#xff1a; 对于两个定义域为整数的函数F(x)和f(x); 若有: 则有#xff1a; 其中μ(x)为莫比乌斯函数#xff0c;其定义为#xff1a; 对于#… 对于两个定义域为整数的函数F(x)和f(x); 若有: 然后F(x)可以快速求出 如何用F求解f呢 莫比乌斯反演 对于两个定义域为整数的函数F(x)和f(x); 若有: 则有 其中μ(x)为莫比乌斯函数其定义为 对于pi为质数 若对于任意i存在ki1,则μ(x)0 否则若质因子的个数为偶数则μ(x)1 若质因子的个数为奇数则μ(x)-1 有了这个定义之后 为什么这是对的呢 莫比乌斯函数有如下性质 μ(1)1; 证明 观察上式其含义为x的所有因子的μ和 若x有重复质因子则di可能有重复质因子 但这样的话μ(di)为零 把μ为0的部分放在一边 剩下各自不含重复质因子的di了 设x有k种质因子 则设 显然有 于是 多项式定理杨辉三角 带入x-1,a1得证 于是莫比乌斯函数有了这样的性质 这可以用来证明莫比乌斯反演 即 证明 发现d的集合完全等于k的集合 对于每一个k,考虑f(k)对答案的贡献 发现在上式中 当即时 f(k)对答案贡献f(k)·μ(d) 于是 由莫比乌斯函数的性质可知 于是 得证 莫比乌斯反演的另一种形式 若有 则有 证明思路大同小异省去 莫比乌斯函数的求法 莫比乌斯函数是积性函数易证 于是可线性筛求解 代码如下: void prime(){int i,j;vis[1]true;mob[1]1;for(i2;iMAXN;i){if(!vis[i])pri[cnt]i,mob[i]-1;for(j1;jcntpri[j]*iMAXN;j){vis[i*pri[j]]true;if(i%pri[j])mob[i*pri[j]]-mob[i];else{mob[i*pri[j]]0;break;}}}
} 转载于:https://www.cnblogs.com/nietzsche-oier/p/6821915.html
