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
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.
Why does this work? I see it's AC and he got points for problem C