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):
n, k = map(int, input().split())
a = list(map(int, input().split()))
m = sum(a)

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

for p in f:
  b = [x%p for x in a]
  b.sort()
  t = 0
  c = n
  for x in b:
    if x + t > k:
      break
    t += x
    c -= 1
  if c*p - sum(b) + t <= k:
    print(p)
    break

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

def canMake(n):
    B = [a % n for a in A]
    B.sort()

    left = 0
    right = sum(B)
    for i, b in enumerate(B, start=1):
        left += b
        right -= b
        if left == n * (N - i) - right:
            return left <= K
    return False

ans = 1
for i in range(1, int(S**0.5) + 100):
    if S % i != 0:
        continue
    k = S // i

    if canMake(i):
        ans = max(ans, i)
    if canMake(k):
        ans = max(ans, k)
        break

print(ans)

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

def ok(d):
    m = sorted(a % d for a in a)
    s, e, plus, minus = 0, len(m) - 1, 0, 0
    while True:
        if s > e:
            return (plus == minus)
        if plus <= minus:
            plus += m[s]
            if plus > k:
                return False
            s += 1
        else:
            minus += d - m[e]
            if minus > k:
                return False
            e -= 1
    return False

b = sum(a)
ret = 1
d = 1
while d * d <= b:
    if b % d == 0:
        if ok(d):
            ret = max(ret, d)
        if ok(b // d):
            ret = max(ret, b //d)
    d += 1
print(ret)

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


N, K = map(int, input().split())
A = list(map(int, input().split()))
divisors = divisor(sum(A))
for d in divisors[::-1]:
    rem = [a % d for a in A]
    rem.sort(reverse=True)
    i = sum(rem) // d
    if sum(rem[i:]) <= K:
        print(d)
        exit()

Solution (Python):
from heapq import heapify, heappush, heappop

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


N, K = map(int, input().split())
A = list(map(int, input().split()))
divisors = divisor(sum(A))
for d in divisors[::-1]:
    heap = []
    s = 0
    for a in A:
        x = a // d * d - a
        heap.append(x)
        s += -x
    heapify(heap)
    n = 0
    for _ in range(s // d):
        x = heappop(heap)
        if x + d > K:
            break
        else:
            if x + d > 0:
                n += x + d
            heappush(heap, x + d)
    else:
        if sum(abs(x) for x in heap) <= 2 * K:
            print(d)
            exit()

Solution (Python):
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a)
d=set()
for i in range(1,int(sum(a)**0.5)+5):
    if s%i==0: d.add(i);d.add(s//i)
d=sorted(list(d),reverse=True)
for x in d:
    b=sorted([a[i]%x for i in range(n)],reverse=True)
    s=sum(b)
    p=s//x
    if s-sum(b[:p])<=k: break
print(x)

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!=n//i:ass.append(n//i)
  return ass
_,k=map(int,input().split())
a=list(map(int,input().split()))
for ans in sorted(divisor(sum(a)))[::-1]:
  b=[i%ans for i in a if i%ans]
  n=len(b)
  b.sort()
  m=[0]+[i for i in b]
  p=[ans-i for i in b]+[0]
  for i in range(n):
    m[i+1]+=m[i]
    p[-i-2]+=p[-i-1]
  flag=False
  for i in range(n+1):
    if max(m[i],p[i])>k:continue
    if abs(m[i]-p[i])%ans!=0:continue
    flag=True
  if flag:print(ans);exit()

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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


S = sum(A)
divisors = []

for i in range(1, S):
    if S < i * i:
        break

    if S % i == 0:
        divisors.append(i)
        divisors.append(S // i)


def check(x):
    modX = [a % x for a in A if a % x != 0]
    modX.sort()

    L = len(modX)
    rtn = False

    for i in range(L):
        cnt = 0
        minus = modX[:i]
        plus = modX[i:]

        cnt_minus = sum(minus)
        cnt_plus = x * (L - i) - sum(plus)

        if cnt_minus <= K and cnt_plus <= K:
            rest = abs(cnt_minus - cnt_plus)
            if rest % x == 0:
                rtn = True
                break

    return rtn


ans = 1
for x in divisors:
    if check(x):
        ans = max(x, ans)

print(ans)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, 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(reverse=True)
    return divisors

G = make_divisors(s)

from itertools import accumulate

for g in G:
    B = [a%g for a in A]
    B.sort()
    B = [0] + B
    B = list(accumulate(B))
    p = 0
    q = 0
    for i in range(n-1):
        p = B[i+1]
        q = g*(n-1-i)-(B[-1]-B[i+1])
        if max(p, q) <= k and (p-q)%g == 0:
            break
    else:
        continue
    break
print(g)

Solution (Python):
from itertools import accumulate

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

N, K = map(int, input().split())
*A, = map(int, input().split())
cands = divisors(sum(A))
for d in sorted(cands, reverse=True):
    rems = sorted([a % d for a in A])
    cumsum_rems = [0] + list(accumulate(rems))
    for i in range(1, N):
        minus = cumsum_rems[i]
        plus = d * (N - i) - (cumsum_rems[N] - minus)
        if max(minus, plus) <= K: break
    else:
        continue
    break
print(d)

Solution (Python):

import sys
input = sys.stdin.readline

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

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

div = divisors(total)
ans = 1
for d in div:
    modd = []
    for item in a:
        modd.append(item % d)
    modd.sort(reverse=True)
    plus = sum(modd)
    opr = 0
    for i, item in enumerate(modd):
        if plus == 0:
            opr += sum(modd[i:])
            break
        plus -= d
        opr += d - item 

    if opr <= k * 2:
        ans = max(ans, d)
print(ans)

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

def isOk(n):
    B = [a % n for a in A]
    B.sort()

    now = 0
    S = sum(B)
    for i, b in enumerate(B[: -1]):
        now += b
        S -= b
        if now == n * (N - i - 1) - S and now <= K:
            return True
    return False

ans = 1
for i in range(1, int(S**0.5) + 100):
    if S % i != 0:
        continue
    j = S // i

    if isOk(i):
        ans = max(ans, i)
    if isOk(j):
        ans = max(ans, j)

print(ans)

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
ans = 1
div = []
for i in range(1,int(S**0.5)+2):
    if S%i == 0:
        if S//i != i:
            div.append(S//i)
            div.append(i)
        else:
            div.append(i)
div.sort()
L = []
for i in range(len(div)):
    cur = div[i]
    mod = []
    for j in range(n):
        if A[j]%cur != 0:
            mod.append(A[j]%cur)
    if len(mod) == 0:
        ans = max(ans, cur)
    else:
        mod.sort()
        mod_dash = []
        for j in range(len(mod)):
            mod_dash.append(cur-mod[j])
        mod2 = [mod[0]]
        mod3 = [mod_dash[0]]
        for j in range(1,len(mod)):
            t = mod2[j-1]+mod[j]
            mod2.append(t)
            u = mod3[j-1]+mod_dash[j]
            mod3.append(u)
        c = 10**10
        for j in range(1,len(mod2)):
            c = min(c, max(mod2[len(mod2)-j-1],mod3[len(mod3)-1]-mod3[len(mod3)-j-1]))
        if c <= k:
            ans = max(ans, cur)
print(ans)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().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


N, K = lr()
A = np.array(lr())
total = A.sum()
D = make_divisors(total) 
for d in D:
    B = A % d   
    B.sort()
    inc = d - B
    B_cum = B.cumsum()
    inc_cum = inc.cumsum()
    for i in range(N):
        x = B_cum[i]
        y = inc_cum[N-1] - inc_cum[i]
        if x > K: 
            break
        if y > K:
            continue
        if (x+y) // 2 <= K:
            print(d); exit()

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().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


N, K = lr()
A = np.array(lr())
total = A.sum()
D = make_divisors(total) 
for d in D:
    B = A % d   
    B.sort()
    inc = d - B
    B_cum = B.cumsum()
    inc_cum = inc.cumsum()
    for i in range(N):
        x = B_cum[i]
        y = inc_cum[N-1] - inc_cum[i]
        if x > K or y > K:
            continue
        if (x+y) // 2 <= K:
            print(d); exit()

Solution (Python):


import math



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

    s = sum(A)

    D1 = []
    D2 = []

    for i in range(1, int(math.sqrt(s))+1):
        if s%i == 0:
            D1.append(s//i)
            D2.append(i)

    for d in D1 + list(reversed(D2)):
        B = sorted([a%d for a in A])
        x = sum(B[:-sum(B)//d])
        
        if x <= K:
            print(d)
            return

main()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a)
ii=[]
for i in range(1,int(s**0.5)+1):
  if s%i>0:
    continue
  ii+=[i,s//i]
ii.sort(reverse=True)
for i in ii:
  r=[]
  for j in range(n):
    r+=[a[j]%i]
  r.sort()
  b=0
  l=0
  while l<n and b+r[l]<=k:
    b+=r[l]
    l+=1
  if sum([i-x for x in r[l:]]) <= k:
    print(i)
    break

Solution (Python):




from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys





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

M=sum(A)
maxi=round(M**.5)+2
lst=[]
i=2

for i in range(1,maxi):
    if M%i==0:
        lst.append(i)
        lst.append(M//i)


lst.sort(reverse=True)
for l in lst:
    B=deque(sorted([i%l for i in A if i%l!=0]))
    _K=K
    
    while len(B)>=2 and _K:

        n=min(B[0],l-B[-1],_K)
        B[0]-=n
        B[-1]+=n
        _K-=n
        if not B[0]%l:
            B.popleft()
        if not B[-1]%l:
            B.pop()

    if not B:
        print(l)
        exit()

Solution (Python):




from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys





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

M=sum(A)
maxi=round(M**.5)+2
lst=[]
i=2

for i in range(1,maxi):
    if M%i==0:
        lst.append(i)
        lst.append(M//i)


lst.sort(reverse=True)
for l in lst:
    B=deque(sorted([i%l for i in A if i%l!=0]))
    _K=K
    
    while len(B)>=2 and _K:

        n=min(B[0],l-B[-1],_K)
        B[0]-=n
        B[-1]+=n
        _K-=n
        if not B[0]%l:
            B.popleft()
        if not B[-1]%l:
            B.pop()

    if not B:
        print(l)
        exit()

Solution (Python):
from math import sqrt
from itertools import accumulate


def common_divisors(x):
    ret = []
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)

    return ret


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

sm = sum(a)
cd = common_divisors(sm)

ans = 0
for ecd in cd:
    r = [e % ecd for e in a]
    r.sort()
    sub = [0] + list(accumulate(r))
    add = [0] + list(accumulate(ecd - e for e in r[::-1]))
    add = add[::-1]
    for sb, ad in zip(sub, add):
        if sb == ad and sb <= k:
            ans = max(ans, ecd)

print(ans)

Solution (Python):
from math import sqrt
from itertools import accumulate


def common_divisors(x):
    ret = []
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)

    return ret


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

sm = sum(a)
cd = common_divisors(sm)

ans = 1
for ecd in cd:
    r = [e % ecd for e in a]
    r.sort()
    sub = [0] + list(accumulate(r))
    add = [0] + list(accumulate(ecd - e for e in r[::-1]))
    add = add[::-1]
    for sb, ad in zip(sub, add):
        if sb == ad and sb <= k:
            ans = max(ans, ecd)

print(ans)

Solution (Python):
from math import sqrt
from itertools import accumulate


def common_divisors(x):
    ret = []
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)

    return ret


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

sm = sum(a)
cd = common_divisors(sm)

ans = 1
for ecd in cd:
    r = [e % ecd for e in a]
    r.sort()
    acc = [0] + list(accumulate(r))
    for i in range(1, n + 1):
        sub = acc[i-1]
        add = ecd * (n - i + 1) - (acc[n] - acc[i-1])
        if sub == add:
            if sub <= k:
                ans = max(ans, ecd)

print(ans)

Solution (Python):

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


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

divisor.sort()

def judge(x):
    
    modlist = []
    for a in A:
        b = a%x
        modlist.append([b, x-b])
    modlist.sort()
    sum1 = [0]*(N+1)
    sum2 = [0]*(N+1)
    idx = 0
    for b,c in modlist:
        sum1[idx+1] = sum1[idx] + b
        sum2[idx+1] = sum2[idx] + c
        idx += 1
    
    res = 10**10
    for i in range(1,N+1):
        tmp = max(sum1[i], sum2[N]-sum2[i])
        res = min(res, tmp)
    
    if res>K:
        return False
    else:
        return True
    
ok = 1
for d in divisor:
    if judge(d):
        ok = d


print(ok)

Solution (Python):
import math

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

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

x=sum(A)

X=[]

for i in range(1,int(math.sqrt(x))+1):
    if x%i==0:
        X.append(i)
        X.append(x//i)
X.sort(reverse=True)

for i in X:
    B=[]
    for j in range(n):
        B.append(A[j]%i)
    B.sort()
    if sum(B[:-1*(sum(B)//i)])<=k:
        print(i)
        break

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

div = set()
for i in range(1, int(Asum ** 0.5 + 0.5) + 1):
    if Asum % i == 0:
        div.add(i)
        div.add(Asum//i)

ans = 1
for d in div:
    R = [a % d for a in A]
    R.sort()
    r = sum(R) // d
    l = N - r
    need = sum(R[:l])
    if need <= K:
        ans = max(ans, d)
print(ans)

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

div = set()
for i in range(1, int(Asum ** 0.5 + 0.5) + 1):
    if Asum % i == 0:
        div.add(i)
        div.add(Asum//i)

ans = 1
for d in div:
    now = 10 ** 18
    R = [a % d for a in A]
    R.sort()
    Rsum = sum(d - r for r in R)
    Lsum = 0
    for r in R:
        Lsum += r
        Rsum -= d - r
        now = min(now, max(Lsum, Rsum))

    if now <= K:
        ans = max(ans, d)

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


def SumArea(r, l, a2):
    return a2[l]-a2[r]

def judge(cand, a, k):
    m_list = [i%cand for i in a]
    m_list.sort()
    p_list = [cand-r for r in m_list]
    
    
    b=list(range(1,30))
    m2=[0]
    p2=[0]
    for i in m_list:m2.append(m2[-1]+i)
    for i in p_list:p2.append(p2[-1]+i)
        
    length = len(a)
    for i in range(length):
        m_total  = SumArea(0, i, m2)
        p_total = SumArea(i, length, p2)
        if m_total == p_total and p_total <= k:
            return True
    return False
    
        
n,k = map(int, input().split())
a = list(map(int, input().split()))
pflag = True

total = sum(a)
length = len(a)
candidate = make_divisors(total)
candidate.sort(reverse = True)
for cand in candidate:
    if judge(cand, a, k):
        print(cand)
        pflag = False
        break
if pflag:
    print(1)

Solution (Python):
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return a // gcd(a, b) * b

def isPrime(x):
    if x < 2 or x % 2 == 0:
        return False
    if x == 2:
        return True
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 2
    return True

def divisor(x):
    res = []
    i = 1
    while i * i <= x:
        if x % i == 0:
            res.append(i)
            if i * i != x:
                res.append(x // i)
        i += 1
    res = sorted(res)
    return res

def factor(x):
    res = []
    if x == 1:
        res.push_back(1)
        return res
    i = 2
    while i * i <= x:
        while x % i == 0:
            res.append(i)
            x //= i
    if x != 1:
        res.append(x)
    res = sorted(res)
    return res

        


if __name__ == "__main__":
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A = sorted(A)
    sum_v = sum(A)
    div = divisor(sum_v)
    div = sorted(div, reverse=True)
    for e in div:
        ok = True
        b = [int(a % e) for a in A]
        b = sorted(b)
        v = sum(b)
        v //= e
        ans = 0
        for i in range(N-v):
            ans += b[i]
        
        if ans <= K:
            print(e)
            exit()

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

S = sum(A)
ans = 0

for i in range(1,int(S**0.5)+1):
    if S%i != 0:
        continue
        
    for j in range(2):
        d = i if j else S//i
        B = sorted(map(lambda a:a%d,A))
        C = [0]
        for k in range(N):
            C.append(C[-1]+B[k])
            
        for k in range(N+1):
            if ((N-k)*d-(C[-1]-C[k])-C[k])%d == 0:
                if max(C[k],(N-k)*d-(C[-1]-C[k])) <= K:
                    ans = max(ans,d)
                    
print(ans)

Solution (Python):
def main():
    N,K,*A=map(int, open(0).read().split())
    S=sum(A)
    X=[S]
    for i in range(2,int(S**.5)+1):
        if S%i==0:
            X.append(i)
            if i*i!=S:
                X.append(S//i)
    ans=1
    for x in X:
        B=[a%x for a in A]
        y=sum(B)//x
        z=sum(sorted(B, reverse=True)[y:])
        if z<=K:
            ans=max(ans,x)
    print(ans)

if __name__ == "__main__":
    main()

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

def yaku(N):
    res = []
    for i in range(1, round(N**(1/2)) + 3 ):
        if N%i == 0:
            res.append(i)

    res2 = [N//i for i in res]
    res = list(set(res + res2))
    return res

ys = yaku(sum(A))
ys.sort(reverse=True)
for y in ys:
    M = [a%y for a in A if a%y]
    ma = 0
    mi = y*len(M) - sum(M)
    M.sort()
    for m in M:
        ma += m
        mi -= (y - m)
        if ma == mi:
            break
    if ma <= K:
        print(y)
        exit()

Solution (Python):
import heapq as h

def partions(M):
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d


N,K=map(int,input().split())
A=list(map(int,input().split()))
s=sum(A)
candidate=partions(s)
ans=1
for i in range(0,len(candidate)):
    X=[A[j]%candidate[i] for j in range(0,N)]
    s=sum(X)//candidate[i]
    test=0
    h.heapify(X)
    for j in range(0,N-s):
        test=h.heappop(X)
    test=candidate[i]*s-sum(X)
    if K>=test:
        ans=candidate[i]
print(ans)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr())
sum = A.sum()


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

B = make_divisors(sum)

for x in B[::-1]:
    c = A % x
    c.sort()
    d = x - c
    c_cum = c.cumsum()
    d_cum = d.cumsum()
    
    for i in range(N):
        y = c_cum[i]
        z = d_cum[N-1] - d_cum[i]
        if y > K or z > K:
            continue
        result = (y + z) // 2
        if result <= K:
            print(x)
            exit()

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):
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:
    A_mod = sorted([a % X for a in A])
    U = [X - a for a in A_mod]
    D = [-a for a in A_mod]  

    U = list(accumulate(U))
    D = list(accumulate(D))

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

        if -D[i] == (U[-1] - U[i]):
            ans = max(ans, X)
            break

print(ans)

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

S = sum(A)
candidates = []
for i in range(1, int(S**0.5)+1):
    if S%i:continue
    a, b = i, S//i
    
    candidates.append(a)
    if a!=b:
        candidates.append(b)
candidates.sort()

ans = 0
for d in candidates:
    rems = []
    rems_size, rems_sum = 0, 0

    for i in A:
        if i%d:
            rems.append(i%d)
            rems_size += 1
            rems_sum += i%d

    rems.sort()

    a = 0
    for i, j in enumerate(rems[:-1], start=1):
        a += j
        b = d*(rems_size-i)-(rems_sum-a)
        if max(a, b)<=K:
            ans = max(ans, d)
    if not rems:
        ans = max(ans, d)

print(ans)

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

S = sum(A)
candidates = []
for i in range(1, int(S**0.5)+1):
    if S%i:continue
    a, b = i, S//i
    
    candidates.append(a)
    if a!=b:
        candidates.append(b)
candidates.sort()

ans = 0
for d in candidates:
    rems = []
    rems_size, rems_sum = 0, 0

    for i in A:
        if i%d:
            rems.append(i%d)
            rems_size += 1
            rems_sum += i%d

    rems.sort()

    a = 0
    for i, j in enumerate(rems[:-1], start=1):
        a += j
        b = d*(rems_size-i)-(rems_sum-a)
        if max(a, b)<=K:
            ans = max(ans, d)
    if not rems:
        ans = max(ans, d)

print(ans)

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

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

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

S=sum(A)
lst=make_divisors(S)

ans=1
B=[0]*N
for u in lst:
    for i in range(N):
        B[i]=A[i]%u
    B.sort()
    kkk=0
    s=0
    while kkk<N and s+B[kkk]<=K:
        s+=B[kkk]
        kkk+=1
    t=0
    for i in range(kkk,N):
        t+=u-B[i]
    if s>=t:
        ans=u

print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
import math
from collections import defaultdict, Counter

def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d
MOD = 10**9 + 7
INF = 10**10

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

    return divisors

def judge(anums, cand, k):
    anums = sorted([num % cand for num in anums])
    rem = sum([(cand - num) for num in anums])
    acc = [0]
    tmp = 0
    ue = 0
    
    for num in anums:
        tmp += num
        acc.append(tmp)

    if acc[rem // cand] <= k:
        return True
    else:
        return False


def main():
    n,k = getlist()
    anums = getlist()

    candidates = make_divisors(sum(anums))
    
    for cand in sorted(candidates, key=lambda x: -x):
        res = judge(anums, cand, k)
        if res:
            print(cand)
            return





if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Solution (Python):
N, K = map(int, input().split())
A = [int(c) for c in input().split()]
S = sum(A)
pls = []
for i in range(1,S):
  if i*i>S:
    break
  if S%i==0:
    pls += [i]
    pls += [S//i]
pls.sort(reverse=True)
for p in pls:
    B = []
    for i in range(N):
      B += [A[i]%p]
    B.sort()
    for j in range(N):
      if B[j]!=0:
        break
    m = j
    lim = N-1
    cnt = 0
    while m<lim:
      if B[m]<p-B[-1]:
        B[-1] += B[m]
        cnt += B[m]
        B[m] = 0
        m += 1
      elif B[m]>p-B[-1]:
        cnt += p-B[-1]
        B[m] -= p-B[-1]
        B.pop()
        lim -= 1
      else:
        B.pop()
        cnt += B[m]
        B[m] = 0
        m += 1
        lim -= 1
    if B[-1]==0 and cnt<=K:
      print(p)
      break

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

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

divs.sort(reverse=True)

for d in divs:
    rest = [a % d for a in A]
    rest.sort(reverse=True)
    restSum = sum(rest) // d
    cnt = 0
    for i in range(restSum):
        cnt += d - rest[i]
    if cnt <= K:
        print(d)
        exit()

Solution (Python):
from heapq import heappush, heappop


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

divs = []
maxA = sum(A)
for i in range(1, int(maxA ** 0.5) + 1):
    if maxA % i == 0:
        heappush(divs, -i)
        j = maxA // i
        if i != j:
            heappush(divs, -j)

while True:
    d = -heappop(divs)
    q = []
    asum = 0
    for a in A:
        rest = a % d
        asum += rest
        heappush(q, -rest)
    cnt = 0
    for i in range(asum // d):
        cnt += d - (-heappop(q))
    if cnt <= K:
        print(d)
        exit()

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():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    div = sorted(divisor(sum(A)), reverse=True)
    ans = 0
    for d in div:
        mod = [0] * N
        for i in range(N):
            mod[i] = A[i] % d
        sort_mod = sorted(mod)
        cnt = float('inf')
        rsum = d * N - sum(sort_mod)
        lsum = 0
        for j in range(N):
            lsum += sort_mod[j]
            rsum -= d - sort_mod[j]
            tmp = max(lsum, rsum)
            cnt = min(cnt, tmp)
        if cnt <= K:
            print(d)
            exit()

    


if __name__ == "__main__":
    main()

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:
    alpha = sorted([(a % X) for a in A])
    beta = [X - a for a in alpha]

    alpha = list(accumulate(alpha))
    beta = list(accumulate(beta))

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

        if alpha[i] == (beta[-1] - beta[i]):
            ans = max(ans, X)
            break

print(ans)