Mobius function

Möbius function

For any positive integer n, define μ(n) as the sum of the primitive nth roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:

• μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
• μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
• μ(n) = 0 if n has a squared prime factor.

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];
		}
	}
}