Choose k elements from an array so that their GCD is maximise.
Constraints: N <= 3000 K <= N; K <= 100 Ai <= 10^10 (ten to the power of 10) I tried an algorithm of enumerating all divisors of ai and find the largest divisors that exists in >= k elements but it TLE. Can somebody help? Thanks in advance.
You say, $$$N\le 3000$$$, but then you again mention that $$$K \le N \le 100 $$$. Can you specify the constraints clearly?
Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).
Nice problem! Is it proposed by yourself?
No its not mine. Its from an online judge :))
First thing to notice is that there are not a lot of different gcd's at all. Number of possible gcds is log2(10^10).
I slightly modify hashlife's code and find that $$$6983776800$$$ is the number $$$\leq 1e10$$$ that has the most divisors ($$$2304$$$):
The code is based on backtracing. Link to the code:
(1) https://mirror.codeforces.com/blog/entry/14463
(2) http://ideone.com/JNRMsQ
The
gcd
s of $$$K$$$ elements have to be divisors of $$$A_i$$$, so there are at most $$$3000*2304=6912000$$$ divisors. For each divisor $$$d$$$ maintains a set of indices $$$i$$$ such that $$$A_i$$$ is divisible by $$$d$$$. According to a simple counting twice method, the sum of set size is no more than $$$6912000$$$ also.You may also look for Tao's blog for the $$$log(n)$$$ mean value of $$$d(n)$$$ ($$$d(n)$$$ denotes the number of divisors of $$$n$$$). Also, there is an analytic bound for $$$d(n)$$$, however, it is not very helpful in your problem. Anyway, it can enlarge our horizon. Actually, the divisor bound is much more complicated that I initially imagine!
Tao's blog: https://terrytao.wordpress.com/2008/09/23/the-divisor-bound/
My solution: Just go through all divisors of $$$a[i]$$$ and find the largest one that occurs in $$$\geq k$$$ numbers.
Hi. Thanks for the answer. I did mention a similar approach in the post, but your comments gave me an idea. To deal with tests that have duplicates with a large number of divisors, I created another map cnt to count the number of appearances so every number we only iterate through 1 time. And it passed !! :))