Unable to understand Hackerearth's HourStorm #1's problem complex gcd's editorial

Revision en1, by roll_no_1, 2018-07-16 16:08:17

I recently participated in HourStorm #1 on hackerearth and during competition time, just managed to solve the last problem partially. Now, I decided to upsolve the problems starting with the first one, but I could not understand the editorial and the author's solution. To clarify my point that I am not trying to ask this without trying myself to understand the editorial, these are the few points that I did not understand:

  • The editorialist says to fix gcd(Ai, Aj), but I do not know how to do that, how can we fix the gcd, if we don't know all pairwise gcd s that exist without iterating over all pairs.

  • The line: An element Ai is inserted in the set as many times as the number of divisors of Bi. ( Even in his solution, the author iterates over all divisors of Bi, and pushes them at the back of the list p[Ai], I do not understand why he did this).

  • The author's solution: Frankly, I understood almost no part of the author's given solution. I mentioned one point in the previous point, and then I saw that he looped i over from mx_value downto 1, and considered every multiple of i. I did not understand why he did that, and what he did in those loops.

P.S. : Sorry, if the above points sound too nooby, but I don't know, whether only I am having troubles understanding it, or did the author omit some details which might be obvious to more experienced coders.

Tags #help, #editorial, #hackerearth, #hourstorm


  Rev. Lang. By When Δ Comment
en1 English roll_no_1 2018-07-16 16:08:17 1467 Initial revision (published)