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):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    a,b,c = LI()
    c -= a-b
    print(max(0,c))
    return


def B():
    n = I()
    ans = 0
    for i in range(1,n+1):
        s = str(i)
        if len(s)%2:
            ans += 1
    print(ans)
    return


def C():
    n = I()
    h = LI()
    h[0] -= 1
    for i in range(n-1):
        if h[i+1] < h[i]:
            print("No")
            return
        if h[i+1] > h[i]:
            h[i+1] -= 1
    print("Yes")
    return


def D():
    s = S()
    n = len(s)
    ans = [0]*n
    l = 0
    i = 0
    while i < n:
        if s[i] == "L":
            j = i
            while i < n and s[i] == "L":
                i += 1
                l += 1
            if l:
                if (l+j-i)%2:
                    ans[j-1] = l-l//2
                    ans[j] = l//2
                else:
                    ans[j-1] = l//2
                    ans[j] = l-l//2
            l = 0
        else:
            l += 1
            i += 1
    print(*ans)
    return


def E():
    def factor(n):
        if n == 1:
            return [1]
        if n < 4:
            return [1,n]
        i = 2
        res = [1]
        while i**2 <= n:
            if n%i == 0:
                res.append(i)
                if n//i != i:
                    res.append(n//i)
            i += 1
        res.append(n)
        res.sort()
        return res

    n,k = LI()
    a = LI()
    s = sum(a)
    f = factor(s)
    for i in f[::-1]:
        s = 0
        b = [[a[j]%i,-a[j]%i] for j in range(n)]
        b.sort()
        for j in range(n-1):
            b[j+1][0] += b[j][0]
            b[j+1][1] += b[j][1]
        for j in range(n-1):
            if b[j][0] == b[n-1][1]-b[j][1]:
                break
        s = b[j][0]
        if s <= k:
            print(i)
            return
    return


def F():

    return


if __name__ == "__main__":
    E()

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

def get_divisor(n):
    a,b = [],[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            a.append(i)
            b.append(n//i)
    if a[-1]==b[-1]:b.pop()
    a.extend(b[::-1])
    return a

div_list = get_divisor(sum(A))

for n in div_list[::-1]:
    d = [0]*N
    for i,a in enumerate(A):
        if a%n <= n//2:
            d[i] = -(a%n)
        else:
            d[i] = (-a)%n
    Sd = sum(d)
    if Sd != 0:
        d.sort()
        i = 0
        while Sd<0:
            d[i] += n
            Sd += n
            i+=1
        i = N-1
        while Sd>0:
            d[i] -= n
            Sd -= n
            i -=1
    check = sum(t for t in d if t>0)
    if check<=K:
        print(n)
        break

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

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

x=sum(A)
import math
xr=math.ceil(math.sqrt(x))

LIST=[]
for i in range(1,xr+1):
    if x%i==0:
        LIST.append(i)
        LIST.append(x//i)

ANS=1

for l in LIST:
    count=0

    B=[a%l for a in A]
    B.sort()

    i=0
    j=N-1

    for i in range(N):
        if B[i]%l==0:
            continue
        else:
            count_temp=B[i]
            count+=count_temp
            B[i]=0

            while count_temp:
                while B[j]%l==0:
                    j-=1
                MINUS=min(count_temp,l-B[j])
                B[j]+=MINUS
                count_temp-=MINUS

    if count<=K:
        ANS=max(ANS,l)

print(ANS)

Solution (Python):

import sys


def factors(n):
    L = []
    for i in range(1, n+1):
        if i * i > n:
            break
        if n % i == 0:
            L.append(i)
            if n // i != i:
                L.append(n // i)
    return L


def solve(N: int, K: int, A: "List[int]"):
    facts = factors(sum(A))
    facts.sort(reverse=True)
    for f in facts:
        B = sorted([a % f for a in A])
        d_m = []
        d_p = []
        for b in B:
            diff_minus = b
            diff_plus = f - diff_minus
            d_m.append(diff_minus)
            d_p.append(diff_plus)
        s_m = 0
        s_p = sum(d_p)
        for i in range(N):
            if s_m == s_p:
                break
            if s_m > s_p:
                print('okashii')
                break
            s_m += d_m[i]
            s_p -= d_p[i]
        if s_m <= K:
            print(f)
            return
            
    return



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

if __name__ == '__main__':
    main()

Solution (Python):
import fractions
import math
import sys

fastinput = sys.stdin.readline
gcd = fractions.gcd
N,K=map(int,fastinput().split())
A = [int(i) for i in fastinput().split()]
S = sum(A)
yakusu = []
for i in range(1,math.floor(math.sqrt(S))+1):
    if not S%i:
        yakusu.append(i)
        yakusu.append(S//i)

yakusu.sort(reverse = True)
for kouho in yakusu:
    amaris =[a%kouho for a in A]
    amaris.sort()
    amarisum= sum(amaris)
    y=amarisum // kouho
    if y==0:
        print(kouho)
        break
    else:
        yakuwa = 0
        for i in range(N-y):
            yakuwa += amaris[i]
        if yakuwa <= K:
            print(kouho)
            break

Solution (Python):
n,k = map(int, input().split())
a = list(map(int, input().split()))
t = sum(a)
r = set()
r.add(t)
for i in range(2,int(t**0.5)+2):
    if t%i == 0:
        r.add(i)
        r.add(t//i)
ans = 1
for i in r:
    f = [x%i for x in a]
    f.sort()
    if sum(f[:-sum(f)//i]) <= k:
        ans = max(ans,i)
print(ans)

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

def chk(x):
    D = []
    c = 0
    for a in A:
        y = a % x
        D.append(y)
    D.sort()
    s = sum(D)
    e = 0; r = N*x - s
    for d in D:
        e += d
        r -= x - d
        if e == r and e <= K:
            return 1
    return 0

ans = 1
S = sum(A)
for x in range(1, int(S**.5)+1):
    if S % x == 0:
        if chk(x):
            ans = max(ans, x)
        if chk(S // x):
            ans = max(ans, S // x)
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
S=sum(A)
DivS=set()
index=1
while(index*index<=S):
    if S%index==0:
        DivS.add(index)
        DivS.add(S//index)
    index+=1

ans=1
for d in DivS:
    B=[A[i] for i in range(N)]
    for i in range(N):
        if A[i]%d==0:
            continue
        
        
        tmp1=(A[i]//d)*d
        tmp2=tmp1+d
        if abs(tmp1-A[i])<=abs(tmp2-A[i]):
            B[i]=tmp1
        else:
            B[i]=tmp2
    nowsum=sum(B)
    
    if nowsum!=S:
        C=sorted(range(N),key=lambda i:abs(A[i]-B[i]),reverse=True)
        if nowsum>S:
            k=0
            need=(nowsum-S)//d
            for i in C:
                if B[i]>A[i]:
                    B[i]-=d
                    k+=1
                if k>=need:
                    break
        if nowsum<S:
            k=0
            need=(S-nowsum)//d
            for i in C:
                if B[i]<A[i]:
                    B[i]+=d
                    k+=1
                if k>=need:
                    break
    
    cost=sum([abs(A[i]-B[i]) for i in range(N)])
    if cost<=2*K:
        ans=max(ans,d)
print(ans)

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

def chk(x):
    D = []
    c = 0
    for a in A:
        y = a % x
        D.append(y)
    D.sort()
    s = sum(D)
    e = 0; r = N*x - s
    for d in D:
        e += d
        r -= x - d
        if e == r and e <= K:
            return 1
    return 0

ans = 1
S = sum(A)
for x in range(1, int(S**.5)+1):
    if S % x == 0:
        if chk(x):
            ans = max(ans, x)
        if chk(S // x):
            ans = max(ans, S // x)
print(ans)

Solution (Python):
def make_divisors(n):
    """自然数nの約数を列挙したリストを出力する
    計算量: O(sqrt(N))
    入出力例: 12 -> [1, 2, 3, 4, 6, 12]
    """
    divisors = []
    for k in range(1, int(n**0.5) + 1):
        if n % k == 0:
            divisors.append(k)
            if k != n // k:
                divisors.append(n // k)
    divisors = sorted(divisors, reverse = True)
    return divisors

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

sum_a = sum(a)
div = make_divisors(sum_a)

for num in div:
    cnt = 0
    li = [0] * n
    for i in range(n):
        li[i] = a[i] % num
    li = sorted(li)
    
    ruiseki = [0] * (n+1)
    for i in range(n):
        ruiseki[i+1] = ruiseki[i] + li[i]
    if ruiseki[-1] == 0:
        print(num)
        exit()
    for i in range(n)[::-1]:
        cnt += num - li[i]
        if ruiseki[i] == cnt:
            if cnt <= k:
                print(num)
                exit()

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def divisors(m: int):
    i = 1
    div = []
    while i * i <= m:
        if m % i == 0:
            div.append(i)
            div.append(m // i)
        i += 1

    return list(set(div))

n, k = li()
a = list(li())

ans = 1


divs = divisors(sum(a))
divs.sort(reverse=True)


for div in divs:
    if div == 1:
        break

    amodr = [ai % div for ai in a]
    amodr.sort(reverse=True)
    rsum = sum(amodr)
    rnum = rsum // div

    req = rsum - sum(amodr[:rnum])

    if req <= k:
        ans = div
        break

print(ans)

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

S = sum(A)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(S)

def chk(n):
    global K
    B = sorted([A[i]%n for i in range(N)])
    r = 0
    i, j = 0, N-1
    k = 0
    while i <= j:
        if r > 0:
            k += n-B[j]
            r -= n-B[j]
            j -= 1
        else:
            k += B[i]
            r += B[i]
            i += 1
    return 1 if k <= K*2 else 0

for d in D[::-1]:
    if chk(d):
        print(d)
        break

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
s = sum(A)
divisor = []
n = 1
while n*n <= s:
    q, m = divmod(s, n)
    if m==0:
        divisor.append(n)
        divisor.append(q)
    n += 1
if n*n==s:
    divisor.pop()
ans = 1
for d in divisor:
    M = []
    for a in A:
        M.append(a%d)
    n = sum(M) // d
    M.sort(reverse=True)
    a = n*d - sum(M[:n])
    if a <= K:
        ans = max(ans, d)
print(ans)

Solution (Python):
from itertools import accumulate


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return sorted(ret, reverse=True)


def solve(n, k, aaa):
    s = sum(aaa)
    div = divisors(s)
    for d in div:
        mods = [a % d for a in aaa]
        mods.sort()
        subs = [0] + list(accumulate(mods))
        adds = [0] + list(accumulate(d - p for p in reversed(mods)))
        adds.reverse()
        
        
        
        for m, a in zip(subs, adds):
            if m == a:
                if m <= k:
                    return d
                break
            if m > a:
                break


n, k = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, k, aaa))

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

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, k = na()
a = na()

q = sum(a)


ds = set()
x = 1
while x*x <= q:
    if q % x == 0:
        ds.add(x)
        ds.add(q//x)
    x += 1

ans = 0
for d in ds:
    costs = []
    for v in a:
        costs.append(v%d)

    costs.sort()
    cost = 0
    if costs[-1] > 0:
        sc = sum(costs)
        ps = 0
        for i in range(n):
            ps += costs[i]
            tps = d*(n-i-1) - (sc - ps)
            if ps == tps:
                cost = ps
                break

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

print(ans)