Mobius function

Möbius function

The Möbius function is multiplicative (i.e. μ(ab) = μ(a) μ(b) whenever a and b are coprime).
The sum of the Möbius function over all positive divisors of n (including n itself and 1) is zero except when n = 1:

Note

• Mobius wiki
• Mobius inversion

Code - Precomputation O(NlogN)

void precal(int maxn){
	mob.resize(maxn+1,2);
	mob[1]=1;
	for(ll i=2;i<=maxn;++i) if(mob[i]==2){
		if(i*i<=maxn) for(ll j=i*i;j<=maxn;j+=i*i) mob[j]=0;
		for(ll j=i;j<=maxn;j+=i){
			if(mob[j]==2) mob[j]=1;
			mob[j]=-mob[j];
		}
	}
}