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



Sample input:
2 3
8 20


Sample output:
7

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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

# aの和を素因数分解
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()
        # print(d)
        # print(mods)
        # print(adds)
        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))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

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

q = sum(a)

# min(a%d, d-a%d)
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)

Submission status: Runtime Error

Solution code:
"""
どんなに操作をおこなっても、全ての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)

#sumAの約数を列挙する。
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 rest]
    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()

Submission status: Runtime Error

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

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

解法としては、Aの総和の約数を列挙して、大きい順に実現可能かどうかを試していく。
実現可能かどうかを試すには、各Aを総和の約数dで割ったときの余りをもとめて、小さい順にソートする。
そのうえで、左からL番目までを「数を与える側」、L+1番目以降を「数をもらう側」として余りが0になるように調整できないかを確かめる。
これは累積和を活用することですくない計算量で実行可能である。
最後に、移動した数がK以下かどうかを確認する。
"""

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

Submission status: Runtime Error

Solution code:
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:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

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

    for d in divs:
        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()

Submission status: Runtime Error

Solution code:
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:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

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

    for d in divs:
        diff_n = []
        for a in A:
            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))
        if min(S_n[i] for i in range(1, N)
               if (S_n[i] - (S_p[N] - S_p[i])) == 0) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

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

    for d in divs:
        diff = []
        for a in A:
            diff.append(a % d)
        diff.sort()
        S = list(accumulate([0] + diff))
        if min(S[i] for i in range(1, N)
               if S[i] == (d * (N-i) - (S[N] - S[i]))) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

