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
Maybe coz you have a strong knowledge in many topics, but not in sieve (like me), its solution using sieve looks very 1700 :)
I don't know if it is better. But Look at my submission 293137515. without using sieve and simple marking solution.
Read solution 2 in the tutorial, its easier. In fact, we can do it without sets and just using vectors 292960644
The main difficulty was reducing the condition in the statement to $$$a_j \nmid a_i$$$ if $$$j \mid i$$$
I knew that this condition was necessary, but in contest I just guessed that it was sufficient and proceeded based on that. I'm pretty sure many others did the same.
I have a fairly simple solution for it. To make you understand better, I have explained everything from getting the intuition, coming up with the claims, proving them, constructing the algorithm and handling the edge cases as comments in a very clean and beginner friendly code.
You can check it here — 295494155