Problem:
 Score : 500 points    Problem Statement We have a sequence of N integers: A_1, A_2, \cdots, A_N .  You can perform the following operation between 0 and K times (inclusive):   Choose two integers i and j such that i \neq j , each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j , possibly producing a negative element.   Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz .      Constraints  2 \leq N \leq 500  1 \leq A_i \leq 10^6  0 \leq K \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  A_1  A_2  \cdots  A_{N-1}  A_{N}       Output Print the maximum possible positive integer that divides every element of A after the operations.        Sample Input 1 2 3
8 20      Sample Output 1 7  7 will divide every element of A if, for example, we perform the following operation:   Choose i = 2, j = 1 . A becomes (7, 21) .   We cannot reach the situation where 8 or greater integer divides every element of A .       Sample Input 2 2 10
3 5      Sample Output 2 8  Consider performing the following five operations:   Choose i = 2, j = 1 . A becomes (2, 6) .  Choose i = 2, j = 1 . A becomes (1, 7) .  Choose i = 2, j = 1 . A becomes (0, 8) .  Choose i = 2, j = 1 . A becomes (-1, 9) .  Choose i = 1, j = 2 . A becomes (0, 8) .   Then, 0 = 8 \times 0 and 8 = 8 \times 1 , so 8 divides every element of A . We cannot reach the situation where 9 or greater integer divides every element of A .       Sample Input 3 4 5
10 1 2 22      Sample Output 3 7       Sample Input 4 8 7
1 7 5 6 8 2 6 5      Sample Output 4 5

Solution (Python):
import sys
input = sys.stdin.readline