s=sum(A)
import math
def yakusu(n):
  ans_local=set()
  for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
      ans_local = ans_local | set([i,n//i]) #setなので平方数でもOK
  return list(ans_local)  #必要に応じてsort

yaku=sorted(yakusu(s), reverse=1)
#print(yaku)
for mod in yaku:
    B=[i%mod for i in A if i%mod!=0]
    B.sort()
    r=[B[0]]*len(B)
    for i in range(len(B)-1):
        r[i+1]= r[i]+B[i+1]
    now=float("INF")
    for i in range(1,len(B)): #切り方
        if r[i-1] ==  mod*(len(B)-i)-(r[-1]-r[i-1]) and r[i-1]<=k:
            print(mod);exit()

Submission status: Runtime Error

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

s=sum(A)
import math
def yakusu(n):
  ans_local=set()
  for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
      ans_local = ans_local | set([i,n//i]) #setなので平方数でもOK
  return list(ans_local)  #必要に応じてsort

yaku=sorted(yakusu(s), reverse=1)
#print(yaku)
for mod in yaku:
    B=[i%mod for i in A if i%mod!=0]
    B.sort()
    r=[B[0]]*len(B)
    for i in range(len(B)-1):
        r[i+1]= r[i]+B[i+1]
    now=float("INF")
    for i in range(1,len(B)):
        now= min(max(r[i-1], mod*(len(B)-i)-(r[-1]-r[i-1])),now)
    if now<=k:
        print(mod);exit()

Submission status: Runtime Error

Solution code:
import numpy as np

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

asum = sum(a)
adiv = make_divisors(asum)
adiv.reverse()

a = np.array(a)
flg = False
for i in adiv:
    a_ = np.sort(a % i)
    # print(i, a_)
    msum = a_.sum()
    msum_ = 0
    for j in range(-1, -n-1, -1):
        msum -= a_[j]
        msum_ += i - a_[j]
        if msum > k:
            break
        if msum < msum_:
            break
        if msum == msum_ :
            ans = i
            flg = True
            break
    if flg:
        break

print(ans)

Submission status: Runtime Error

Solution code:
import sympy

def resolve():
    lines = sys.stdin.readlines()
    n, k = tuple(map(int, lines[0].split(' ')))
    a = list(map(int, lines[1].split(' ')))
    divs = sympy.divisors(sum(a))
    divs = list(reversed(divs))

    for div in divs:
        a_mod = list(map(lambda x: x % div, a))
        sum_mod = sum(a_mod)
        if k >= sum_mod//2:
            print(div)
            break
resolve()

Submission status: Runtime Error

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

    #inf = 10**17
    #mod = 10**9 + 7

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2
        # 約数のリストを返す

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

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

Submission status: Runtime Error

Solution code:
from copy import copy, deepcopy
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    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:  # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)

        divisors.sort(reverse=True)  # ソートしたけりゃして
        return divisors

    M = make_divisors(sum(A))

    def main():
        for i in M:
            AA = A.copy()
            age = 0
            delete = 0
            for j in range(N):
                AA[j] = AA[j] % i
                if AA[j] == 0:
                    delete += 1
                    age -= i
                age += i-AA[j]
            AA.sort()

            times = 10**9
            sage = 0
            for j in range(delete, N-1):
                sage += AA[j]
                age -= i-AA[j]
                if sage % i == age % i:
                    times = min(max(sage, age), times)
            if times <= K:
                return i
    print(main())

resolve()

Submission status: Runtime Error

Solution code:
from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
import unittest
from io import StringIO
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    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:  # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)

        divisors.sort(reverse=True)  # ソートしたけりゃして
        return divisors

    M = make_divisors(sum(A))

    def main():
        for i in M:
            AA = A.copy()
            age = 0
            delete = 0
            for j in range(N):
                AA[j] = AA[j] % i
                if AA[j] == 0:
                    delete += 1
                    age -= i
                age += i-AA[j]
            AA.sort()

            times = 10**9
            sage = 0
            for j in range(delete, N-1):
                sage += AA[j]
                age -= i-AA[j]
                if sage % i == age % i:
                    times = min(max(sage, age), times)
            if times <= K:
                return i
    print(main())

resolve()

Submission status: Runtime Error

Solution code:
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
import unittest
from io import StringIO
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    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:  # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)

        divisors.sort(reverse=True)  # ソートしたけりゃして
        return divisors

    M = make_divisors(sum(A))

    def main():
        for i in M:
            AA = A.copy()
            age = 0
            delete = 0
            for j in range(N):
                AA[j] = AA[j] % i
                if AA[j] == 0:
                    delete += 1
                    age -= i
                age += i-AA[j]
            AA.sort()

            times = 10**9
            sage = 0
            for j in range(delete, N-1):
                sage += AA[j]
                age -= i-AA[j]
                if sage % i == age % i:
                    times = min(max(sage, age), times)
            if times <= K:
                return i
    print(main())

resolve()

Submission status: Runtime Error

Solution code:
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    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:  # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)

        divisors.sort(reverse=True)  # ソートしたけりゃして
        return divisors

    M = make_divisors(sum(A))

    def main():
        for i in M:
            AA = A.copy()
            age = 0
            delete = 0
            for j in range(N):
                AA[j] = AA[j] % i
                if AA[j] == 0:
                    delete += 1
                    age -= i
                age += i-AA[j]
            AA.sort()

            times = 10**9
            sage = 0
            for j in range(delete, N-1):
                sage += AA[j]
                age -= i-AA[j]
                if sage % i == age % i:
                    times = min(max(sage, age), times)
            if times <= K:
                return i
    print(main())

resolve()

Submission status: Runtime Error

Solution code:
INF = float("inf")
n, k = map(int, input().split())
a = list(map(int, input().split()))

def get_divisors(num):
    f_divs, l_divs = [], []
    for i in range(1, int(num**0.5)+1):
        if not num % i:
            f_divs.append(i)
            if i != num // i:
                l_divs.append(num // i)
    return f_divs + l_divs[::-1]

s = sum(a)
divs = get_divisors(s)
ans = 1

def evl(d):
    if d == 1: return True
    m = d*n*2
    rem = [x % d for x in a]
    dp = [[INF] * (m+d*2+10) for _ in range(n+1)]
    mid = m // 2
    dp[0][mid] = 0
    for i in range(n):
        for j in range(m):
            if rem[i] == 0:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j])
                continue
            dp[i+1][j-rem[i]] = min(dp[i+1][j-rem[i]], dp[i][j]+rem[i])
            dp[i+1][j+d-rem[i]] = min(dp[i+1][j+d-rem[i]], dp[i][j]+(d-rem[i]))
    return dp[n][mid] // 2 <= k

l, r = -1, len(divs)

while r-l > 1:
    x = (r+l) // 2
    if evl(divs[x]): l = x
    else: r = x

print(divs[l])

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
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

pr = make_divisors(sum(a))
pr = sorted(list(set(pr)), reverse = True)
def sol(p):
    mo = []
    pl = []
    for i in a:
        if i%p != 0:
            mo += [i%p]
            pl += [p-i%p]
    mo.sort(); pl.sort()
    m = 0; c = sum(pl)
    ln = len(mo)
    for i in range(ln):
        m += mo[i]
        c -= pl[ln-i-1]
        if max(m,c) <= k and m == c:
            return True
    return False
for p in pr:
    if sol(p):
        res = p
        break
print(res)