## ICPC Warmup mobius function

Moderator: Board moderators

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

### 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 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
You need to find mu(i) for all i from 1 to n. (After that, finding M(n) is simple)

little joey
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.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
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
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
Is there a faster way to solve the task than n log n?