CJam (25 24 22 2221 bytes)
{:X!X{X\2*)%!4*+~)4*\-}/z}
This runs in pseudoquasilinear time* and uses the statement from the OEIS that
Moebius transform is period 4 sequence [ 4, 0, -4, 0, ...]. - Michael Somos, Sep 17 2007
The input 0
is obviously a special case (Möbius tranforms and annihilators don't go well together), but ended up only costing one char.
* Pseudo- because it's quasilinear in the value of the input, not the size of the input; quasi because it does Theta(n)
operations on integers of size on the order of n
; a b
-bit mod operation should take b lg b
time, so overall this takes Theta(n lg n lg lg n)
time.