wantToImprove's blog

By wantToImprove, history, 8 years ago, In English

The question is this. http://codeforces.com/contest/547/problem/C Here is the link to the editorial of the contest. http://codeforces.com/blog/entry/18126

I understand till the part he talks about the inclusion and exclusion principle after that when he starts talking about the good numbers and present the new elegant formula out of thin air,my mind begins to wander.Someone please help me with the problem.Any help is appreciated.Thanks for reading.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have used a different approach to solve this problem, using simple mobius inversion. Here is my accepted code, i have commented it for better understanding.

http://codeforces.com/contest/547/submission/18179999

If you have trouble in understanding how to derive the inversion part, you should read this.

https://www.quora.com/profile/Surya-Kiran/Posts/A-Dance-with-Mobius-Function