ICPC Warmup mobius function
Moderator: Board moderators
ICPC Warmup mobius function
Hey, what is the strategy for doing the mobius function problem efficiently? I see how to determine mu(i) efficiently, but i find M(i) to be the problem. I can see how many nonsquarefree numbers there are less than i, but how do you deal with checking how many sqyarefree numbers less than i have a positive/even number of prime factors?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
With the current limit of the problem (1000000) it is possible to precalculate all values of M(x), which makes it a trivial task. In my original statement the limit was much higher, but that would require longer runtimes and that is no longer possible during an online contest with the current judge.