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 ?

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://mirror.codeforces.com/contest/364/submission/237449074

Auto comment: topic has been updated by harsh-apcr (previous revision, new revision, compare).i think since you have 20 times compute divisors consider computing them in a faster way(maybe sieve) it is just and idea i am not so sure.

I don't think its gonna work, only thing it'll do is reduce by a factor of $$$\log A$$$ (i.e. take $$$\sqrt{A}$$$ to $$$\sqrt{A}/\log A$$$, which isn't much of an improvement, Also I tried submitting with $$$m=10$$$, it still failed at test-case 3. So, it seems unlikely that'll help

yeah it was just an idea well i guess you should see editorial and try to look for an improvement maybe your idea was not so efficient.

Function

`rand()`

only returns small numbers (at least, on Windows).Auto comment: topic has been updated by harsh-apcr (previous revision, new revision, compare).n<=1e6

ai<=1e12

max. number of divisors can be (ai)^(1/3). In worst case, 1e4.

Worst case time complexity : 20*1e4*1e6 : 2e11

That's why you got tle.

My Submission

hmm.. I see, I thought number of divisors was logarithmic, but that's not true

Can you explain your submission ? Thanks

To avoid looping through the array(arr) for all divisors of an element, you can use seive technique.

But array values 'arr[i]' is pretty large(1e12). So, how to use seive technique here.

We can mask the values of the divisors(possible gcd values) to smaller indices(can be done using map).