hell_hacker's blog

Help in Gym problem Coprimes
By hell_hacker, history, 6 years ago, In English

In this problem Coprimes I saw some solutions using mobius function. Can anyone throw some light on how mobius function can be used in this problem. Thank you!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it
  1. Given a simple array of numbers (size=N), observe how ans can be calculated for the whole array itself firstly, You have NC2 pairs to choose from. consider all numbers in array divisible by 2 suppose there are mtwo such numbers, then you know you have lost mtwoC2 pairs which could have been the ans.similarly for mthree such numbers (divisible by 3) you have lost mthreeC2 pairs...., obviously you are overcounting because divisible by 2 and divisible by 3 numbers might overlap, so mobius function precisely helps in getting the right count adjusting here and there. if you know mobius function i have given sufficient information to help you figure out the rest. final expression will look something like this NC2-(mtwoC2+mthreeC2+mfiveC2....)+(msixC2+..)
  2. As far as I have experienced, in a problem of sufficiently good difficulty, if the queries are being provided ordinarily as [l,r] without updates, intended solution 90% of the times uses offline answering of queries (MO's algorithm), if you know MOs you can figure out the solution from here on, just see if you have the ans for a range how will it change on adding or removing an element from range. This is what I can see from the first look at the problem, might be wrong. Thank You.
→ Reply