Help in solving randomised algorithm problems

Revision en1, by harsh-apcr, 2023-12-16 12:18:35

I was practicing randomised algorithm problems and I stumbled across this nice problem : https://mirror.codeforces.com/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://mirror.codeforces.com/contest/364/submission/237431910

I am getting TLE, what can be the problem ?

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 harsh-apcr 2023-12-16 14:32:01 249
en2 harsh-apcr 2023-12-16 12:19:02 5
en1 harsh-apcr 2023-12-16 12:18:35 1198 Initial revision (published)