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

this is my code

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?

i have a problem as follow Given a tree with n nodes with unique value for each node and q queries as given two nodes a and b ,find Mex in the path from a to b for each query

(1<n,q<200000)

my solution is using Mo algorithm as mentioned Here. i can find the Mex either using segment tree or set with log(n) for each query,but i think it is a bit hard for my solution to be valid under this constraints .

is there another solution with a better time complexity ?