### AshrafSustS19's blog

By AshrafSustS19, history, 10 months ago, I wasn't happy with the time complexity of my solution. So, I was looking for a solution with improved time complexity. And I found this. This guy solved this problem by only checking the first 200 elements after each index and comparing GCD of each pair . He won with the power of probability!

His submission: 184781213

Test Case

Test Case result should be Yes. His solution prints No Comments (4)
 » 10 months ago, # | ← Rev. 2 →   What about picking $\min(n, 100)$ numbers randomly and then trying all possible pairs of them? Will it work? How to calculate the probability of getting it right?
•  » » No, would have worked during the contest, but further test cases have been added. 184857290
•  » » It doesn't work because you can construct an array with only one pair such that $\gcd(a_i, a_j) = 1$. In that case, the probability of both $i, j$ being chosen randomly is $(100 \cdot 99) / (n \cdot (n-1))$, too low.
 » 10 months ago, # | ← Rev. 2 →   Why does this work? I see it's AC and he got points for problem C