莫比乌斯函数的原式是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;
}