Maximum GCD after at most k operation

Правка en1, от 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?

Теги gcd, number theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Khalell 2024-06-29 19:51:36 53
en1 Английский Khalell 2024-06-28 20:29:19 797 Initial revision (published)