ICPC Warmup mobius function

Let's talk about algorithms!

Moderator: Board moderators

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

ICPC Warmup mobius function

Post by Minilek »

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

Post by Per »

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

Post by little joey »

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:

Post by Minilek »

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

Post by Cosmin.ro »

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

Post Reply

Return to “Algorithms”