Maximum GCD after at most k operation

Revision en1, by Khalell, 2024-06-28 20:29:19

Given n numbers, what's the maximum GCD of the array that can we get after using at most k operations?

The only operation we can do at most k times, is to choose a number from the array and increment it by 1.

1 <= n <= 10^5

1 <= a_i <= 10^5

1 <= k <= 10^18

my approach was trying every number x smaller than the largest number in the array and count minimum operations to make each number divisible by x and if it possible then update my answer. now if the answer larger than or equal the largest then all numbers of the array must be equal, and the answer will be (k-sum)/n

i could solve this problem with these constraints but what if the numbers in the array were up to 10^9 or even 10^18, can anyone help me with the new constraints?

Tags gcd, number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Khalell 2024-06-29 19:51:36 53
en1 English Khalell 2024-06-28 20:29:19 797 Initial revision (published)