Just how did so many solve this problem. I understand the rating is related to the number of people who solved it during the contest but I don't get it. Even with the editorial it seems so tough. Just what prerequisties should I have to solve these types of problems during contests?

Though I have to say I learnt a lot from the editorial. Building using given conditions, Sufficiency of a condition.

Is there a better way to solve than the given editorial?

Problem Link — Shohag Loves GCD