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: Wrong Answer

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]

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

def evl(d):
    rem = [x % d for x in a]
    rem.sort()
    s = sum(rem)
    c = 0
    for i, x in enumerate(rem):
        c += x
        if c == d*(n-i-1) - (s-c):
            return c <= k
    return False

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: Wrong Answer

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
divs = make_divs(S)
ans = 0

for d in divs:
    B = [Ai%d for Ai in A]
    B.sort()
    l, r = 0, N-1
    cnt = 0
    
    while l!=r:
        t = min(B[l], d-B[r])
        B[l] -= t
        B[r] += t
        cnt += t
        
        if B[l]==0:
            l += 1
        else:
            r -= 1
    
    if cnt<K:
        ans = max(ans, d)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def getDivisor(n):
  divisor = []
  tmp = n
  for i in range(2, int(n**0.5)+1):
    cnt = 1
    d = [1,]
    while tmp%i == 0:
      d.append(i**cnt)
      tmp //= i
      cnt += 1
    if cnt > 1:
      divisor.append(d)
  if tmp != 1:
    divisor.append([1,tmp])
  if divisor == []:
    divisor.append([1,n])
  return divisor

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

a = np.array(a)
sum_a = a.sum()
divisor = np.array(getDivisor(sum_a))
dmat = np.matrix(1)
for d in divisor:
  d = np.matrix(d)
  mat = []
  for dm in dmat:
    mat.append(dm.T * d)
  dmat = np.concatenate(mat)
num_d = len(divisor) - 1
divisor = np.array(np.array(dmat.flatten())[0].tolist() + [n])
divisor.sort()

for d in divisor[::-1]:
  tmp = a % d
  idx = tmp.sum() // d
  tmp.sort()
  num_op = tmp[:-idx].sum()
  if num_op <= k:
    break
print(d)

Submission status: Wrong Answer

Solution code:
import numpy as np

def getDivisor(n):
  divisor = [1,]
  tmp = n
  for i in range(2, int(n**0.5)+1):
    while tmp%i == 0:
      divisor.append(i)
      tmp //= i
  if tmp != 1:
    divisor.append(tmp)
  if divisor == [1,]:
    divisor.append(n)
  return divisor

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

a = np.array(a)
sum_a = a.sum()
divisor = np.array(getDivisor(sum_a))
num_d = len(divisor) - 1
for b in range(2**num_d-1, -1, -1):
  bit = [0] * len(divisor)
  for i in range(1, len(divisor)):
    bit[i] = b%2
    b //= 2
  bit[0] = 1
  ans = np.prod(divisor[np.array(bit, dtype=bool)])
  tmp = a % ans
  idx = tmp.sum() // ans
  tmp.sort()
  num_op = tmp[:-idx].sum()
  if num_op <= k:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def getDivisor(n):
  divisor = [1,]
  tmp = n
  for i in range(2, int(n**0.5)+1):
    while tmp%i == 0:
      divisor.append(i)
      tmp //= i
  if tmp != 1:
    divisor.append(tmp)
  if divisor == [1,]:
    divisor.append(n)
  return divisor

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

a = np.array(a)
sum_a = a.sum()
divisor = getDivisor(sum_a)

ans = sum_a
for d in divisor:
  ans = ans // d
  tmp = a % ans
  idx = tmp.sum() // ans
  tmp.sort()
  num_op = tmp[:-idx].sum()
  if num_op <= k:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def getDivisor(n):
  divisor = [1,]
  tmp = n
  for i in range(2, int(n**0.5)+1):
    while tmp%i == 0:
      divisor.append(i)
      tmp //= i
  if tmp != 1:
    divisor.append(tmp)
  if divisor == [1,]:
    divisor.append(n)
  return divisor

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

a = np.array(a)
sum_a = a.sum()
divisor = getDivisor(sum_a)

ans = sum_a
for d in divisor:
  ans = ans // d
  tmp = a % ans
  num_op = tmp.sum() - tmp.max()
  if num_op <= k:
    break
print(ans)

