|
之前一直没弄明白这个莫比乌斯反演是个什么，相关资料太过于开门见山，看了大佬的入门级别的讲解，才算是略懂一二 。
反演条件：
给定两个函数，一个是和函数F（x），一个是原函数f（x），其中，和函数为已知函数。
给定F（x）和f（x）的关系为F（n）的函数值等于所有能整除n的d所对应的f（d）的和。
而莫比乌斯反演就是根据已知的和函数求原函数的过程。
结果是f（x）=∑（所有能整除n的d或者能整除n的d）U（n/d或者d/n）*F（d）。
其中U（x）为莫比乌斯函数，若d=p1^e1*p2^e2……*pk^e^k（其中pi为质数，i=1,2...k）,则有：
1.当存在ei>2，i=1,2,...k的时候，U（d）=0。
2.当所有e均为1且k为偶数，则U（d）=1。
3.当所有e均为1且k为奇数，则U（d）=-1。
特别的，U（1）=1。
证明就不再孤陋寡闻了，莫比乌斯反演主要用于优化gcd的相关问题的求解，U（x）的线性筛法的代码如下：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define maxn 10010
using namespace std;
int mu[maxn];
int visit[maxn];
int prime[maxn];
int total;
void getmu(){
int i,j;
memset (visit,0,sizeof(visit));
mu[1]=1;
total=0;
for (i=2;i<maxn;i++){
if (!visit[i]){
prime[++total]=i;
mu[i]=-1;
}
for (j=1;j<=total&&prime[j]*i<maxn;j++){
visit[i*prime[j]]=1;
if (i%prime[j]){
mu[i*prime[j]]=-mu[i];
}
else {
mu[i*prime[j]]=0;
break;
}
}
}
}
int main(){
getmu();
}
| 
转播
