I was practicing randomised algorithm problems and I stumbled across this nice problem : https://codeforces.net/contest/364/problem/D

My approach to this problem is as follows : Let $$$g$$$ be the ghd of the input, then prob($$$g | a_i$$$) = 1/2 (where $$$a_i$$$ is random number from the input) thus with 1/2 probability $$$g$$$ is divisor of $$$a_i$$$, so divisors of $$$a_i$$$ can be good candidate for $$$g$$$

So my algorithm is repeat 20 times : take random number $$$a_i$$$ from the input array, compute its divisors iterate over its divisors list, and for each divisor $$$d$$$ of $$$a_i$$$, compute number of $$$a_j$$$ such that $$$d | a_j$$$, if it is $$$\geq \frac{n}{2}$$$ then $$$d$$$ is candidate $$$g$$$

Probability I don't get correct answer = probability in none of the 20 trails I get the correct $$$a_i$$$ = $$$1/2^{20}$$$ approx $$$10^{-6}$$$

Time complexity of the solution is : $$$O((n d + \sqrt{A})m)$$$ ,where $$$m$$$ is number of trails, $$$A = \textrm{max} a_i$$$, and $$$d$$$ is max number of divisors (which is typically very small and grows logarithmically)

Here is my submission link : https://codeforces.net/contest/364/submission/237431910

I am getting TLE, what can be the problem ?

UPDATE : I did some optimizations, and passed the 3rd test-case now I am stuck at 4th These two test cases are very similar I don't know why there is this problem

updated submission : https://codeforces.net/contest/364/submission/237449074