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.buffer.readline

def divisors(n) -> list:
  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)
  res = sorted(res)[::-1]
  return res

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

div = divisors(sum(A))

for d in div:
  arr = []
  for a in A:
    if a % d != 0:
      arr.append(d - a % d)
    else:
      arr.append(0)
  arr = sorted(arr)[::-1]
  tmp = sum(arr[sum(arr) // d:])
  if tmp <= K:
    print(d)
    exit()

Solution (Python):
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = sum(A)


ans_candidates = []
for n in range(1, int(M ** 0.5) + 1):
    if M % n == 0:
        ans_candidates.append(n)
        ans_candidates.append(M // n)


ans = 0
for X in ans_candidates:
    need_plus = sorted([(X - a % X) % X for a in A])
    need_minus = [X - nm for nm in need_plus]

    need_plus = list(accumulate(need_plus))
    need_minus = list(accumulate(need_minus))

    for i in range(N):
        if need_plus[i] > K:
            break

        if need_plus[i] == (need_minus[-1] - need_minus[i]):
            ans = max(ans, X)
            break

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

div=make_divisors(sum(A))

ans=0
for g in div:
    near=[0]*N
    S=0
    for i in range(N):
        near[i]=a=A[i]%g
        S+=near[i]
    near.sort()
    ii=0
    while S!=0:
        S-=g
        ii-=1
    temp=sum(near[:ii])
    if temp<=K:
        ans=max(ans,g)
        
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = LI()
    s = sum(a)
    dv = set([1,s])
    for i in range(2,int(s**0.5)+5):
        if s%i == 0:
            dv.add(i)
            dv.add(s//i)

    def f(i):
        pm = []
        for c in a:
            t = c % i
            if t == 0:
                continue
            pm.append((i-t, t))
        pm.sort()
        p = pi = m = 0
        mi = len(pm) - 1
        while pi <= mi:
            if p < m:
                p += pm[pi][0]
                pi += 1
            else:
                m += pm[mi][1]
                mi -= 1
        return max(p,m) <= k

    r = 1
    for c in dv:
        if f(c):
            if r < c:
                r = c

    return r


print(main())

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    sA = sum(A)
    divs = []
    i = 1
    while i * i < sA:
        if sA % i == 0:
            divs.append(i)
            divs.append(sA // i)
        i += 1
    if i * i == sA:
        divs.append(i)
    divs.sort()
    for d in reversed(divs):
        t = [i % d for i in A]
        t.sort()
        k = sum(t[:-sum(t) // d])
        if k <= K:
            return d

print(main())

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    m = sum(A)
    d = []
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            d.append(i)
            if i != m // i:
                d.append(m//i)
    d.sort(reverse=True)
    for j in d:
        if j > K + max(A):
            continue
        l = []
        for i in A:
            l.append(i % j)
        t = N - sum(l) // j
        l.sort()
        if sum(l[:t]) <= K:
            print(j)
            return
    print(1)
main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def find_divisor(n):
    divisors=[]
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n // i)
    return divisors


def main():
    N,M = MI()
    A = LI()
    S = sum(A)
    pri = find_divisor(S)
    ans = 0
    for p in pri:
        
        B = [a%p for a in A]
        B.sort()
        B_rev = [b-p if b else 0 for b in B ]
        *cumsum, = accumulate(B)
        cumsum_rev = [0]*(N+1)
        now = 0
        for i in range(N)[::-1]:
            now += B_rev[i]
            cumsum_rev[i] = now
        
        for i in range(N):
            if (cumsum[i] + cumsum_rev[i+1]) % p == 0:
                c = max(cumsum[i], -cumsum_rev[i+1])
                if c<=M:
                    ans = max(ans, p)
    print(ans)
if __name__ == '__main__':
    main()

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

sum_a = sum(a)
divisors = sorted(make_divisors(sum_a), reverse=True)

for div in divisors:
    if(sum_a % div != 0):
        continue

    mod_a = []
    for ai in a:
        mod_a.append(ai % div)
    mod_a = sorted(mod_a)

    sum_mod_a = sum(mod_a)
    k_min = sum(mod_a[: (n-sum_mod_a//div) ])

    if(k_min <= k):
        print(div)
        exit()


print(-1)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
max_div = int(S**0.5)


small_div = []
large_div = []
for i in range(1, max_div+1):
  if S%i == 0:
    small_div.append(i)
    large_div.append(S//i)


div = large_div + small_div[::-1]

ans = 1
for d in div:
  r = []
  for a in A:
    r.append(a%d)
  
  r.sort()
  
  minus = [0]*(N+1)
  plus = [0]*(N+1)
  for i, ri in enumerate(r, 1):
    minus[i] = minus[i-1] + ri
  
  for i, ri in enumerate(r[::-1], 1):
    plus[i] = plus[i-1] + (d - ri)
  
  plus = plus[::-1]
  for m, p in zip(minus, plus):
    if m == p and m <= K:
      ans = d
      break
  
  else:
    continue
  
  break

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
max_div = int(S**0.5)


small_div = []
large_div = []
for i in range(1, max_div+1):
  if S%i == 0:
    small_div.append(i)
    large_div.append(S//i)


div = large_div + small_div[::-1]

ans = 1
for d in div:
  r = []
  for a in A:
    r.append(a%d)
  
  r.sort()
  
  minus = [0]*(N+1)
  plus = [0]*(N+1)
  for i, ri in enumerate(r, 1):
    minus[i] = minus[i-1] + ri
  
  for i, ri in enumerate(r[::-1], 1):
    plus[i] = plus[i-1] + (d - ri)
  
  plus = plus[::-1]
  for m, p in zip(minus, plus):
    if m == p and m <= K:
      ans = d
      break
  
  else:
    continue
  
  break

print(ans)

Solution (Python):
import sys,math
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def divisorlist(z):
    if len(z)==1:
        return [z[0][0]**i for i in range(z[0][1]+1)]
    y = divisorlist(z[1:])
    s = []
    for i in range(z[0][1]+1):
        for j in y:
            s.append((z[0][0]**i)*j)
    return s

n,k = inm()
a = inl()
sm = sum(a)
zz = prime_division(sm)
z = divisorlist(zz)
z.sort(reverse=True)
ddprint(z)
for p in z:
    if p>sm+k:
        continue
    b = [ai%p for ai in a]
    b.sort()
    s = sum(b)
    m = s//p
    t = sum(b[:n-m])
    ddprint("p {} b {} s {} m {} t {}".format(p,b,s,m,t))
    if t<=k:
        print(p)
        exit()

Solution (Python):
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

N, K = map(int,input().split())
A = list(map(int,input().split()))
for d in reversed(divisors(sum(A))):
    R = sorted(a % d for a in A)
    
    if sum(R[:-sum(R) // d]) <= K:
        print(d)
        quit()

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,K=LI()
AS=LI()
SUMM= sum(AS)

DIVS=set()
for i in range(1,40000):
    if SUMM % i == 0:
        DIVS.add(i)
        DIVS.add(SUMM//i)


DIFF=[0]*N

res = 0
for div in DIVS:
    for i in range(N):
        DIFF[i] = AS[i]%div
    DIFF.sort()
    i = 0
    j = N-1
    sm = 0
    cost = 0
    while i <= j:
        if sm + DIFF[j] >= div:
            sm -= (div - DIFF[j])
            j -= 1
        else:
            cost += DIFF[i]
            sm += DIFF[i]
            i += 1
    
    if cost <= K: res = max(res, div)


print(res)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,K=LI()
AS=LI()
SUMM= sum(AS)

DIVS=set()
for i in range(1,40000):
    if SUMM % i == 0:
        DIVS.add(i)
        DIVS.add(SUMM//i)



DIFF=[0]*N
ACC=[0]*N



for div in sorted(DIVS, reverse=True):
    for i in range(N):
        DIFF[i] = AS[i]%div
    DIFF.sort()
    ACC[0] = DIFF[0]
    for i in range(1,N): ACC[i] = ACC[i-1] + DIFF[i]
    
    for i in range(N-1):
        left = ACC[i]
        right = (N-1-i)*div-(ACC[N-1]-ACC[i])
        if left%div == right%div:
            if max(left, right) <= K:
                
                print(div)
                exit()

Solution (Python):
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
suma = sum(a)
devisor = []
for i in range(1,int(suma**0.5)+1):
  if suma%i == 0:
    devisor.extend((i,suma//i))
devisor.sort(reverse=True)
for x in devisor:
  b = [a[i]%x for i in range(n)]
  b.sort()
  sumb = list(accumulate(b))
  for y in range(n-1):
    bf = sumb[y]
    bl = sumb[n-1]-sumb[y]
    if bf%x == (x-(bl%x))%x:
      if k>=max(bf,(n-1-y)*x-bl):
        print(x)
        exit()
      else:
        continue

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

sumA = sum(A)

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()
  divisors = divisors[::-1]
  return divisors

div = make_divisors(sumA)


for d in div:
  tmp = []
  for a in A:
    tmp.append(a % d)
  tmp.sort()
  tmp = tmp[::-1]
  sum_tmp = sum(tmp)
  
  if sum(tmp[sum_tmp // d:]) <= K:
    print(d)
    exit()

Solution (Python):
def get_divisor(num, max_val):
    ret = []
    num_sq = int(num**0.5)
    for k in range(1, num_sq+1):
        if num % k == 0:
            if k <= max_val: ret.append(k)
            if num//k <= max_val: ret.append(num//k)
            
    return ret


def solve():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    sum_A = sum(A)
    max_A = max(A)
    div = get_divisor(sum_A, max_A+K)
    ret = 1
    for d in div:
        sum_k = 0
        red_k = 0
        flag = True
        mod_d = [a%d for a in A]
        mod_d.sort()
        
        for a in mod_d:
            if sum_k+a <= K:
                sum_k += a
            else: 
                red_k += d-a
            if sum_k-red_k < 0:
                break

        if (sum_k-red_k)%d == 0: ret = max(ret, d)
            
    print(ret)
    
solve()

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

divisors = []
for i in range(1,int(s**0.5)+1):
    if s%i==0:
        divisors.append(i)
        divisors.append(s//i)
divisors = list(set(divisors))
divisors.sort(reverse=True)

def possible(n):
    a = []
    for i in range(N):
        if A[i]%n != 0:
            a.append(A[i]%n)
    a.sort()
    k = 0
    while k <= K and a:
        m = a[0]
        M = a[-1]
        if m <= n-M:
            k += m
            a[-1] = (M+m)%n
            a[0] = 0
        else:
            k += n-M
            a[0] = (m-n+M)%n
            a[-1] = 0
        if a[0]==0:
            a = a[1:]
        if a[-1]==0:
            a = a[:-1]
        a.sort()
    return k<=K

for n in divisors:
    if possible(n):
        ans = n
        break

print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
num=sum(A)
L=[]
cnt=0
for i in range(2,10**5+1):
    while num%i==0:
        num//=i
        cnt+=1
    if cnt>0:
        L.append([i,cnt])
        cnt=0
if num>1:
    L.append([num,1])

import copy
L1=[1]
L2=[]
for i in range(len(L)):
    for j in range(len(L1)):
        for k in range(L[i][1]+1):
            L2.append(L1[j]*L[i][0]**k)
    L1=copy.deepcopy(L2)
    L2=[]
L1.sort(reverse=True)


for i in range(len(L1)):
    C=[]
    for j in range(N):
        C.append(A[j]%L1[i])
    C.sort(reverse=True)
    D=sum(C)
    E=0
    cnt=0
    for k in range(len(C)):
        if D==E:
            break
        else:
            D-=(C[k])
            E+=(L1[i]-C[k])
    if E<=K:
        print(L1[i])
        exit()

Solution (Python):
import  numpy as np


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


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    np.cumsum(mods, out=mods)
    idx = mods[n-1] // div
    count = mods[-1-idx]
    if count <= k:
        print(div)
        exit()

Solution (Python):
import  numpy as np


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


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    subcum = np.cumsum(mods)
    idx = subcum[n-1] // div
    count = subcum[-1-idx]
    if count <= k:
        print(div)
        exit()

Solution (Python):
import  numpy as np


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


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    add = div - mods

    addcum = np.cumsum(add)
    subcum = np.cumsum(mods)
    for i in range(n):
        addcount = addcum[n-1] - addcum[i]
        subcount = subcum[i]
        if addcount == subcount and addcount <= k:
            print(div)
            exit()

Solution (Python):
import numpy as np



def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(list(divisors))


N, K, *A = map(int, open(0).read().split())

A = np.array(A, np.int64)
d = make_divisors(A.sum())

for i in d[::-1]:
    r = A % i
    r = r[r.nonzero()]
    l = r.size
    if l == 0:
        print(i)
        exit()
    else:
        n = np.arange(l - 1, 0, -1)
    r.sort()
    np.cumsum(r, out=r)
    if np.any((r[:-1] == i * n - (r[-1] - r[:-1])) & (r[:-1] <= K)):
        print(i)
        exit()

Solution (Python):
import numpy as np



def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(list(divisors))


N, K, *A = map(int, open(0).read().split())

A = np.array(A, np.int64)
d = make_divisors(A.sum())

for i in d[::-1]:
    r = A % i
    r = r[r != 0]
    l = r.size
    if l == 0:
        print(i)
        exit()
    else:
        n = np.arange(l - 1, 0, -1)
    r.sort()
    np.cumsum(r, out=r)
    if np.any((r[:-1] == i * n - (r[-1] - r[:-1])) & (r[:-1] <= K)):
        print(i)
        exit()

Solution (Python):
import numpy as np



def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(list(divisors))


N, K, *A = map(int, open(0).read().split())

A = np.array(A, np.int64)
d = make_divisors(A.sum())

for i in d[::-1]:
    r = A % i
    r = r[r != 0]
    l = r.size
    if l == 0:
        print(i)
        exit()
    else:
        n = np.arange(l - 1, 0, -1)
    r.sort()
    np.cumsum(r, out=r)
    equal = np.where(r[:-1] == i * n - (r[-1] - r[:-1]))[0]
    if np.any(r[equal] <= K):
        print(i)
        exit()

Solution (Python):
import numpy as np



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, *A = map(int, open(0).read().split())

A = np.array(A, np.int64)
d = make_divisors(A.sum())

for i in d[::-1]:
    r = A % i
    r.sort()
    r = r[r != 0]
    if r.size == 0:
        print(i)
        exit()
    else:
        n = np.arange(r.size - 1, 0, -1)

    np.cumsum(r, out=r)
    equal = np.where(r[:-1] == i * n - (r[-1] - r[:-1]))[0]
    if np.any(r[equal] <= K):
        print(i)
        exit()

Solution (Python):
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

M = sum(A)
L = []
i = 1
while i <= M**0.5:
    if M%i == 0:
        L.append(i)
        L.append(M//i)
    i += 1
    
L.sort(reverse=True)

for i in L:
    temp = [0]*N
    for j in range(N):
        temp[j] = A[j]%i
    temp.sort()
    cnt = 0
    l = 0
    r = N-1
    while l < r:
        if temp[l] == 0:
            l += 1
            continue
        if temp[r] == 0:
            r -= 1
            continue
        t = temp[l]
        temp[l] = 0
        cnt += t
        while l < r and temp[r]+t > i:
            t -= i-temp[r]
            temp[r] = 0
            r -= 1
        temp[r] += t
        temp[r] %= i
            
    if cnt <= K:
        ans = i
        break

print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
As = list(map(int, input().split()))
rs = []
a = sum(As)
for i in range(a):
    i += 1
    if a % i == 0:
        rs.append(i)
        rs.append(a//i)
    if a < i**2:
        break
rs = sorted(rs)[::-1]
for r in rs:
    Bs = sorted([A%r for A in As])
    sum1 = 0
    sum2 = r*N - sum(Bs)
    R = None
    for b in Bs:
        sum1 += b
        sum2 -= r - b
        if abs(sum1 - sum2) % r == 0:
            if max(sum1, sum2) > K:
                continue
            R = r
            break
    if R:
        break
print(R)

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

def answer_is_X(X):
    mod = deque(sorted([i%X for i in A if i%X != 0]))
    answer = 0
    while mod:
        Amin = mod.popleft()
        answer += Amin
        while Amin > 0:
            
            if not mod:
                return False
            Amax = mod.pop()
            sub = X - Amax
            if sub <= Amin:
                Amin -= sub
            else:
                Amax += Amin
                mod.append(Amax)
                Amin = 0

    if answer <= K:
        return True
    else:
        return False

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 = [int(i) for i in input().split()]

sumA_divisors = make_divisors(sum(A))

answer = 0
for i in sumA_divisors:
    if answer_is_X(i):
        answer = i

print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    D=divisors(sum(A))

    def check(d):
        B=[a%d for a in A]
        B.sort()
        res=INF
        for i in range(n):
            minus=sum(B[:i])
            plus=sum(d-b for b in B[i:])
            res=min(res,max(minus,plus))
        return res<=k

    print(max(d for d in D if(check(d))))
resolve()

Solution (Python):


def solve():
    n, k = map(int, input().split())
    a = tuple(sorted(map(int, input().split()), reverse=True))

    sum_a = sum(a)
    e = set()
    divisor = 1
    while divisor * divisor <= sum_a:
        if sum_a % divisor == 0:
            e.add(divisor)
            e.add(sum_a // divisor)
        divisor += 1

    e = sorted(e, reverse=True)
    

    for cand in e:
        r = tuple(sorted(x % cand for x in a if x % cand != 0))

        accm = [0]
        t = 0
        for x in r:
            t += x
            accm.append(t)

        accp = [0]
        t = 0
        for x in r:
            t += cand - x
            accp.append(t)

        m = len(r)
        for i in range(m + 1):
            if (accm[i] == (accp[m] - accp[i])) and (accm[i] <= k):
                return cand
    return -1


print(solve())

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

asum=sum(a)


def divisor(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=divisor(asum)

b=[0]*n

ans=0
for d in div:
    count=0
    
    
    for i in range(n):
        b[i]=a[i]%d
    b.sort()
    
    que=deque(b)
    
    while que:
        s=que.popleft()
        if s==0:
            continue
        if len(que)==0:
            count=0
            break
        g=que.pop()
        
        if s==d-g:
            count+=s
        if s<d-g:
            que.append(s+g)
            count+=s
        if s>d-g:
            que.appendleft(s-d+g)
            count+=(d-g)
    
    if count<=k:
        ans=d
print(ans)

Solution (Python):
n,k=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
s=sum(a)
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
l=make_divisors(s)
ans=1
from itertools import accumulate
for i in l[::-1]:
    ll=[]
    for j in a:
        ll.append(j%i)
    ll.sort()
    if sum(ll[:n-sum(ll)//i])<=k:
        print(i)
        exit()

Solution (Python):
N,K = map(int,input().split())
A = [int(i) for i in input().split()]
S = sum(A)

def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(40000)

lis = []
for p in plis:
    if S%p == 0:
        lis.append([p,1])
        S = S//p
        while S%p == 0:
            lis[-1][1] += 1
            S = S//p
    if S == 1:
        break
if S != 1:
    lis.append([S,1])

yakulis =[1]
for l in lis:
    for j in range(len(yakulis)):
        for k in range(l[1]):
            n = yakulis[j]
            yakulis.append(l[0]**(k+1)*n)
yakulis.sort(reverse=True)

s = True
for r in yakulis:
    B = [i%r for i in A]
    B.sort()
    le = -1
    ri = N
    while ri-le > 1:
        mid = (le+ri)//2
        pl = sum(B[:mid+1])
        mi = r*(N-1-mid) - sum(B[mid+1:])
        if pl > mi:
            ri = mid
        else:
            le = mid
    k = sum(B[:le+1])
    if k <= K:
        s = False
        print(r)
        break
if s:
    print(1)

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

all_sum = sum(A)


divisors = []


for i in range(1,all_sum+1):
    if i * i > all_sum:
        break
    if all_sum % i != 0:
        continue
    divisors.append(i)
    if all_sum // i != i:
        divisors.append(all_sum // i)


divisors.sort(reverse=True)

def ok(d):
    
    a = [x % d for x in A]
    
    
    move = n - sum(a) // d
    a.sort()
    
    
    return sum(a[:move]) <= k

for d in divisors:
    if ok(d):
        print(d)
        break

Solution (Python):


import sys

n,k = map(int,input().split())
al = 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

divisors = sorted(make_divisors(sum(al)), reverse=True)

for i in divisors:
    point = 0
    div_l = sorted([a%i for a in al if a%i > 0])
    while div_l:
        if div_l[0] < i - div_l[-1]:
            div_l[-1] += div_l[0]
            point += div_l[0]
            div_l.pop(0)
        else:
            div_l[0] -= (i - div_l[-1])
            point += i - div_l[-1]
            div_l.pop(-1)
            
    
    if point <= k:
        print(i)
        sys.exit()

Solution (Python):
from itertools import accumulate

def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

N, K, *A = map(int, open(0).read().split())

for d in reversed(divisors(sum(A))):
    R = [0] + list(accumulate(sorted(a % d for a in A)))
    for i in range(N):
        l = R[i]
        r = (N - i) * d - (R[N] - R[i])
        if max(l, r) <= K:
            print(d)
            quit()

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(p)
    check(b)
l.reverse()

for b in l:
    check(b)