Artifact daa89aa8f6eb3e5c0aa30d56173dc0c713fccef3
//-------------------------------------------------------------
// Mebius Function
// O( sqrt(N) )
//
// mebius(n) = 0 if n=0 mod p*p for some p
// mebius(n) = (-1)^k otherwise, where k is the number of n's prime factors
//
// properties:
// 1: mebius(nm) = mebius(n) mebius(m) if gcd(n,m)=1
// 2: f(n) = Sigma_{d|n} g(d)
// <=>
// g(n) = Sigma_{d|n} f(d)mebius(n/d)
//
// Verified by
// - CodeCraft '11 PSTR
//
// Further memoization or more might be needed.
//-------------------------------------------------------------
int mebius(int n)
{
int f = 1;
for(int q=2; q*q<=n; ++q)
if( n%q == 0 )
{
if( n%(q*q) == 0 )
return 0;
n /= q;
f *= -1;
}
if(n>1)
f *= -1;
return f;
}