When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Loserinlife's blog

By Loserinlife, history, 10 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +21 Vote: I do not like it

You say, $$$N\le 3000$$$, but then you again mention that $$$K \le N \le 100 $$$. Can you specify the constraints clearly?

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think he/she mentions : 2 <= N <= 3000 ; 1 <= K <= 100 ; 1 <= A[i] <= 1e10.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem! Is it proposed by yourself?

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it
Hint
»
10 months ago, # |
Rev. 6   Vote: I like it +4 Vote: I do not like it

I slightly modify hashlife's code and find that $$$6983776800$$$ is the number $$$\leq 1e10$$$ that has the most divisors ($$$2304$$$):

Spoiler

The code is based on backtracing. Link to the code:

(1) https://codeforces.com/blog/entry/14463

(2) http://ideone.com/JNRMsQ

The gcds 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.

Spoiler
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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 !! :))