Submission status: Wrong Answer

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):
    cnt = 0
    for i in a:
        cnt += i%p
    if cnt//2 <= k:
        return True
    return False
for p in pr:
    if sol(p):
        res = p
        break
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
N, K = map(int, input().split())
*A, = map(int, input().split())
S = sum(A)


div_small = []
div_large = []
for p in range(1, int(S**0.5)+1):
    if S % p == 0:
        div_small.append(p)
        if S // p != p:
            div_large.append(S//p)
div_large += div_small[::-1]

for d in div_large:
    R = [a%d for a in A]
    SR = sum(R)
    acc = accumulate(R)

    for r in acc:
        if r == SR//2 and r <= K:
            print(d)
            sys.exit()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
s = sum(A)
def md(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
P = md(s)
def test(x):
  L = sorted([a%x for a in A])
  M = sum(L)
  c = M//x
  for _ in range(c):
    M -= L.pop()
  return M <= k

Submission status: Wrong Answer

Solution code:
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()))
d = sorted(make_divisors(sum(a)),reverse = True)
for i in d:
  check = 0
  for j in a:
    check += min(j%i,i-j%i)
  if check//2 <=  k & (check//2-k)%2 == 0:
    print(i)

Submission status: Wrong Answer

Solution code:
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()))
d = sorted(make_divisors(sum(a)),reverse = True)
for i in d:
  check = 0
  for j in a:
    check += min(j%i,i-j%i)
    if check <= k & (check-k)%2 == 0:
      print(i)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    for i in reversed(range(1, 1 + 10 ** 6)):
        if i % 2 == 1:
            plus, minus = 0, 0
            for a in A:
                m = a % i
                if m > i // 2: plus += (i - m)
                elif m > 0: minus += m
            if abs(plus - minus) % i == 0:
                if max(plus, minus) <= K:
                    print(i)
                    break
        else:
            plus, minus, both = 0, 0, 0
            for a in A:
                m = a % i
                if m > i // 2: plus += (i - m)
                elif 0 < m < i // 2: minus += m
                elif m == i // 2: both += 1
            if abs(plus - minus) % i == 0:
                if both % 2 == 0 and max(plus, minus) + (both // 2) * (i // 2) <= K:
                    print(i)
                    break
            elif abs(plus - minus) % i == i // 2 and max(plus, minus) + (both // 2) * (i // 2) + (i // 2) <= K:
                if both % 2 == 1:
                    print(i)
                    break
    else: print(1)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    for i in reversed(range(1, 1 + 10 ** 6)):
        if i % 2 == 1:
            plus, minus = 0, 0
            for a in A:
                m = a % i
                if m > i // 2: plus += (i - m)
                elif m > 0: minus += m
            if abs(plus - minus) % i == 0:
                if plus + minus + abs(plus - minus) // i <= K:
                    print(i)
                    break
        else:
            plus, minus, both = 0, 0, 0
            for a in A:
                m = a % i
                if m > i // 2: plus += (i - m)
                elif 0 < m < i // 2: minus += m
                elif m == i // 2: both += 1
            if abs(plus - minus) % i == 0:
                if both % 2 == 0 and plus + minus + abs(plus - minus) // i + (both // 2) * (i // 2) <= K:
                    print(i)
                    break
            elif abs(plus - minus) % i == i // 2 and plus + minus + abs(plus - minus) // i + (both // 2) * (i // 2) + (i // 2) <= K:
                if both % 2 == 1:
                    print(i)
                    break
    else: print(1)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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:
    operations = 0
    max_op = 0
    for item in a:
        operation = min(item % d, d - item % d)
        operations += operation
        max_op = max(max_op, operation)
    if operations - max_op <= k:
        ans = max(ans, d)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

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):
    # 全てのAiをK回以下の操作で0(mod 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 = 0
ng = len(divisor)

while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if judge(divisor[mid]):
        ok = mid
    else:
        ng = mid
    

print(divisor[ok])

Submission status: Wrong Answer

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

