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