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
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union






























def main():
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def enum_divisor(num):
        i = 1
        left = []
        right = []
        while i ** 2 < num:
            if num % i == 0:
                left.append(i)
                right.append(num // i)
            i += 1
        if i ** 2 == num:
            return left + [i] + list(reversed(right))
        else:
            return left + list(reversed(right))
    

    def is_ok(m, k, L):
        mod_list = [elm % m for elm in L]
        plus_group, minus_group = [], []
        plus_cnt, minus_cnt = 0, 0
        for mod_num in mod_list:
            if mod_num <= m - mod_num:
                minus_group.append(mod_num)
                minus_cnt += mod_num
            else:
                plus_group.append(mod_num)
                plus_cnt += m - mod_num
        
        
        
        assert abs(plus_cnt - minus_cnt) % m == 0
        cnt = plus_cnt + minus_cnt
        if plus_cnt > minus_cnt:
            
            plus_group.sort()
            for i in range((plus_cnt - minus_cnt) // m):
                mod_num = plus_group[i]
                cnt += (mod_num - (m - mod_num))
        else:
            
            minus_group.sort(reverse=True)
            for i in range((minus_cnt - plus_cnt) // m):
                mod_num = minus_group[i]
                cnt += ((m - mod_num) - mod_num)
        
        assert cnt % 2 == 0
        return cnt // 2 <= k
    

    n, k = mi()
    L = lmi()
    s = sum(L)
    div = enum_divisor(s)
    div.reverse()


    for m in div:
        if is_ok(m, k, L):
            print(m)
            break







if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
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=1)
    return divisors

n,k = map(int,input().split())
a = list(map(int,input().split()))
S = sum(a)
for gcd in make_divisors(S):
    li = deque(sorted([x % gcd for x in a]))
    count = 0
    L = li.popleft()
    R = li.pop()
    while li:
        if L >= gcd-R:
            L -= gcd-R
            count += gcd-R
            R = li.pop()
        else:
            R += L
            count += L
            L = li.popleft()
    count += L
    if count <= k:
        print(gcd)
        exit()

Solution (Python):
import numpy as np

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

As_arr = np.array(As_lis)
S = np.sum(As_arr)

smaller_factors = []
larger_factors = []
for i in range(1, int(S ** 0.5) + 1):
    if S % i == 0:
        smaller_factors.append(i)
        larger_factors.append(S // i)

for fac in larger_factors:
    mods = As_arr % fac
    k = np.sum(np.sort(mods)[:N - np.sum(mods) // fac])
    if k <= K:
        print(fac)
        exit()

for fac in reversed(smaller_factors):
    mods = As_arr % fac
    k = np.sum(np.sort(mods)[:N - np.sum(mods) // fac])
    if k <= K:
        print(fac)
        exit()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

def is_divide(d):
    Rs = [a%d for a in A]
    Rs.sort()
    cumsum = [0] * (N + 1)
    for i in range(N - 1,-1,-1):
        cumsum[i] = cumsum[i + 1] + d - Rs[i]
    cum = 0
    for i in range(N):
        if max(cum,cumsum[i]) <= K:
            return True
        cum += Rs[i]
    return False

S = sum(A)
ans = 0
for i in range(1,S + 1):
    if i*i > S:
        break
    if S%i == 0:
        if is_divide(i):
            ans = max(ans,i)
        if is_divide(S//i):
            ans = max(ans,S//i)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

def is_divide(d):
    Rs = [a%d for a in A]
    Rs.sort()
    cumsum = [0] * (N + 1)
    for i in range(N - 1,-1,-1):
        cumsum[i] = cumsum[i + 1] + d - Rs[i]
    cum = 0
    for i in range(N):
        if max(cum,cumsum[i]) <= K:
            return True
        cum += Rs[i]
    return False

S = sum(A)
ans = 0
for i in range(1,S + 1):
    if i*i > S:
        break
    if S%i == 0:
        if is_divide(i):
            ans = max(ans,i)
        if is_divide(S//i):
            ans = max(ans,S//i)
print(ans)

Solution (Python):









import sys
readline = sys.stdin.readline

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

all = sum(A)
divisors = []
for i in range(1,int(all ** 0.5) + 1):
  if all % i == 0:
    divisors.append(i)
    divisors.append(all // i)

divisors = sorted(divisors,reverse = True)

for d in divisors:
  mods = [0] * (N)
  for i in range(len(A)):
    mods[i] = A[i] % d
  mods = sorted(mods)
  mods_front = [0] * N
  mods_front[0] = mods[0]
  for i in range(1,N):
    mods_front[i] = mods_front[i - 1] + mods[i]
  mods_back = [0] * N
  mods_back[-1] = d - mods[-1]
  for i in range(N - 2,-1,-1):
    mods_back[i] = mods_back[i + 1] + (d - mods[i])
  for i in range(N - 1):
    if mods_front[i] == mods_back[i + 1]:
      if K >= mods_front[i]:
        print(d)
        exit(0)
else:
  print(1)

Solution (Python):







import sys
readline = sys.stdin.readline

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

all = sum(A)
divisors = []
for i in range(1,int(all ** 0.5) + 1):
  if all % i == 0:
    divisors.append(i)
    divisors.append(all // i)

divisors = sorted(divisors,reverse = True)

for d in divisors:
  mods = [0] * (N)
  for i in range(len(A)):
    mods[i] = A[i] % d
  mods = sorted(mods)
  mods_front = [0] * N
  mods_front[0] = mods[0]
  for i in range(1,N):
    mods_front[i] = mods_front[i - 1] + mods[i]
  mods_back = [0] * N
  mods_back[-1] = d - mods[-1]
  for i in range(N - 2,-1,-1):
    mods_back[i] = mods_back[i + 1] + (d - mods[i])
  for i in range(N - 1):
    if mods_front[i] == mods_back[i + 1]:
      if K >= mods_front[i]:
        print(d)
        exit(0)
else:
  print(1)

Solution (Python):








import sys
readline = sys.stdin.readline

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

all = sum(A)
divisors = []
for i in range(1,int(all ** 0.5) + 1):
  if all % i == 0:
    divisors.append(i)
    divisors.append(all // i)

divisors = sorted(divisors,reverse = True)



for d in divisors:
  mods = [0] * (N)
  for i in range(len(A)):
    mods[i] = A[i] % d
  mods = sorted(mods)
  
  mods_front = [0] * N
  mods_front[0] = mods[0]
  for i in range(1,N):
    mods_front[i] = mods_front[i - 1] + mods[i]
  mods_back = [0] * N
  mods_back[-1] = d - mods[-1]
  
  for i in range(N - 2,-1,-1):
    mods_back[i] = mods_back[i + 1] + (d - mods[i])
  
  for i in range(N - 1):
    if mods_front[i] == mods_back[i + 1]:
      if K >= min(mods_front[i],mods_back[i + 1]):
        print(d)
        exit(0)
else:
  print(1)

Solution (Python):
def factors(n):
  a = [1,n]
  x = 2
  while x * x <= n :
    if n % x == 0:          
      a.append(x)
      c=n//x
      while(c+1)*x<=n:
        c+=1
      a.append(c)
    x+=1
  return a
n,k=map(int,input().split())
a=list(map(int,input().split()))
candidates=factors(sum(a))
candidates.sort()
candidates.reverse()
for i in candidates:
  b=[]
  for j in range(n):
    b.append(a[j]%i)
  b.sort()
  upsum=0
  downsum=0
  for j in range(n):
    upsum+=i-b[j]
  for j in range(n):
    upsum-=i-b[j]
    downsum+=b[j]
    if upsum<=downsum:
      break
  if upsum<=k:
    print(i)
    break

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)

    return divisors

N, K = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
L = make_divisors(S)
ans = 0
for i in L:
    D = []
    for a in A:
        if a % i != 0:
            D.append(a % i)
    D.sort()
    L1 = [0]
    L2 = [0]
    for j in range(len(D)):
        L1.append(L1[-1] + D[j])
        L2.append(L2[-1] + i - D[len(D)-1-j])
    L2.reverse()
    
    for j in range(len(D)+1):
        if K >= max(L1[j], L2[j]):
            ans = max(ans, i)

print(ans)

Solution (Python):

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

s = sum(A)



def solve():
    ans = 1
    idx = 1

    while idx * idx <= s:
        if s % idx == 0:
            if ok(s // idx):
                return s // idx
            if ok(idx):
                ans = idx
        idx += 1

    return ans


def ok(i):
    D = list(filter(lambda x: x != 0, [a % i for a in A]))
    D.sort()

    l = len(D)

    S = [0] * (l + 1)
    for j in range(l):
        S[j + 1] = S[j] + D[j]

    for j in range(l):
        if S[j] == i * (l - j) - (S[l] - S[j]) and S[j] <= K:
            return True

    return False


print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')


from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations




def solve():
    N, K = MI()
    A = LI()

    M = sum(A)
    divs = []
    for i in range(1, int(pow(M, 0.5))+1):
        if M % i: continue
        divs.append(i)
        if i != M//i: divs.append(M//i)
    divs.sort(reverse=True)

    for d in divs:
        B = list(map(lambda x: x%d, A))
        B.sort()
        C = list(map(lambda x: d-x, B))
        
        
        Ba = list(accumulate(B))
        Ca = list(accumulate(C))
        for i in range(0, N-1):
            b = Ba[i]
            c = Ca[-1] - Ca[i]
            
            if b == c and b <= K:
                print(d)
                return
    print(1)


if __name__ == '__main__':
    solve()

Solution (Python):
def divisors(N):
    return sorted(sum((list({n, N // n}) for n in range(1, int(N ** 0.5) + 1) if not N % n), []), reverse=True)
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
D = divisors(sum(A))
for d in D:
    L = sorted(a % d for a in A)
    if not sum(L):
        print(d)
        break
    left, right = 0, N - 1
    count = 0
    while left < right:
        if L[left] + L[right] <= d:
            next_right = right - (L[right] + L[left] == d)
            next_left = left + 1
            L[right] += L[left]
            count += L[left]
            L[left] = 0
        else:
            next_left = left
            next_right = right - 1
            m = d - L[right]
            count += m
            L[right] += m
            L[left] -= m
        left, right = next_left, next_right
    if count <= K:
        print(d)
        break

Solution (Python):
def get_divisors(x):
    i = 1
    ret = set()
    while i * i <= x:
        if x % i == 0:
            ret.add(i)
            ret.add(x // i)

        i += 1

    return ret


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

sm = sum(a)
divs = get_divisors(sm)

ans = 0
for div in divs:
    mods = [e % div for e in a]
    mods.sort()
    p = 0
    m = n * div - sum(mods)
    for mod in mods:
        p += mod
        m -= div - mod
        if p == m:
            if p <= k:
                ans = max(ans, div)
            break

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush


def solve():
    n, k = MI()
    A = LI()
    sm = sum(A)

    div = []
    for i in range(1, int(pow(sm, 0.5))+1):
        if sm % i: continue
        div.append(i)
        if i != sm //i:
            div.append(sm // i)
    ans = 1
    for d in div:
        R = [a % d for a in A]
        R.sort()
        plus = 0
        minus = 0
        for r in R:
            plus += d - r
        for r in R:
            minus += r
            plus -= d - r
            if minus == plus and plus <= k:
                ans = max(ans, d)
    print(ans)



if __name__ == '__main__':
    solve()

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    s = sum(a)
    cand = [s]
    for i in range(2, int(s ** 0.5) + 1):
        if s % i == 0:
            cand.append(i)
            cand.append(s // i)
    cand.sort(reverse=True)

    for c in cand:
        arr = [a[i] % c for i in range(n)]
        arr.sort()
        sum_r = [0] * n
        sum_r[0] = arr[0]
        for i in range(1, n):
            sum_r[i] = sum_r[i - 1] + arr[i]
        for i in range(n - 1):
            if sum_r[i] <= k:
                sum_l = c * (n - i - 1) - sum_r[-1] + sum_r[i]
                if sum_r[i] == sum_l:
                    print(c)
                    exit()

    print(1)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
def divisor(n):
    res = []
    i = 1
    while i*i <= n:
        if n%i == 0:
            res.append(i)
            if i*i != n:
                res.append(n//i)
        i += 1
    res.sort()
    return res

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
ans = 1
for d in divisor(S):
    rs = [a%d for a in A]
    rs.sort()
    Sum = [0]*(N+1)
    Sum2 = [0]*(N+1)
    for i in range(1,N+1):
        Sum[i] = Sum[i-1]+rs[i-1]
        Sum2[i] = Sum2[i-1]+(d-rs[i-1])
    for i in range(N+1):
        if Sum[i] == Sum2[N]-Sum2[i]:
            if Sum[i] <= K:
                ans = d
print(ans)

Solution (Python):
def divisor(n):
    res = []
    i = 1
    while i*i <= n:
        if n%i == 0:
            res.append(i)
            if i*i != n:
                res.append(n//i)
        i += 1
    res.sort()
    return res

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
ans = 1
for d in divisor(S):
    rs = [a%d for a in A]
    rs.sort()
    Sum = [0]*(N+1)
    Sum2 = [0]*(N+1)
    for i in range(1,N+1):
        Sum[i] = Sum[i-1]+rs[i-1]
        Sum2[i] = Sum2[i-1]+(d-rs[i-1])
    for i in range(N+1):
        if Sum[i] == Sum2[N]-Sum2[i]:
            if Sum[i] <= K:
                ans = d
print(ans)

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


@mt
def slv(N, K, A):
    S = sum(A)
    ans = 0
    for d in divisor(S):
        r = [a%d for a in A]
        r.sort()
        lr = [0]
        rr = [0]
        for v in r:
            lr.append(lr[-1] + v)
            rr.append(rr[-1] + (d-v))
        for i in range(N):
            l = lr[i+1] - lr[0]
            r = rr[-1] - rr[i+1]
            if l == r and l <= K:
                ans = max(ans, d)
    return ans






def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

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

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

fac=sorted(factor(sum_),reverse=True)
ans=1
for x in fac:
    li=sorted(z%x for z in a)
    res=0
    cum=[0]*(n+1)
    for i in range(n):
        cum[i+1]=cum[i]+li[i]
    for i in range(1,n):
        l,r=cum[i],x*(n-i)-(cum[n]-cum[i])
        if l==r and r<=k:
            ans=max(ans,x)
print(ans)

Solution (Python):
from collections import deque
def isok(x):
    que=deque(sorted(z%x for z in a))
    res=0
    while que:
        l=que[0]
        if l==0:
            que.popleft()
            continue
        r=que[-1]
        if r==0:
            que.pop()
            continue
        d=min(l,x-r)
        que[0]-=d
        que[-1]=(que[-1]+d)%x
        res+=d
    return res
        
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

fac=sorted(factor(sum_),reverse=True)
ans=1
for x in fac:
    c=isok(x)
    if c<=k:
        ans=x
        break
print(ans)

Solution (Python):
from collections import deque
def isok(x):
    que=deque(sorted(z%x for z in a))
    res=0
    while que:
        l=que[0]
        if l==0:
            que.popleft()
            continue
        r=que[-1]
        if r==0:
            que.pop()
            continue
        d=min(l,x-r)
        que[0]-=d
        que[-1]=(que[-1]+d)%x
        res+=d
    return res
        

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

fac=set()
for i in range(1,sum_+1):
    if i*i>sum_:
        break
    if sum_%i==0:
        fac.add(i)
        fac.add(sum_//i)

fac=sorted(fac,reverse=True)
ans=1
for x in fac:
    c=isok(x)
    if c<=k:
        ans=x
        break
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
sum_a = sum(a)
ans = 0
def try_ans(target):
    remain = [i % target for i in a]
    remain.sort()
    count = 10**10
    
    sum_remain = sum(remain)
    
    plus_remain = 0
    for i in range(n-1,-1,-1):
        plus_remain += target - remain[i]
        sum_remain -= remain[i]
        count = min(count, max(sum_remain,plus_remain))
    return count <= k

for i in range(1,int(sum_a**0.5)+1):
    if sum_a % i == 0:
        if try_ans(i):
            ans = max(ans, i)
        if try_ans(sum_a // i):
            ans = max(ans, sum_a//i)
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
cnt=1
A=sum(a)
l=[]
for i in range(1,int(A**(1/2))+1):
    if A%i!=0:continue
    l.append(i)
    if  A// i != i:
        l.append(A // i)
for i in l:
    x=[0]*n
    for j in range(n):
        x[j]=a[j]%i
    s=sum(x)
    l=0
    x.sort(reverse=True)
    for j in range(n):
        if s<=k and l<=k:
            if (s-l)%i==0:
                if i>cnt:
                    cnt=i
                break
        l+=i-x[j]
        s-=x[j]

print(cnt)

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)

    
    return divisors

ans = 1

for div in make_divisors(sum(a)):
    mod_div = []
    for ai in a:
        mod_div.append(ai % div)
    mod_div.sort()

    tmp_p = n * div - sum(mod_div)
    tmp_m = 0

    for i, x in enumerate(mod_div):
        tmp_m += x
        tmp_p -= div - x
        if tmp_m == tmp_p and tmp_m <= k:
            ans = max(div, ans)

print(ans)

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)

    
    return divisors

ans = 1

for div in make_divisors(sum(a)):
    mod_div = []
    for ai in a:
        mod_div.append(ai % div)
    mod_div.sort()

    tmp_p = n * div - sum(mod_div)
    tmp_m = 0

    for i, x in enumerate(mod_div):
        tmp_m += x
        tmp_p -= div - x
        if tmp_m == tmp_p and tmp_m <= k:
            ans = max(div, ans)

print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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()
    return divisors

divs=make_divisors(sum(a))

ans=1
for i in range(len(divs)):
    r=[]
    d=divs[i]
    for j in range(n):
        if a[j]%d!=0:
            r.append(a[j]%d)
    r.sort()

    ruir=ruiseki(r)
    
    
    if ruir==[0]:
        ans=d
    for i in range(len(r)):
        hiku=ruir[i]
        tasu=-(ruir[-1]-ruir[i])+d*(len(r)-i)
        
        if hiku%d==tasu%d and max(hiku,tasu)<=k:
            ans=d

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,input().split())
a = [int(i) for i in input().split()]

def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]
 
 
def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

c = []
fct = factorize(sum(a))
for div in divisorize(fct):
    c.append(num(div))

c.sort(reverse=True)
ans = 1
from heapq import heapify,heappush,heappop

for num in c:
  chk = 0; cnt = 0
  sp = 0
  pl = []; mi = []
  heapify(pl); heapify(mi)
  for j in a:
    m = min(j%num,num-j%num)
    chk += m
    if m == j%num:
      cnt += m
      heappush(pl,-m)
    else:
      cnt -= m
      heappush(mi,-m)
  
  if cnt != 0:
    for i in range(abs(cnt)//num):
      if cnt > 0 and pl!=[]:
        p = heappop(pl)
        chk += (num+2*p)
      elif cnt < 0 and mi!=[]:
        q = heappop(mi)
        chk += (num+2*q)
        
  if chk <= 2*k:
    ans = num
    break
    
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
s = sum(A)
def md(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
P = md(s)
def test(x):
  L = sorted([a%x for a in A])
  M = sum(L)
  c = M//x
  for _ in range(c):
    M -= L.pop()
  return M <= k

for p in P:
  if test(p):
    print(p)
    break

Solution (Python):












def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from fractions import gcd

    
    

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2
        

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

    for i in kouho[::-1]:
        nega = [0]*n
        posi = [0]*n
        for j in range(n):
            posi[j] = a[j] % i
        posi.sort()
        for j in range(n):
            nega[j] = posi[j] - i
        posi = [0] + posi
        nega = [0] + nega
        posi = list(accumulate(posi))
        nega = list(accumulate(nega))
        for j in range(1, n+1):
            if posi[j] == -(nega[-1]-nega[j]):
                total = posi[j]
                break
        if total <= k:
            print(i)
            break
        
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from fractions import gcd

    
    

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2
        

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

    for i in kouho[::-1]:
        nega = [0]*n
        posi = [0]*n
        for j in range(n):
            posi[j] = a[j] % i
        posi.sort()
        for j in range(n):
            nega[j] = posi[j] - i
        posi = [0] + posi
        nega = [0] + nega
        posi = list(accumulate(posi))
        nega = list(accumulate(nega))
        total = 10**10
        for j in range(1, n+1):
            total = min(total, max(posi[j], -(nega[-1]-nega[j])))
        if total <= k:
            print(i)
            break
        
if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

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

def getDivisors(x):
    anss = set()
    for d in range(1, int(x**0.5)+1):
        if x%d == 0:
            anss.add(d)
            anss.add(x//d)
    return sorted(anss)

sumA = sum(As)
divs = getDivisors(sumA)

def check(x):
    Bs = [A%x for A in As if A%x]
    if not Bs:
        return True
    Bs.sort()
    accNums = list(accumulate(Bs))
    accNumRevs = list(accumulate([x-B for B in reversed(Bs)]))[::-1]
    for i in range(len(Bs)-1):
        if accNums[i] == accNumRevs[i+1] and accNums[i] <= K:
            return True
    return False

for div in reversed(divs):
    if check(div):
        print(div)
        break

Solution (Python):
N,K,*A = map(int, open(0).read().split())
pls = []
S = sum(A)
for i in range(1,int(S**0.5)+1):
  if S%i==0:
    pls.append(i)
    pls.append(S//i)
pls.sort()
ans = 0
for p in pls:
  B = [a%p for a in A]
  B.sort()
  i = 0
  j = N-1
  cnt = K
  while i<N:
    if B[i]!=0:
      break
    i += 1
  else:
    ans = p
    continue
  while True:
    a = B[i]
    b = B[j]
    if a<p-b:
      if cnt<a:
        break
      B[j] += a
      cnt -= a
      i += 1
    elif a>p-b:
      if cnt<p-b:
        break
      B[i] -= p-b
      cnt -= p-b
      j -= 1
    else:
      if cnt<a:
        break
      cnt -= a
      i += 1
      j -= 1
    if i>=j:
      ans = p
      break
print(ans)