div = []
for i in range(1, int(Asum ** 0.5 + 0.5) + 1):
    if Asum % i == 0:
        div.append(i)
        if i * i != Asum:
            div.append(Asum // i)

div.sort()
ans = 0

for d in div:
    tmp = 0
    for a in A:
        tmp += min(a % d, d - a % d)
    if tmp <= K:
        ans = max(ans, d)

print(ans)

Submission status: Wrong Answer

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

div = []
for i in range(1, int(Asum ** 0.5 + 0.5) + 1):
    if Asum % i == 0:
        div.append(i)
        if i * i != Asum:
            div.append(Asum // i)

div.sort()
ans = 0

for d in div:
    tmp = sum(a % d for a in A) // 2
    if tmp <= K:
        ans = max(ans, d)

print(ans)

Submission status: Wrong Answer

Solution code:
# E
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()))
# 候補はsum(a)の正約数。
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)
        break

Submission status: Wrong Answer

Solution code:
import heapq as h

def partions(M):#Mの約数列 O(n^(0.5+e))
    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)]
    test=0
    h.heapify(X)
    for j in range(0,N-1):
        s=h.heappop(X)
        X=[candidate[i]-X[j] for j in range(0,len(X))]
        t=h.heappop(X)
        X=[candidate[i]-X[j] for j in range(0,len(X))]
        if t>s:
            test+=s
            h.heappush(X,(N-(t-s))%candidate[i])
        else:
            test+=t
            h.heappush(X,s-t)


    if K>=test:
        ans=candidate[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
lists=list(map(int,input().split()))
K=sum(lists)
#prime_factorization関数
#ある数Nの素因数分解をdicに保管して返す。
#ただし、素因数分解する数Mに応じて、Mの値は変わってしまうので注意が必要である
n=10**6
#primeに素数を保管する下準備
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
MAX=0

for i in range(1,10**4+1):
    c=0
    if K%i==0:
        c=K//i
        d=i
        p=0
        q=0
        P=0
        Q=0
        for j in range(len(lists)):
            p+=min(lists[j]//c,c-lists[j]//c)
            P=max(min(lists[j]//c,c-lists[j]//c),P)
            q+=min(lists[j]//d,d-lists[j]//d)
            Q=max(min(lists[j]//c,c-lists[j]//c),Q)
        if p-P<=k:
            MAX=max(MAX,c)
        if q-Q<=k:
            MAX=max(MAX,d)
print(MAX)

Submission status: Wrong Answer

Solution code:
def check(b):
    res = K
    A1 = [0 for _ in range(N)]
    k = a//b
    for i in range(N-1,-1,-1):
        s = min(A[i]//b+1,k)
        while b*s-A[i]>res:
            s -= 1
        A1[i] = b*s
        res -= max(b*s-A[i],0)
        k -= s
    if sum(A1)==a:
        return 1
    else:
        return 0
N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))
a = sum(A)
B = []
for i in range(1,10**5):
    if a%i==0:
        B.append(i)
        B.append(a//i)
B = sorted(B)
n = len(B)
high = n
low = 0
while high-low>1:
    mid = (high+low)//2
    b = B[mid]
    if check(b):
        low = mid
    else:
        high = mid
print(B[low])

Submission status: Wrong Answer

Solution code:
def check(b):
    res = K
    A1 = [0 for _ in range(N)]
    k = a//b
    for i in range(N-1,-1,-1):
        s = k
        while b*s-A[i]>res:
            s -= 1
        if s>0:
            A1[i] = b*s
            res -= max(b*s-A[i],0)
            k -= s
        else:
            break
    if sum(A1)==a:
        return 1
    else:
        return 0
N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))
a = sum(A)
B = []
for i in range(1,10**5):
    if a%i==0:
        B.append(i)
        B.append(a//i)
B = sorted(B)
n = len(B)
high = n
low = 0
while high-low>1:
    mid = (high+low)//2
    b = B[mid]
    if check(b):
        low = mid
    else:
        high = mid
print(B[low])

Submission status: Wrong Answer

Solution code:
def check(b):
    res = K
    A1 = [0 for _ in range(N)]
    k = a//b
    for i in range(N-1,-1,-1):
        s = min(A[i]//b+1,k)
        while b*s-A[i]>res:
            s -= 1
        if s>0:
            A1[i] = b*s
            res -= max(b*s-A[i],0)
            k -= s
        else:
            break
    if sum(A1)==a:
        return 1
    else:
        return 0
N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))
a = sum(A)
B = []
for i in range(1,10**5):
    if a%i==0:
        B.append(i)
        B.append(a//i)
B = sorted(B)
n = len(B)
high = n
low = 0
while high-low>1:
    mid = (high+low)//2
    b = B[mid]
    if check(b):
        low = mid
    else:
        high = mid
print(B[low])

Submission status: Wrong Answer

Solution code:
def check(b):
    res = K
    A1 = [0 for _ in range(N)]
    k = a//b
    for i in range(N-1,-1,-1):
        s = A[i]//b+1
        while k>0 and b*s-A[i]>res:
            s -= 1
        if s>0 and k>=s:
            A1[i] = b*s
            res -= max(b*s-A[i],0)
            k -= s
        else:
            break
    if sum(A1)==a:
        return 1
    else:
        return 0
N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))
a = sum(A)
B = []
for i in range(1,10**5):
    if a%i==0:
        B.append(i)
        B.append(a//i)
B = sorted(B)
n = len(B)
high = n
low = 0
while high-low>1:
    mid = (high+low)//2
    b = B[mid]
    if check(b):
        low = mid
    else:
        high = mid
print(B[low])

Submission status: Wrong Answer

Solution code:
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()
# Aiが1以上のため、answerはsumの約数

def make_divisors(n): # 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
    for i in range(N):
        result = c[:i].sum() + d[i:].sum()
        result //= 2
        if result <= K:
            print(x)
            exit()

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

def divisors(n):
    ds = []
    for d in range(1, n + 1):
        if d * d > n:
            break
        if n % d == 0:
            ds.append(d)
            if d * d < n:
                ds.append(n // d)
    return ds

sum_A = sum(A)
ds = sorted(divisors(sum_A), reverse=True)

for d in ds:
    pos = []
    neg = []
    n_both = 0
    cost = 0
    for a in A:
        r = a % d
        if r < d - r:
            neg.append(r)
        elif r > d - r:
            pos.append(d - r)
        else:
            n_both += 1
    if n_both >= 2:
        cost += (n_both // 2) * (d // 2)
        n_both %= 2
    sum_pos = sum(pos)
    sum_neg = sum(neg)
    if sum_pos < sum_neg:
        cost += sum_pos
        sum_neg -= sum_pos
        if n_both:
            cost += sum_neg
        else:
            cost += sum_neg - max(neg)
    elif sum_pos > sum_neg:
        cost += sum_neg
        sum_pos -= sum_neg
        if n_both:
            cost += sum_pos
        else:
            cost += sum_pos - max(pos)
    else:
        assert n_both == 0
        cost += sum_pos
    if cost <= K:
        print(d)
        break

Submission status: Wrong Answer

Solution code:
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.pop()
        B[m] -= p-B[-1]
        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

Submission status: Wrong Answer

Solution code:
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]
        B[-1] %= p
        cnt += B[m]
        B[m] = 0
        m += 1
      elif B[m]>p-B[-1]:
        B.pop()
        cnt += p-B[-1]
        B[m] -= p-B[-1]
        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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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

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

div = divisors(sum(A))

for d in div:
  cnt = 0
  for a in A:
    if a % d != 0:
      cnt += d - a % d
  if cnt // 2 <= K:
    print(d)
    exit()

Submission status: Wrong Answer

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


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


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

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

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

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

print(ans)

Submission status: Wrong Answer

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


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


ans = 0
for X in ans_candidates:
    need_minus = sorted([a - (X * (a // X)) for a in A], reverse=True)
    need_plus = [X - nm for nm in need_minus]

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

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


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

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

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

    return r


print(main())

Submission status: Wrong Answer

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

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

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


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

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

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

    return r


print(main())