ICPC Warmup mobius function

Minilek · Post by **Minilek** » Sun Oct 03, 2004 3:38 pm

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 non-square-free numbers there are less than i, but how do you deal with checking how many sqyare-free numbers less than i have a positive/even number of prime factors?

Per · Post by **Per** » Sun Oct 03, 2004 5:53 pm

You need to find mu(i) for all i from 1 to n. (After that, finding M(n) is simple)

little joey · Post by **little joey** » Sun Oct 03, 2004 8:57 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.

Minilek · Post by **Minilek** » Mon Oct 04, 2004 2:40 am

Ah. Thanks for the responses. This is exactly the strategy I used, but after asking a friend he told me my way of calculating mu wasn't efficient enough (I actually factored each number from 1 to 1000000 instead of writing down a factor in the array when sieving).

Cosmin.ro · Post by **Cosmin.ro** » Sat Oct 09, 2004 6:33 pm

Is there a faster way to solve the task than n log n?