Artifact daa89aa8f6eb3e5c0aa30d56173dc0c713fccef3

• File _lib/numeric/mebius.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/numeric/mebius.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

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