Maximum GCD of new sequence

Revision en1, by Vasiljko, 2017-11-23 23:10:45

Given array A of N elements. We are allowed to do one operation: merge two elements A[i] and A[i+1] into A[i]+A[i+1]. We need to find sequence of exactly K elements with maximum possible GCD.

1 <= K < N <= 10^5
A[i] <= 10^6
sum of all A[i]'s <= 10^6

Input: 6 3
12 7 3 2 15 15

Output:
6
12 12 30

Tags #number theory, gcd

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Vasiljko 2017-11-23 23:10:45 372 Initial revision (published)