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