莫比乌斯函数与反演

 莫比乌斯函数的原式是u(n)={1,n=1

　　　　　　　　　　　　　(-1)^r,n=p1*p2*p3*......*pr  其中p为不同的质数

                                              0,其他}

它有两种解法，分别是欧拉筛和杜教筛

下面给出欧拉筛的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7;
bool vis[N];int prime[N],Mob[N];
void Mobius_solve(){
	int cnt=0;
	vis[1]=1;Mob[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i]){
			prime[cnt++]=i;
			Mob[i]=-1;
		}
		for(int j=0;j<cnt;j++){
			if(prime[j]*i>=N)break;
			vis[prime[j]*i]=1;
			Mob[prime[j]*i]=(i%prime[j]?-Mob[i]:0);
			if(i%prime[j]==0)break;
		}
	} 
}
int main(){
	Mobius_solve();
	int n;cin>>n;
	cout<<Mob[n];
	return 0;
}