莫比乌斯函数

//求单个值
ll getmob(ll a){
    ll x=a,tmp=a;
    int cnt=0,now=0;
    for(ll j=2;j*j<=x;j++){
        now=0;
        if(x%j==0){
            while(x%j==0) now++,x/=j;
            if(now>1) return 0;
            cnt++;
        }
    }
    if(x!=1) cnt++;
    return (cnt&1)?-1:1;
}
int getmu(int n)
{
    int v=1;
    for(int i=2;i*i<=n;i++)
     if(n%i==0)
     {
        v=-v;n/=i;
        if(n%i==0)return 0;
     }
    if(n!=1)v=-v;
    return v;
}


//最大可用范围[1,maxn),实际使用[1,maxn);
//初始化要求vis,mu至0,maxn
const int maxn;
int mu[maxn],sum[maxn],prime[maxn];
bool vis[maxn];
void mobius_ini(){
    mu[1]=1;
    prime[0]=0;
    for(int i=2;i<maxn;i++){
        if(!vis[i]){
            mu[i]=-1;
            prime[++prime[0]]=i;
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){
            vis[i*prime[j]]=true;
            if(i%prime[j])
                mu[i*prime[j]]=-mu[i];
            else{
                mu[i*prime[j]]=0;
                break;
            }
        }
    }
    for(int i=1;i<maxn;i++)sum[i]=sum[i-1]+mu[i];
}
/*
01: 1 02:-1 03:-1 04: 0 05:-1 06: 1 07:-1 08: 0 09: 0 10: 1 
11:-1 12: 0 13:-1 14: 1 15: 1 16: 0 17:-1 18: 0 19:-1 20: 0 
21: 1 22: 1 23:-1 24: 0 25: 0 26: 1 27: 0 28: 0 29:-1 30:-1 
31:-1 32: 0 33: 1 34: 1 35: 1 36: 0 37:-1 38: 1 39: 1 40: 0 
41:-1 42:-1 43:-1 44: 0 45: 0 46: 1 47:-1 48: 0 49: 0 50: 0 
51: 1 52: 0 53:-1 54: 0 55: 1 56: 0 57: 1 58: 1 59:-1 60: 0 
61:-1 62: 1 63: 0 64: 0 65: 1 66:-1 67:-1 68: 0 69: 1 70:-1 
71:-1 72: 0 73:-1 74: 1 75: 0 76: 0 77: 1 78:-1 79:-1 80: 0 
81: 0 82: 1 83:-1 84: 0 85: 1 86: 1 87: 1 88: 0 89:-1 90: 0 
91: 1 92: 0 93: 1 94: 1 95: 1 96: 0 97:-1 98: 0 99: 0 
*/