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