n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(reverse=True)
divisors=[]
aa=sum(A)
for i in range(1,int(aa**0.5)+1):
  if aa%i==0:
    divisors.append(i)
    if i!=n//i:
      divisors.append(aa//i)
divisors.sort(reverse=True)

def f(d):
  count=0
  res1,res2=[],[]
  q=aa//d
  for i in range(n):
    if A[i]%d<(A[i]//d+1)*d-A[i]:
      count+=A[i]//d
      res2.append(A[i]%d)
    else:
      count+=A[i]//d+1
      res1.append((A[i]//d+1)*d-A[i])
  if count==q:
    return sum(res1)
  elif count<q:
    r2=len(res2)
    res2.sort(reverse=True)
    if r2==0:
      return sum(res1)+d*(q-count)
    else:
      if r2>q-count:
        return sum(res1)+d*(q-count)-sum(res2[:q-count])
      else:
        return sum(res1)+d*(q-count)-sum(res2)
  else:
    r1=len(res1)
    res1.sort(reverse=True)
    if r1==0:
      return sum(res2)+d*(count-q)
    else:
      if r1>q-count:
        return sum(res2)+d*(count-q)-sum(res1[:count-q])
      else:
        return sum(res2)+d*(count-q)-sum(res1)

ans=1
for d in divisors:
  if f(d)<=k:
    ans=d
    break
print(ans)

Solution (Python):
def div(n):
  ret=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      if i!=n//i:
        ret.append(n//i)
  return ret

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=sum(arr)
ans=1
d=div(s)
for val in d:
  arr=sorted(arr,key=lambda x:x%val)
  parr=[]
  narr=[]
  for num in arr:
    narr.append(num%val)
    parr.append(val-num%val)
  for i in range(n-1):
    parr[i+1]+=parr[i]
    narr[i+1]+=narr[i]
  for i in range(n-1):
    ncnt=narr[i]
    pcnt=parr[-1]-parr[i]
    if ncnt!=pcnt:
      continue
    else:
      if pcnt<=k:
        ans=max(ans,val)
print(ans)

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors = sorted(divisors)
    return divisors

n,k = map(int,input().split())
a = list(map(int,input().split()))

sum_a = sum(a)
div = make_divisors(sum_a)
ans = []
for i in div:
    mod_list = sorted([j%i for j in a],reverse=True)
    x = int(sum(mod_list)/i)
    mod_list = mod_list[:x]
    change = sum([i-j for j in mod_list])
    if change <= k:
        ans.append(i)
print(max(ans))

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a_list=list(map(int,input().split()))
S=sum(a_list)
import sys
i=1
while i**2<=S:
    if S%i==0:
        x=S//i
        temp=[]
        s=0
        for j in range(n):
            if (a_list[j]%x)!=0:
                s+=x-a_list[j]%x
                temp.append(a_list[j]%x)
        temp.sort()
        num=sum(temp[:s//x])
        if num<=k:
            print(x)
            sys.exit()
        temp=[]
        s=0
        for j in range(n):
            if (a_list[j]%i)!=0:
                s+=i-a_list[j]%i
                temp.append(a_list[j]%i)
        temp.sort()
        num=sum(temp[:s//i])
        if num<=k:
            ans=i
    i+=1
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

A_sum = sum(A)
A_sum_div = []
div = 1
while div ** 2 <= A_sum:
    if A_sum % div == 0:
        A_sum_div.append(div)
        if div ** 2 != A_sum:
            A_sum_div.append(A_sum // div)
    div += 1
A_sum_div.sort(reverse=True)

for i in range(len(A_sum_div)):
    M = A_sum_div[i]
    A_mod = [0] * N
    for j in range(N):
        A_mod[j] = A[j] % M
    A_mod.sort(reverse=True)
    A_mod_sum = sum(A_mod)
    need = 0
    if A_mod_sum != 0:
        for j in range(N):
            need += M - A_mod[j]
            A_mod_sum -= M
            if A_mod_sum == 0:
                break
    if need <= K:
        print(M)
        break

Solution (Python):

n, k = map(int, input().split())
a = list(map(int, input().split()))

s = sum(a)
d = []
for i in range(1, s):
    if s % i == 0:
        d.append(i)
    if s <= i * i:
        break
    if s % i == 0:
        d.append(s // i)
d = list(reversed(sorted(d)))

for di in d:
    b = []
    for ai in a:
        b.append(ai % di)
    b = list(sorted(b))
    cnt = 0
    il = 0
    ir = n - 1
    while il < ir:
        if b[il] <= di - b[ir]:
            cnt += b[il]
            b[ir] += b[il]
            b[il] = 0
            il += 1
        else:
            cnt += di - b[ir]
            b[il] -= di - b[ir]
            b[ir] = di
            ir -= 1
    if cnt <= k:
        print(di)
        break

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()

    cump = [0]
    for m in mods:
        cump.append(cump[-1] + m)
    cumm = [0]
    for m in reversed(mods):
        cumm.append(cumm[-1] + (d-m))
    for i in range(1,N):
        if cump[i] == cumm[N-i] and cump[i] <= K:
            print(d)
            exit()

Solution (Python):
from fractions import gcd

n, k = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())

S = sum(a)

div = []
for d in xrange(1, int(S ** 0.5) + 1):
    if S % d == 0:
        div.append(d)
        if d * d != S:
            div.append(S // d)

g = 0
for i in xrange(n):
    g = gcd(g, a[i])

ans = g
for d in div:
    if d < g: continue
    
    X = 0
    liz = []
    for i in xrange(n):
        x = a[i] % d
        if (x != 0): y = d - x
        else: y = 0
        
        X += y
        liz.append(y)
    liz.sort()

    q = X // d
    op = 0
    for i in xrange(len(liz) - 1, len(liz) - q - 1, -1):
        liz[i] -= d
        assert(liz[i] < 0)
        op += abs(liz[i])

    if op <= k:
        ans = max(ans, d)

print ans

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()

    cump = [0]
    for m in mods:
        cump.append(cump[-1] + m)
    cumm = [0]
    for m in reversed(mods):
        cumm.append(cumm[-1] + (d-m))
    for i in range(1,N):
        if cump[i] == cumm[N-i] and cump[i] <= K:
            print(d)
            exit()

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
divisor = []
for i in range(int(total ** 0.5)):
    if total % (i + 1) == 0:
        divisor.append(i + 1)
        divisor.append(total // (i + 1))
divisor.sort(reverse = True)
i = 0
while True:
    num = divisor[i]
    a2 = [a[j] % num for j in range(n)]
    count = 0
    res = 0
    while a2:
        test = min(a2)
        a2.remove(test)
        count += test
        res += test
        while res:
            test2 = max(a2)
            if res >= num - test2:
                res -= num - test2
                a2.remove(test2)
            else:
                a2[a2.index(test2)] += res
                res = 0
    if count <= k:
        break
    else:
        i += 1
print(num)

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, A: "List[int]"):
    s = sum(A)
    A.sort()
    i = 1
    
    
    ret = 1
    def is_ok(n):
        downs = []
        for v in A:
            downs.append(v % n)
        downs.sort()
        
        cnt = float('inf')
        for i in range(1, N):
            left = 0
            right = 0
            for l in range(i):
                left += downs[l]
            for r in range(i, N):
                right += (n - downs[r])
            tmp = max(left, right)
            cnt = min(cnt, tmp)
            
        
        if cnt <= K:
            return True
        return False

    while i * i <= s:
        if s % i == 0:
            if is_ok(s // i):
                ret = max(ret, s // i)
            if is_ok(i):
                ret = max(ret, i)
        i += 1
    print(ret)
    return


def _solve(N: int, K: int, A: "List[int]"):
    s = sum(A)
    A.sort()
    i = 1
    print(s)
    print(A)
    ret = 1
    def is_ok(n):
        cnt = 0
        ls = 0
        us = 0
        bs = 0
        for v in A:
            tmp = v // n
            l = abs(v - n * (tmp))
            u = abs(v - n * (tmp + 1))
            if l < u:
                ls += l
            elif l > u:
                us += u
            else:
                bs += l
        cnt = max(ls, us)
        
        
        
        
        
        print(n, ls, us, cnt)
        if cnt <= K:
            return True
        return False

    while i * i <= s:
        if s % i == 0:
            if is_ok(s // i):
                ret = max(ret, s // i)
            if is_ok(i):
                ret = max(ret, i)
        i += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, K, A)

if __name__ == '__main__':
    main()

Solution (Python):
n, k = list(map(int, input().split() ))
nums = list(map(int, input().split() ))

summ = sum(nums)
divisors = []

for d in range(1, summ):
	if d * d > summ:
		break
	if summ % d == 0: 
		divisors.append(d)
		divisors.append(int(summ // d))

divisors.sort(reverse = True)



for d in divisors:

	residues = [0] * n
	for i in range(n):
		residues[i] = nums[i] % d

	residues.sort(reverse = True)

	init_sum = sum(residues)
	num_reverse = init_sum // d




	times_operation = d * num_reverse - sum(residues[0:num_reverse])



	if times_operation <= k:
		print(d)
		exit()

Solution (Python):
words = lambda t : list(map(t, input().split()))
n,k = words(int)
xs = words(int)

def divisor (x):
    ans = []
    for i in range(1, int(x**0.5)+1):
        if x % i == 0:
            ans.append(i)
            if i != x // i:
                ans.append(x//i)
    ans.sort()
    return list(reversed(ans))

s = sum(xs)

ds = divisor(s)
ans = 1

for d in ds:
    ms = []
    for x in xs:
        ms.append(x%d)
    ms.sort()
    
    f = 0
    f_ttl = ms[f]
    b = len(ms)-1
    b_ttl = d - ms[b]
    while f != b:
        if f_ttl >= b_ttl:
            b -= 1
            b_ttl += d - ms[b]
        else:
            f += 1
            f_ttl += ms[f]
    if k >= f_ttl:
        ans = d
        break
print(ans)

Solution (Python):




n, k = map(int, input().split())
an = list(map(int, input().split()))

sa = sum(an)
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)

  divisors.sort()
  return divisors
div = make_divisors(sa)

for d in div[::-1]:
  if d == 1:
    print(1)
    break
  bn = [a % d for a in an if a % d != 0]
  bn.sort()
  sb = sum(bn)
  sb_l = sum(bn[:-1*(sb//d)])
  if sb_l <= k:
    print(d)
    break

Solution (Python):
N,KK = list(map(int,input().split()))
A = list(map(int,input().split()))
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)

    
  return divisors
for i in sorted(make_divisors(sum(A)),key=lambda x:-x ):
  
  J = []
  j_prev=0
  for j in  sorted([a%i for a in A if a%i !=0]):
    J.append(j_prev+j)
    j_prev = J[-1]
  
  K = []
  k_prev=0
  for k in  sorted([a%i-i for a in A if a%i !=0],key=lambda x:-x ):
    K.append(k_prev+k)
    k_prev = K[-1]
  for jdx,j in enumerate(J):
    
    if jdx<len(K)-1 and j + K[-jdx-2] ==0:
      if j<= KK:
        print(i)
        quit()
else:
  print(1)

Solution (Python):


def factors(N): 
    from collections import deque
    ret = deque()
    middle = int( N**(1/2))
    for i in range(1, middle):
        if N%i == 0:
            ret.append(i)
            ret.append(N//i)
            
    if N%middle == 0:
        ret.append(middle)
        if middle != N//middle:
            ret.append(N//middle)
    return ret

def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    sa = sum(A)
    R = factors(sa)
    l = len(R)
    E = [0]*l
    ans = 0
    for r in R:
        cnt = 0
        E = list( map( lambda x:x%r, A))
        E.sort()
        s = sum(E)
        now = 0
        if s - E[-1] <= K:
            if ans < r:
                ans = r
            continue
        if s == 0:
            continue
        v = 0
        w = N-1
        cnt = 0
        while w-v != 0:
            if E[v] == 0:
                v += 1
                continue
            if E[w] == 0:
                w -= 1
                continue
            if E[v] + E[w] >= r:
                E[v] -= r - E[w]
                cnt += r - E[w]
                E[w] = 0
                w -= 1
            else:
                E[w] += E[v]
                cnt += E[v]
                E[v] = 0
                v += 1
        if cnt <= K:
            if r > ans:
                ans = r
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

x = sum(A)

tL = prime(x)
L = [1]
for k, v in tL.items():
  t = len(L)
  n = k
  for i in range(v):
    for j in range(t):
      L.append(L[j] * n)
    n *= k

L.sort(reverse = True)

for i in L:
  M = [j % i for j in A]
  M.sort()
  f = True
  c = 0
  for k in M:
    if f:
      if c + k <= K:
        c += k
      else:
        f = False
        c = (i - k)
    else:
      if c + (i - k) <= K:
        c += (i - k)
      else:
        break
  else:
    print(i)
    break

Solution (Python):
submit = True


def solve_e(test=False, n=2, k=3, a_list=[8, 20]):

    if not test:
        n, k = map(int, input().split())
        a_list = list(map(int, input().split()))

    a_sum = sum(a_list)
    q_list = []

    for i in range(1, int(a_sum ** 0.5)+1):
        if a_sum % i == 0:
            q_list.append(i)
            if i != a_sum // i:
                q_list.append(a_sum // i)

    res = 1
    for q in q_list:
        r_list = [0] * n
        for i in range(n):
            r_list[i] = a_list[i] % q
        r_list_s = sorted(r_list)
        cnt = 0
        right = n - 1
        for i in range(n):
            if r_list_s[i] == q:
                break
            r = r_list_s[i]
            cnt += r
            while r > 0:
                d = q - r_list_s[right]
                if r >= d:
                    r -= d
                    r_list_s[right] = q
                    right -= 1
                else:
                    r_list_s[right] += r
                    r = 0
            r_list_s[i] = 0
        if cnt <= k:
            if q > res:
                res = q

    print(res)


if __name__ == "__main__":
    if submit:
        solve_e()
    else:
        solve_e(test=True, n=2, k=3, a_list=[8, 20])
        solve_e(test=True, n=2, k=10, a_list=[3, 5])
        solve_e(test=True, n=4, k=5, a_list=[10, 1, 2, 22])
        solve_e(test=True, n=8, k=7, a_list=[1, 7, 5, 6, 8, 2, 6, 5])

Solution (Python):
def divi(n):
    res = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n//i)
    return res
N, K = map(int, input().split())
A = list(map(int, input().split()))

SA = sum(A)
D = divi(SA)
D.sort(reverse = True)
ans = 0
for d in D:
    P = []
    for a in A:
        P.append(-(-a//d)*d - a)
    P.sort()
    ups = sum(P)
    if ups <= K:
        ans = d
        break
    ss = ups
    for i in range(1, N+1):
        ss -= P.pop()
        if max(ss, i*d -ups + ss) <= K:
            ans = d
            break
    else:
        continue
    break
print(ans)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial


def divisor(n): 
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    table.sort(reverse=True)
    return table


def check(data, ele, num, k):
    plus, minus = 0, 0
    amari_dic = defaultdict(int)
    for i in range(num):
        now_num = data[i]
        amari = now_num % ele
        amari_dic[amari] += 1
        
        
        
        

    amari_dic = sorted(amari_dic.items(), key=lambda x: x[0])

    for amari, kosuu in amari_dic:
        if amari == 0:
            continue
        ikeru = min((k - plus) // amari, kosuu)
        plus += ikeru * amari
        minus += (kosuu - ikeru) * (ele - amari)


    
    if max(plus, minus) <= k:
        return 1
    else:
        return 0

def main():

    num, k = map(int, input().split())
    data = list(map(int, input().split()))

    sum_num = sum(data)
    yakusuu_list = divisor(sum_num)

    

    for ele in yakusuu_list:
        if check(data, ele, num, k):
            print(ele)
            sys.exit()







if __name__ == '__main__':
    main()

Solution (Python):
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass 

def main():
    import sys,bisect
    input = sys.stdin.readline

    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    kouho = divisor(sum(a))
    kouho.sort(reverse = True)

    for e in kouho:
        tank = [s%e for s in a]
        tank.sort()

        p = 0
        q = n-1

        s = tank[0]
        t = e-tank[-1]
        while p != q-1:
            if s > t:
                q -= 1
                t += e-tank[q]
            else:
                p += 1
                s += tank[p]


        if s <= k:

            print(e)
            exit()

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque

N,K = map(int,input().split())

A = [int(x) for x in input().split()]
S = sum(A)

div = set()
for d in range(1,S+1):
    if d*d > S:
        break
    if S%d == 0:
        div.add(d)
        div.add(S//d)

def F(d):
    
    cost = 0
    q = deque(sorted(x%d for x in A))
    while q:
        x = q[0]
        if x == 0:
            q.popleft()
            continue
        y = q[-1]
        if y == 0:
            q.pop()
            continue
        z = d - y
        t = x if x < z else z
        cost += t
        q[0] -= t
        q[-1] += t
        q[-1] %= d
    return cost

answer = None
div = sorted(div, reverse = True)
for d in div:
    cost = F(d)
    if cost <= K:
        answer = d
        break

print(answer)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort(reverse=True)
    return divisors


s = sum(a)
divisors = make_divisors(s)

for d in divisors:
    reminders = [ai % d for ai in a]
    reminders.sort()
    for i in range(n - sum(reminders) // d, n):
        reminders[i] -= d

    se = sum(abs(r) for r in reminders)
    if se <= 2 * k:
        print(d)
        break

Solution (Python):


import sys

n, k = map(int, input().split())

a = list(map(int, input().split()))

s = sum(a)

l = []

def check(b) :
    r1 = [x % b for x in a]
    r1.sort()
    s1 = sum(r1)
    
    mn = 1e9
    s2 = 0
    for i in range(n):
        s2 += r1[i]
        mn = min(max(s2, (n-1-i)*b - (s1-s2)), mn)
        
    if mn <= k :
        print(int(b))
        sys.exit(0)
        

for p in range(1,int((s+1)**0.5+1)) :
    if s % p != 0:
        continue
    b = s // p
    l.append(b)
    check(b)
    
l.reverse()

for p in l:
    b = s // p
    check(b)

Solution (Python):
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))

sA = sum(A)

div_list = []

for i in range(1,int(sA**0.5)+1):
    if sA%i==0:
        if i!=sA**0.5:
            div_list.append(i)
            div_list.append(sA//i)
        else:
            div_list.append(i)


div_list.sort(reverse=True)

for d in div_list:
    count=0
    count_list = []
    l = 0
    for a in A:
        n=a%d
        if n!=0:
            l+=1
            count+=n
            count_list.append(n)

    if count%d==0:
        if count//d<l:
            count_list.sort()
            if sum(count_list[:l-count//d])<=K:
                break

print(d)

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort(reverse=True)
    return divisors


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

div = make_divisors(sum(a))

for x in div:
    aa = [ai % x for ai in a]
    aa.sort()
    ss = aa[:len(aa) - sum(aa) // x]
    s = sum(ss)

    if 0 <= s <= k:
        print(x)
        break

Solution (Python):
import math
n,k = map(int,input().split())
lis = list(map(int,input().split()))
li = []
num = sum(lis)
for i in range(1,math.ceil(math.sqrt(num))+1):
    if num % i == 0:
        li.append(i)
        li.append(num // i)
li.sort(reverse = True)


for numb in li:
    liss = []
    for i in lis:
        if i % numb == 0:
            liss.append(numb)
        else:
            liss.append(i % numb)
    liss.sort(reverse=True)
    co = 0
    numm = sum(liss)

    for i in range(numm//numb):
        co += numb-liss[i]
    if co <= k:
        print(numb)
        exit()

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    divisors=sorted(divisors)
    return divisors

n, k = map(int, input().split())
alist = list(map(int, input().split()))
nagaa = len(alist)
wa = sum(alist)
yakusu=make_divisors(wa)
ng=len(yakusu)

for i in range(ng):
    nowyaku=yakusu[ng-i-1]
    amalist=[]
    for al in alist:
        amalist.append(al%nowyaku)
    amalist=sorted(amalist)
    amawa=sum(amalist)
    hidari=amawa
    migi=0
    j=0
    while hidari!=migi:
        
        nowama=amalist[nagaa-j-1]
        hidari-=nowama
        migi+=(nowyaku-nowama)
        j+=1
    
    if hidari<=k:
        print(nowyaku)
        exit()

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
li = make_divisors(sum(A))
for i in li[::-1]:
    cnt = 0
    B = [x%i for x in A]
    B.sort(reverse=True)
    now_all = sum(B)
    for j in B:
        if(now_all==0):break
        if(j!=0):
            cnt += i-j
            now_all -= i
    if(cnt<=K):
        print(i)
        break

Solution (Python):
def divisible(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort(reverse=True)
    return divisors

n, k = map(int, input().split())
arr = list(map(int, input().split()))
divs = divisible(sum(arr))

for div in divs:
    test_arr = [x % div for x in arr]
    test_arr.sort()
    sum_test_arr = sum(test_arr)
    change = sum(test_arr[:-sum_test_arr // div])
    if change <= k:
        print(div)
        exit()

Solution (Python):


from collections import Counter
from itertools import product
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield n

from functools import reduce
import operator
int_product = lambda it: reduce(operator.mul,it,1)


def divisors(n):
    factors = prime_factors(n)
    factors = Counter(factors)
    pows = tuple(factors.values())
    factors = tuple(factors.keys())
    for pp in product(*(range(p+1) for p in pows)):
        yield int_product(f**p for f,p in zip(factors,pp))


N,K = map(int,input().split())
A = list(map(int,input().split()))

def check(m):
    cost = 0
    S = sorted(a%m for a in A)
    total = sum(S)//m
    
    return (sum(s for s in S[:N-total]) + sum(m-s for s in S[N-total:]))//2

for d in sorted(divisors(sum(A)), reverse=True):
    
    if check(d) <= K:
        print(d)
        break

Solution (Python):
import math
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
S = sum(A)
P = []
_P = []
for i in range(1, int(math.sqrt(S)) + 1):
  if S % i:
    continue
  P.append(S // i)
  _P.append(i)
P += _P[::-1]
for p in P:
  _A = sorted([a - p * (a // p) for a in A], reverse=True)
  n = sum(_A) // p
  if sum(_A) - sum(_A[:n]) <= K:
    print(p)
    break

Solution (Python):
n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
total = sum(a)

def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

divs = divisors(total)

for div in divs[::-1]:
    mod_div = [0] * n
    mod_sum = 0
    opr_cnt = 0
    for i, item in enumerate(a):
        mod_div[i] = item % div
    mod_sum = opr_cnt = sum(mod_div)
    mod_div.sort()
    for i, item in enumerate(mod_div[::-1]):
        if mod_sum == 0:
            break
        
        mod_sum -= div
        opr_cnt += div - 2 * item
    if opr_cnt <= k * 2:
        print(div)
        exit()

Solution (Python):
import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
fact=[]
for i in range(1,int(sum(a)**0.5)+1):
  if sum(a)%i==0:
    fact.append(i)
    fact.append(sum(a)//i)
fact=list(set(fact))
fact.sort()
fact.reverse()
a.sort()
a.reverse()
for i in range(len(fact)):
  a2=copy.copy(a)
  for j in range(n):
    a2[j]%=fact[i]
  a2.sort()
  a2.reverse()
  ct=0
  for m in range(sum(a2)//fact[i]):
    ct+=a2[m]
  if (sum(a2)-ct)<=k:
    print(fact[i])
    break

Solution (Python):


import sys

class EMaxGCD:
    def solve(self):
        n, k = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]
        a.sort()
        s = sum(a)
        ans = 1
        for u in range(1, int(s ** .5) + 1):
            if s % u:
                continue
            v = s // u
            for d in [u, v]:
                b = sorted([x % d for x in a])
                need = 0
                l, r = 0, n - 1
                while l < r:
                    m = min(b[l], d - b[r])
                    need += m
                    b[l] -= m
                    b[r] += m
                    if b[r] % d == 0:
                        r -= 1
                    if b[l] % d == 0:
                        l += 1
                
                
                
                
                if need <= k:
                    ans = max(ans, d)

        print(ans)


solver = EMaxGCD()
input = sys.stdin.readline

solver.solve()

Solution (Python):
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y, x%y)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        
        
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N,K = map(int,input().split())
a_list = list(map(int,input().split()))

sums = sum(a_list)
divisors = make_divisors(sums)
divisors.reverse()

def func():
    for d in divisors:
        amaris = [a%d for a in a_list]
        amaris.sort()
        amaris.reverse()
        amari_sum = sum(amaris)
        hanten_cnt = int(amari_sum / d)
        sousa_cnt = 0
        for i in range(hanten_cnt):
            sousa_cnt += d - amaris[i]
        if sousa_cnt <= K:
            return d

result = func()

print(result)