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?