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 collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(A, n):
    L = [0] + sorted([a % n for a in A if a % n != 0])
    R = [n - a for a in L[1:]] + [0]
    for i in range(len(L) - 1):
        L[i + 1] += L[i]
        R[len(L) - i - 2] += R[len(L) - i - 1]

    res = 10 ** 20
    for l, r in zip(L, R):
        res = min(res, max(l, r))
    return res


def main():
    N, K = read_values()
    A = read_list()
    S = sum(A)
    
    res = 0
    for n in range(1, int(S ** 0.5) + 1):
        if S % n != 0:
            continue
        m = S // n
        if f(A, n) <=  K:
            res = max(res, n)
        if f(A, m) <=  K:
            res = max(res, m)
    print(res)
        

if __name__ == "__main__":
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    A = LI()

    s = sum(A)
    d = [s]
    for i in range(2,int(math.sqrt(s))+1):
        if s % i == 0:
            d.append(i)
            if s // i != i:
                d.append(s//i)

    ans = 1
    for x in d:

        B = []
        s = 0
        for y in A:
            c1 = x - y % x
            B.append((c1,y))
            s += c1

        B.sort(reverse=True)
        cnt = 0
        for y,_ in B[s//x:]:
            cnt += y
        if cnt <= K:
            ans = max(ans,x)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
s = sum(a)
def fs(n):
    s = set()
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            s.add(i)
            s.add(n//i)
    l = sorted(list(s))
    return l
l = fs(s)
def sub(v):
    val0 = [item%v for item in a if item%v!=0]
    val1 = [(v-item)%v for item in val0]
    val0.sort()
    val1.sort(reverse=True)

    i = 0
    j = len(val0)-1
    ans = 0
    while i<j:
        if val0[i]<val1[j]:
            val1[j] -= val0[i]
            ans += val0[i]
            i += 1
        else:
            val0[i] -= val1[j]
            ans += val1[j]
            j -= 1
    return ans
for v in reversed(l):
    if k>=sub(v):
        break
print(v)

Solution (Python):
"""
どんなに操作をおこなっても、全てのi,j(i<j)に関して、Ai,Ajの絶対値の差がsum(A)より大きくなることはない。
したがって、答えがsum(A)より大きくなることはない。
さらに言うなら、数値の状態がワイルドカードである0がベストなので負の値にする必要もない。

また、答えはsum(A)の約数になる。
答えをXとおくと、全ての数はXで割り切れる＝Xの倍数である。
Ai/X = Biとおくと、XBi = Ai　と表すことができる。。
X*sum(B) = sum(A)なので、答えXはsum(A)の約数であることがわかる。

解法：
基本方針としては、sum(A)の約数を列挙して、K回以内の操作で大きい順に実現可能かどうかを調べる。
実現可能かどうかは、各Aiを数が引かれる方と足される方に分けることで考えることができる。
"""
from itertools import accumulate
N,K = map(int,input().split())
A = list(map(int,input().split()))

sumA = sum(A)


yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)

for d in yakusu:
    X = [A[i]%d for i in range(N)]
    X.sort()
    Y = [d-x for x in X]
    Y.sort()
    X = list(accumulate(X))
    Y = list(accumulate(Y))
    Y = Y[::-1]
    for i in range(N-1):
        if X[i] == Y[i+1] and X[i]<=K:
            print(d)
            exit()
    if X[N-1] == 0:
        print(d)
        exit()

Solution (Python):
from collections import deque

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


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                                                                                     31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    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, reverse=True)


def is_ok(n):
    B_ = []
    for a in A:
        b = a % n
        B_.append(b)
    B_.sort()
    B = deque(B_)
    start = 0
    end = 0
    cnt = 0
    while B:
        start += B.popleft()
        while start > end:
            end += n - B.pop()
        end -= start
        cnt += start
        start = 0
        if cnt > K:
            return False
    return True






Can = divisors(AS)

for c in Can:
    if is_ok(c):
        print(c)
        exit()

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


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

divisors = list(make_divisors(sum(A)))
divisors.sort(reverse=True)

for divisor in divisors:
    M = [a % divisor for a in A]
    M.sort(reverse=True)
    
    if sum(M[sum(M) // divisor:]) <= K:
        print(divisor)
        exit()

Solution (Python):
from collections import deque
N,K=map(int,input().split())
L=list(map(int,input().split()))

def factorization(N):
    res=[]
    for i in range(2,int(N**(1/2))+2):
        if not N%i:
            r=0
            while not N%i:
                N//=i
                r+=1
            res.append((i,r))
    if N>1:
        res.append((N,1))
    return res

def factors(n):
    res=[1]
    for i,j in factorization(n):
        res+=[r*i**(b+1) for r in res for b in range(j)]
    return res

A=factors(sum(L))
A.sort()

def check(n):
    B=deque(sorted([a%n for a in L if a%n>0]))
    rp,rm=0,0
    while B:
        if rp<rm:
            rp+=B.popleft()
        else:
            rm+=n-B.pop()
    if rp!=rm:
        return False
    return rp<=K












for a in reversed(A):
    if check(a):
        break
print(a)

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

    divisors.sort()
    return divisors


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

x=sum(a)

lst=make_divisors(x)

lst.reverse()

for can in lst:
    aa=list(map(lambda x:x%can,a))
    aa.sort()

    cnt=0
    l=0
    r=0
    lll=0
    rrr=len(aa)-1
    while lll<=rrr:
        if l<r:
            l+=aa[lll]
            lll+=1
        
        else:
            r+=can-aa[rrr]
            rrr-=1
    
    if (l+r)//2<=k:
        print(can)
        exit()

Solution (Python):
"""
まず、答えは必ずAの総和以下になる。なぜなら、A同士の差の最大値がAの総和だからである。
移動回数が足りるのであれば、一つだけAの総和になるような項を作って、他を全部0にするのがよい。
ここからわかるのは、数を移動させ終わった後の各Aは全て0以上になるということである。

また答えはからなずAの総和の約数になる。
理由：
答えをXとすると、各AはbXと表すことができる。
したがって、Aの総和＝(bの総和*X)となる。
ゆえに、答えXはAの総和の約数である。

解法としては、Aの総和の約数を列挙して、大きい順に実現可能かどうかを試していく。
実現可能かどうかを試すには、各Aを総和の約数dで割ったときの余りをもとめて、小さい順にソートする。
そのうえで、左からL番目までを「数を与える側」、L+1番目以降を「数をもらう側」として余りが0になるように調整できないかを確かめる。
これは累積和を活用することですくない計算量で実行可能である。
最後に、移動した数がK以下かどうかを確認する。
"""
from itertools import accumulate
N,K = map(int,input().split())
A = list(map(int,input().split()))
sumA = sum(A)
 
yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)
for d in yakusu:
    
    rest = [a%d for a in A]
    rest.sort()
    
    rest = [a%d for a in A]
    rest.sort()
    Rrest = [d-r for r in rest]
    Rrest = Rrest[::-1]
    rest = [0]+list(accumulate(rest))
    Rrest = [0]+list(accumulate(Rrest))
    for i in range(N+1):
        if rest[i] == Rrest[N-i]:
            if rest[i] <= K:
                print(d)
                exit()
            break

Solution (Python):
"""
最大公約数を追い求める。

少なくとも、Aの合計値より答えが大きくなることはない。
なぜなら、どんなに頑張ってもA同士の差分はAの合計値以下になるからである。

答えの最大値はAの合計値。
マイナスを作る必要はない。
0を作る必要はある。

やっぱり、Aの合計値の約数のどれかが答えになりそうだな。証明はできないけど。
Aの合計値の約数を大きいものから順に、実現可能かどうかを検証していけばよい。

"""

from itertools import accumulate

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

yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)
for d in yakusu:
    
    rest = [a%d for a in A]
    rest.sort()
    Rrest = [d-r for r in rest]
    Rrest = Rrest[::-1]
    rest = [0]+list(accumulate(rest))
    Rrest = [0]+list(accumulate(Rrest))
    for i in range(N+1):
        if rest[i] == Rrest[N-i]:
            if rest[i] <= K:
                print(d)
                exit()
            break

Solution (Python):
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
s=sum(a)

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

ans=0
for cdd in candidates:
  f=sorted([x%cdd for x in a])
  
  ans=max(ans,cdd) if sum(f[:-sum(f)//cdd])<=k else ans   
    
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
s=sum(a)

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

ans=0
for cdd in candidates:
  div_cdd=[0]*n
  for i in range(n):
    div_cdd[i]=a[i]%cdd
  div_cdd=sorted(div_cdd)
  
  idx=n-sum(div_cdd)//cdd
  need=0
  for i in range(idx):
    need+=div_cdd[i]
  ans=max(ans,cdd) if need<=k else ans
    
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
s=sum(a)

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

ans=0
for cdd in candidates:
  div_cdd=[0]*n
  for i in range(n):
    div_cdd[i]=a[i]%cdd
  div_cdd=sorted(div_cdd)
  pstv,ngtv=0,-sum(div_cdd)
  
  if pstv==-ngtv:
    ans=max(ans,cdd)
    continue
  for i in range(n):
    pstv+=cdd-div_cdd[-1-i]
    ngtv+=div_cdd[-1-i]
    if pstv==-ngtv: break
  ans=max(ans,cdd) if pstv<=k else ans
    
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
s=sum(a)

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

ans=0
for cdd in candidates:
  div_cdd=[0]*n
  for i in range(n):
    div_cdd[i]=a[i]%cdd
  div_cdd=sorted(div_cdd)
  pstv,ngtv=0,-sum(div_cdd)
  
  if pstv==-ngtv:
    ans=max(ans,cdd)
    continue
  for i in range(n):
    pstv+=cdd-div_cdd[-1-i]
    ngtv+=div_cdd[-1-i]
    if pstv==-ngtv: break
  ans=max(ans,cdd) if pstv<=k else ans
    
print(ans)

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



def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


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



sum_A = sum(A)
div_list = make_divisors(sum_A)
ans = 1

for div in div_list:
    
    
    tmp = [a % div for a in A]
    tmp.sort()

    
    cumsum1 = [0]
    cumsum2 = [0]
    for i in tmp:
        cumsum1.append(cumsum1[-1] + i)
        if i != 0:
            cumsum2.append(cumsum2[-1] + (div - i))
        else:
            cumsum2.append(cumsum2[-1])

    for i in range(1, N):
        cnt_minus = cumsum1[i]
        cnt_plus = cumsum2[N] - cumsum2[i]
        
        
        if cnt_minus == cnt_plus and cnt_minus <= K:
            ans = div

print(ans)

Solution (Python):




def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



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

sum_A = sum(A)
div_list = make_divisors(sum_A)
ans = 1


for div in div_list:
    tmp = []
    for a in A:
        tmp.append(a % div)
    tmp.sort()
    cumsum1 = [0]
    cumsum2 = [0]
    for i in tmp:
        cumsum1.append(cumsum1[-1] + i)
        if i != 0:
            cumsum2.append(cumsum2[-1] + (div - i))
        else:
            cumsum2.append(cumsum2[-1])
    for i in range(1, N):
        if cumsum1[i] <= K and cumsum2[N] - cumsum2[i] <= K:
            ans = div

print(ans)

Solution (Python):


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



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

sum_A = sum(A)
div_list = make_divisors(sum_A)
ans = 1


for div in div_list:
    tmp = []
    for a in A:
        tmp.append(a % div)
    tmp.sort()
    cumsum1 = [0]
    cumsum2 = [0]
    for i in tmp:
        cumsum1.append(cumsum1[-1] + i)
        if i != 0:
            cumsum2.append(cumsum2[-1] + (div - i))
        else:
            cumsum2.append(cumsum2[-1])
    for i in range(1, N):
        if cumsum1[i] <= K and cumsum2[N] - cumsum2[i] <= K:
            ans = div

print(ans)

Solution (Python):
from itertools import accumulate
from math import floor, sqrt
N, K = map(int,input().split())
A = list(map(int,input().split()))
sm = sum(A)
divs = set()
for i in range(1, floor(sqrt(sm))+1):
    if sm % i == 0:
        divs.add(i)
        divs.add(sm // i)
ans = 1
for d in divs:
    ls = sorted(map(lambda x: x%d, A))
    acc = [0]+list(accumulate(ls, lambda x,y:x+y))
    for i in range(1, N):
        minus = acc[i]-acc[0]
        plus = d*(N-i) - (acc[-1]-acc[i])
        if plus == minus and plus <= K:
            ans = max(ans, d)
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


def main():
    N, K, *A = map(int, read().split())

    total = sum(A)
    div = divisors(total)

    for d in reversed(div):
        vec = [a % d for a in A]
        vec.sort()

        M = len(vec)
        csum_sub = [0] * (M + 1)
        csum_add = [0] * (M + 1)
        for i in range(M):
            csum_sub[i + 1] = csum_sub[i] + vec[i]
            csum_add[i + 1] = csum_add[i] + d - vec[i]

        for i in range(M + 1):
            if csum_sub[i] <= K and csum_sub[i] == csum_add[M] - csum_add[i]:
                print(d)
                return

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


def main():
    N, K, *A = map(int, read().split())

    total = sum(A)
    div = divisors(total)

    for d in reversed(div):
        vec = [a % d for a in A if a % d]
        if not vec:
            print(d)
            return
        vec.sort()
        M = len(vec)
        csum_sub = [0] * (M + 1)
        csum_add = [0] * (M + 1)
        for i in range(M):
            csum_sub[i + 1] = csum_sub[i] + vec[i]
            csum_add[i + 1] = csum_add[i] + d - vec[i]

        for i in range(1, M):
            if csum_sub[i] <= K and csum_sub[i] == csum_add[M] - csum_add[i]:
                print(d)
                return

    return


if __name__ == '__main__':
    main()

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

x = sum(a)
search = []
i = 1
while i ** 2 <= x:
    if x % i == 0:
        heapq.heappush(search, -i)
        heapq.heappush(search, -x//i)
    i += 1

while search:
    ans = -heapq.heappop(search)
    u = [a[i] % ans for i in range(n)]
    u.sort()

    plus = [0]
    minus = [0]
    for i in range(n):
        plus.append(plus[-1] + ans - u[i])
        minus.append(minus[-1] + u[i])

    for i in reversed(range(n+1)):
        
        m = minus[i]
        p = plus[-1] - plus[i]
        if m == p and m <= k:
            print(ans)
            exit()

Solution (Python):
import math

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

sumA = sum(A)
factors = []

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

div =  make_divisors(sumA)
ans = 1
for div_ in div:
    A_ = sorted([a % div_ for a in A])[::-1]
    if sum(A_[sum(A_) // div_:]) <= K:
        ans = div_
print(ans)

Solution (Python):
def yakusu(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
N,K=map(int,input().split())
L=list(map(int,input().split()))
a=sum(L)
R=yakusu(a)[::-1]
for i in range(len(R)):
  add=0
  minus=0
  s=R[i]
  A=list()
  B=list()
  for j in range(N):
    k=L[j]
    a=k%s
    b=s-a
    if a>b:
      add+=b
      B.append(b)
    elif a<b:
      minus+=a
      A.append(a)
    else:
      add+=a
      B.append(a)
  
  A=sorted(A)
  B=sorted(B)
  if minus==add:
    d=minus
    if d<=K:
      print(s)
      exit()
  elif minus>add:
    q=(minus-add)//s
    d=sum(A[:len(A)-q])
    if d<=K:
      print(s)
      exit()
  else:
    q=(add-minus)//s
    d=sum(B[:len(B)-q])
    if d<=K:
      print(s)
      exit()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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


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

    div = make_divisors(sum(A))
    res = 1
    for x in div:
        B = sorted([a % x for a in A])
        M, P = [0], [0]
        for i in range(n):
            M.append(M[-1] + B[i])
            P.append(P[-1] + x - B[i])
        M.pop(0)
        P.pop(0)
        for i in range(n - 1):
            m = M[i]
            p = P[n - 1] - P[i]
            if m <= k and p <= k and m % x == p % x:
                res = max(res, x)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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


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

    div = make_divisors(sum(A))
    res = 1
    for x in div:
        B = sorted([a % x for a in A])
        M, P = [0], [0]
        for i in range(n):
            M.append(M[-1] + B[i])
            P.append(P[-1] + x - B[i])
        M.pop(0)
        P.pop(0)
        for i in range(n - 1):
            m = M[i]
            p = P[n - 1] - P[i]
            if m <= k and p <= k and m % x == p % x:
                res = max(res, x)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def divisor(n):
    d = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            d.append(i)
            if i != n//i:
                d.append(n//i)
    
    return d

n,k = ma()
A = lma()
s = sum(A)
ds = divisor(s);ds.sort(reverse=True)
for d in ds:
    ls = []
    cost=0
    for a in A:
        p,r = divmod(a,d)
        ls.append(r)
    ls.sort(reverse=True)
    s0 = sum(ls)
    cost=s0
    
    for r in ls:
        if s0==0:
            break
        s0 -=d
        cost-=r
    if cost<=k:
        print(d)
        exit()

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def Enumeration(x):
    low = []
    high = []
    for i in range(1,x):
        if i**2 >= x:
            if i**2 == x:
                low.append(i)
            break
        if x%i == 0:
            low.append(i)
            high.append(x//i)
    return high+low[::-1]  


def main():
    n,k = map(int,ipt().split())



    a = [int(i) for i in ipt().split()]
    sm = sum(a)
    ys = Enumeration(sm)

    for i in ys:
        nm = 0
        vs = [j%i for j in a]
        vs.sort()
        l = 0
        r = n-1
        rs = 0

        while l <= r:
            if rs == 0:
                rs = vs[l]
                nm += rs
                l += 1
            if l > r:
                break
            if rs+vs[r] >= i:
                rs = rs-(i-vs[r])
                r -= 1
            else:
                vs[r] += rs
                rs = 0

        if nm <= k and rs == 0:
            print(i)
            exit()


    return None

if __name__ == '__main__':
    main()

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


def calc_min_ops(r, d):
    i, j = 0, len(r)
    while i < j and r[i] == 0:
        i += 1
    i -= 1
    a, b = 0, 0
    while j-i != 1:
        if a <= b:
            i += 1
            a += r[i]
        else:
            j -= 1
            b += d - r[j]
    return a


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

c = sum(A)
divisors = make_divisor_list(c)
divisors.sort(reverse=True)
r = [None] * N

for d in divisors:
    for i in range(N):
        r[i] = A[i] % d
    r.sort()
    if calc_min_ops(r, d) <= K:
        print(d)
        break

Solution (Python):
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

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

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        if d == 1:
            print(d)
            return
        diff_n = [a % d for a in A if a % d != 0]
        diff_n.sort()
        diff_p = [d - dn for dn in diff_n]
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        M = len(S_n) - 1
        if any(max(S_n[i], S_p[M] - S_p[i]) <= K for i in range(1, M)):
            print(d)
            return


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

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

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        if d == 1:
            print(d)
            return
        diff_n = [a % d for a in A if a % d != 0]
        diff_n.sort()
        diff_p = [d - dn for dn in diff_n]
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        M = len(S_n) - 1
        if min(S_n[i] for i in range(1, M)
               if (S_n[i] - (S_p[M] - S_p[i])) == 0) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

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

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        if d == 1:
            print(d)
            return
        diff_n = []
        for a in A:
            if a % d != 0:
                diff_n.append(a % d)
        diff_n.sort()
        diff_p = [d - dn for dn in diff_n]
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        M = len(S_n) - 1
        if min(S_n[i] for i in range(1, M)
               if (S_n[i] - (S_p[M] - S_p[i])) == 0) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

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

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        if d == 1:
            print(d)
            return
        diff_n = []
        for a in A:
            if a % d != 0:
                diff_n.append(a % d)
        diff_n.sort()
        diff_p = []
        for dn in diff_n:
            diff_p.append(d - dn)
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        M = len(S_n) - 1
        if min(S_n[i] for i in range(1, M)
               if (S_n[i] - (S_p[M] - S_p[i])) == 0) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()