Moblus

bool check[maxn];  
LL prime[maxn],mu[maxn];  
int tot;

void Moblus()  
{  
    memset(check,true,sizeof(check));  
    mu[1]=1;  
    tot=0;  
    for(int i=2;i<maxn;i++)  
    {  
        if(check[i])  
        {  
            prime[tot++]=i; mu[i]=-1;  
        }  
        for(int j=0;j<tot;j++)  
        {  
            LL ij=prime[j]*i;  
            if(ij>maxn) break;  
            check[ij]=false;  
            if(i%prime[j]==0)  
            {  
                mu[ij]=0; break;  
            }  
            else mu[ij]=-mu[i];  
        }  
    }  
}