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:
[N,K] = list(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:
                divisors.append(n//i)
    return divisors

SUMA = sum(A)
yaku = make_divisors(SUMA)
yaku.sort(reverse=True)

for yakusu in yaku:
    Adai = 0
    Asho = 0
    for i in range(N):
        if A[i] >yakusu :
            Adai += A[i]//yakusu
        elif A[i] < yakusu:
            Asho += min(yakusu-A[i],A[i])
    if (Adai <= K) and (Asho <= K):
        print(yakusu)
        break

Submission status: Wrong Answer

Solution code:
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

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

x = sum(A)

tL = prime(x)
L = [1]
for k, v in tL.items():
  t = len(L)
  n = k
  for i in range(v):
    for j in range(t):
      L.append(L[j] * n)
    n *= k

L.sort(reverse = True)

for i in L:
  M = [j % i for j in A]
  M.sort()
  f = True
  c = 0
  for k in M:
    if f:
      if c + k <= K:
        c += k
      else:
        f = False
        c = 0
    else:
      if c + (i - k) <= K:
        c += k
      else:
        break
  else:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


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 solve(N: int, K: int, A: "List[int]"):
    tot = sum(A)
    divs = make_divisors(sum(A))

    m = 1
    for cand in divs[1:]:
        modA = [a % cand for a in A]
        counter = 0
        for ma in modA:
            if ma <= cand//2:
                counter += ma
            else:
                counter += cand-ma
        # print("counter", counter)
        if counter <= 2*K:
            m = cand
    print(m)

    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))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A_sum = sum(A)
A_sum_div = []
div = 1
while div ** 2 <= A_sum:
    if A_sum % div == 0:
        A_sum_div.append(div)
        if div ** 2 != A_sum:
            A_sum_div.append(A_sum // div)
    div += 1
A_sum_div.sort()

left = 0
right = len(A_sum_div) - 1
i = (left + right + 1) // 2
while True:
    M = A_sum_div[i]
    A_mod = [0] * N
    for j in range(N):
        A_mod[j] = A[j] % M
    A_mod.sort(reverse=True)
    A_mod_sum = sum(A_mod)
    need = 0
    if A_mod_sum != 0:
        for j in range(N):
            need += M - A_mod[j]
            A_mod_sum -= M
            if A_mod_sum == 0:
                break
    if need <= K:
        left = i
    else:
        right = i - 1
    if left == right:
        ans = A_sum_div[left]
        break
    i = (left + right + 1) // 2

print(ans)

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(reverse =True)
    return divisors

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

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

sumli = sum(li)

div =make_divisors(sumli)
for i in range(len(div)):
    ans = div[i]
    diff = map(lambda x: min(x % ans, x-x%ans), li)
    a = sum(diff)
    if (a/2 < k):
        print(ans)
        break

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)

    list.sort(divisors, reverse=True)
    return divisors


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

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

a.sort()

a_sum = 0
for i in range(n):
    a_sum += a[i]

for i in make_divisors(a_sum):
    kaisu = 0
    for j in range(n-1):
        if a[j] % i < i - (a[j] % i):
            kaisu += a[j] % i
        else:
            kaisu += i - (a[j] % i)
    if kaisu<=k:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N,KK = list(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:
        divisors.append(n//i)

    # divisors.sort()
  return divisors
for i in sorted(make_divisors(sum(A)),key=lambda x:-x ):
  
  J = []
  j_prev=0
  for j in  sorted([a%i for a in A if a%i !=0]):
    J.append(j_prev+j)
    j_prev = J[-1]
  
  K = []
  k_prev=0
  for k in  sorted([a%i-i for a in A if a%i !=0],key=lambda x:-x ):
    K.append(k_prev+k)
    k_prev = K[-1]
  for jdx,j in enumerate(J):
    
    if jdx<len(K)-1 and j + K[-jdx-2] ==0:
      if j<= KK:
        print(i)
        quit()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter, deque
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys
#input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().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

D = sorted(make_divisors(sum(A)))

ans = 0
g0 = itemgetter(0)

for d in D:
    x = 0
    L = []
    R = []
    for i in range(N):
        L.append([A[i]%d, i, A[i]])
        R.append([-A[i]%d, i, A[i]])

    L = sorted(L, key=g0)
    R = sorted(R, key=g0)
    l = 0
    r = 0
    checked = [0]*N
    while l < N and L[l][0] == 0:
        checked[L[l][1]] = 1
        l += 1
        r += 1
        
    while l < N and checked[L[l][1]] == 0:
        m = min(L[l][0], R[r][0])
        L[l][0] -= m
        R[r][0] -= m
        x += m
        if L[l][0] == 0:
            checked[L[l][1]] = True
            l += 1
        if R[r][0] == 0:
            checked[R[r][1]] = True
            r += 1


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

print(ans)

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(reverse =True)
    return divisors

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

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

sumli = sum(li)

div =make_divisors(sumli)
for i in range(len(div)):
    ans = div[i]
    diff = map(lambda x: x % ans, li)
    a = sum(diff)
    if (a/2 < k):
        print(ans)
        break

Submission status: Wrong Answer

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

nums = A[:]

sum_n = sum(nums)

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)

    return divisors

divisors = sorted(list(make_divisors(sum_n)), reverse=True)

for d in divisors:
    mod_nums = list(map(lambda x: x%d, nums[:]))
    #print(mod_nums)
    diff_nums = list(map(lambda x: min(x, d-x), mod_nums))
    #print(diff_nums)
    #print(sum(diff_nums)/2)
    if sum(diff_nums)/2 <= K:
        ans = d
        break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def GCDs(*a):
    # リストで入力しないよう注意。
    if len(a) == 0:
        return -1  # エラー

    if len(a) == 1:
        return a[0]

    res = a[0]
    for i in range(1, len(a)):
        res = GCD(res, a[i])
    return res


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 solve(N: int, K: int, A: "List[int]"):
    tot = sum(A)
    divs = make_divisors(sum(A))

    m = 1
    for cand in divs[1:]:
        modA = [a % cand for a in A]
        counter = 0
        for ma in modA:
            if ma <= cand//2:
                counter += ma
            else:
                counter += cand-ma
        # print("counter", counter)
        if counter < 2*K:
            m = cand
    print(m)

    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))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A_sum = sum(A)
A_sum_div = []
div = 1
while div ** 2 <= A_sum:
    if A_sum % div == 0:
        A_sum_div.append(div)
        A_sum_div.append(A_sum // div)
    div += 1
A_sum_div.sort()

left = 0
right = len(A_sum_div) - 1
i = (left + right + 1) // 2
while True:
    M = A_sum_div[i]
    A_mod = [0] * N
    for j in range(N):
        A_mod[j] = A[j] % M
    A_mod.sort(reverse=True)
    A_mod_sum = sum(A_mod)
    need = 0
    if A_mod_sum != 0:
        for j in range(N):
            need += M - A_mod[j]
            A_mod_sum -= M
            if A_mod_sum == 0:
                break
    if need <= K:
        left = i
    else:
        right = i - 1
    if left == right:
        ans = A_sum_div[left]
        break
    i = (left + right + 1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
     n,k=map(int,input().split())
     a=list(map(int,input().split()))
     sum_a=sum(a)
     anskoho=[]
     for i in range(1,int(sum_a**0.5)+1):
          if sum_a%i==0:
               anskoho+=[i,sum_a//i]
     anskoho.sort(reverse=True)
     for i in anskoho:
          if sum([j%i for j in a])//2<=k:
               print(i)
               break
if __name__ == '__main__':
     main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import functools
import operator


def main():
  _, k = map(int, input().split())
  values = list(map(int, input().split()))
  values.sort(reverse=True)
  value = sum(values)
  elements = []

  for i in range(2, value):
    if i * i > value:
      break

    while value % i == 0:
      elements.append(i)
      value //= i

  elements.append(value)

  targets = set(itertools.chain.from_iterable([[
    functools.reduce(operator.mul, v) for v in itertools.combinations(elements, i)]
    for i in range(1, len(elements) + 1)]))
  targets = list(targets)
  targets.sort(reverse=True)

  for t in targets:
    r = 0

    for v in values:
      m = v % t
      r += min(m, t - m)

    if r <= k * 2:
      print(t)
      return

  print(1)


if __name__ == '__main__':
  main()

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)

    list.sort(divisors, reverse=True)
    return divisors


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

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

a.sort()

a_sum = 0
for i in range(n):
    a_sum += a[i]

for i in make_divisors(a_sum):
    kaisu = 0
    for j in range(n-1):
        if a[j] % i < i - (a[j] % i):
            kaisu += a[j] % i
        else:
            kaisu += i - (a[j] % i)
        if kaisu > k:
            break
    else:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
i = 1
while True:
  if sum(l)%i == 0 and k >= sum(l)//i:
    break
  i+= 1
print(sum(l)//i)

Submission status: Wrong Answer

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

nums = A[:]

sum_n = sum(nums)

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

divisors = sorted(list(make_divisors(sum_n)), reverse=True)

for d in divisors:
    mod_nums = list(map(lambda x: x%d, nums[:]))
    #print(mod_nums)
    diff_nums = list(map(lambda x: min(x, d-x), mod_nums))
    #print(diff_nums)
    #print(sum(diff_nums)/2)
    if sum(diff_nums)/2 < K:
        ans = d
        break
print(ans)

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

n, k = map(int, input().split())
dat = list(map(int, input().split()))
dat = list(map(abs, dat))
total = sum(dat)
divs = make_divisors(total)
for ds in divs:
    t = 0
    for i in range(n):
        t += min( (dat[i] % ds) , abs((dat[i] % ds) - ds))
        #print(" = {0} ... {1}".format(dat[i], min( (dat[i] % ds) , abs((dat[i] % ds) - ds))))
    #print("end: {0} {1}".format(ds, t))
    t = t // 2
    if t < k:
        res = ds
        break
print(ds)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,k=map(int,input().split())
a=list(map(int,input().split()))
arr=np.array(a)
ans=0
m=max(a)
for i in range(1,m):
    arr_=arr%i
    if sum(arr_)%i==0:
        l=0
        for j in range(n):
            l+=min(arr_[j],i-arr_[j])
        if l<=2*k:
            ans=i
print(ans)

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 = sum(A)
D = make_divisors(D)[::-1]

for d in D:
    a = []
    for i in range(N):
        a.append(A[i]%d)
    k = 0
    M = max(a)
    while k <= K and M != 0:
        i = 0
        j = 0
        m = d
        M = 0
        for l in range(N):
            if 0 < a[l] < m:
                m = a[l]
                i = l
            if a[l] > M:
                M = a[l]
                j = l
        if m == d:
            break
        if m <= d-M:
            a[i] = 0
            a[j] += m
            a[j] %= d
            k += m
        else:
            a[i] -= d-M
            a[i] %= d
            a[j] = 0
            k += d-M
    if k <= K:
        break

print(d)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque

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

A = [int(x) for x in input().split()]
S = sum(A)

div = set()
for d in range(1,S+1):
    if d*d > S:
        break
    if S%d == 0:
        div.add(d)
        div.add(S//d)

def F(d):
    # 全部をdの倍数にするまでの最小コスト
    cost = 0
    q = deque(sorted(x%d for x in A))
    while q:
        x = q[0]
        if x == 0:
            q.popleft()
            continue
        y = q[-1]
        if y == 0:
            q.pop()
        z = d - y
        t = x if x < z else z
        cost += t
        q[0] -= t
        q[-1] += t
        q[-1] %= d
    return cost

answer = None
div = sorted(div, reverse = True)
for d in div:
    cost = F(d)
    if cost <= K:
        answer = d
        break

print(answer)

Submission status: Wrong Answer

Solution code:
import math

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_sum = sum(a_list)
a_sum_yakusu = []
for i in range(1, int(math.sqrt(a_sum)) + 1):
    if a_sum % i == 0:
        a_sum_yakusu.append(i)
        a_sum_yakusu.append(a_sum // i)
a_sum_yakusu.sort(reverse=True)

ans = -1
for y in a_sum_yakusu:
    sub_list = [None] * n
    for i, a in enumerate(a_list):
        sub1 = abs(a % y)
        sub2 = abs(sub1 - y)
        sub_list[i] = min(sub1, sub2)
    sub_list.sort()
    sub_sum = sum(sub_list[:-1])
    if sub_sum <= k:
        ans = y
        break
print(ans)

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

n, k = map(int, input().split())
dat = list(map(int, input().split()))
total = sum(dat)
divs = make_divisors(total)
for ds in divs:
    t = 0
    for i in range(n):
        t += min( (dat[i] % ds) , abs((dat[i] % ds) - ds))
        #print(" = {0} ... {1}".format(dat[i], min( (dat[i] % ds) , abs((dat[i] % ds) - ds))))
    #print("end: {0} {1}".format(ds, t))
    t = t // 2
    if t < k:
        res = ds
        break
print(ds)

Submission status: Wrong Answer

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

A_sum = sum(A)
A_sum_div = []
div = 1
while div ** 2 < A_sum:
    if A_sum % div == 0:
        A_sum_div.append(div)
        A_sum_div.append(A_sum // div)
    div += 1
A_sum_div.sort()

left = 0
right = len(A_sum_div) - 1
i = (left + right + 1) // 2
while True:
    M = A_sum_div[i]
    A_mod = [0] * N
    for j in range(N):
        A_mod[j] = A[j] % M
    A_mod.sort(reverse=True)
    A_mod_sum = sum(A_mod)
    need = 0
    if A_mod_sum != 0:
        for j in range(N):
            need += M - A_mod[j]
            A_mod_sum -= M
            if A_mod_sum == 0:
                break
    if need <= K:
        left = i
    else:
        right = i - 1
    if left == right:
        if need <= K:
            ans = M
        else:
            ans = A_sum_div[left]
        break
    i = (left + right + 1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(2*i)
            if i**2 == n:
                continue
            ass.append(n//i)
            ass.append(n*2//i)
    return ass #sortされていない

def main():
    import sys,bisect
    input = sys.stdin.readline

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

    kouho = divisor(sum(a))
    kouho.sort(reverse = True)

    for e in kouho:
        tank = [s%e for s in a]
        if sum(tank)//2 <= k:
            print(e)
            exit()

if __name__ == '__main__':
    main()

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(reverse=True)
    return divisors


n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
d = make_divisors(s)
for x in d:
    b = a[:]
    for i in range(n):
        b[i] %= x
        if b[i] > x // 2:
            b[i] -= x
    su = sum(b)
    b[0] -= su
    abs_sum = 0
    for i in range(n):
        abs_sum += abs(b[i])
    if abs_sum // 2 <= k:
        print(x)
        break

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


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 main():
    n, k = get_li()
    A = get_li()
    ds = make_divisors(sum(A))
    ans = 1
    for d in ds[1:]:
        diff = 0
        for a in A:
            diff += min(a % d, d - a % d)
        if diff <= 2 * k:
            ans = d
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Wrong Answer

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

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=sum(arr)
ans=1
d=div(s)
for val in d:
  tmp=0
  for num in arr:
    tmp+=num%val
  if tmp%val==0 and tmp//2<=k:
    ans=max(ans,val)
print(ans)

Submission status: Wrong Answer

Solution code:
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass #sortされていない

def main():
    import sys,bisect
    input = sys.stdin.readline

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

    kouho = divisor(sum(a))
    kouho.sort(reverse = True)

    for e in kouho:
        tank = [s%e for s in a]
        if sum(tank)//2 <= k:
            print(e)
            exit()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

s = sum(a)
d = []
for i in range(1, s):
    if s % i == 0:
        d.append(i)
    if s <= i * i:
        break
    if s % i == 0:
        d.append(s // i)
d = list(reversed(sorted(d)))

for di in d:
    diff = 0
    for ai in a:
        diff += min(ai % di, di - ai % di)
    if diff <= 2 *k:
        print(di)
        break

Submission status: Wrong Answer

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

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

divs = divisors(total)
# print(divs)
for div in divs[::-1]:
    mod_div = [0] * n
    mod_sum = 0
    opr_cnt = 0
    for i, item in enumerate(a):
        mod_div[i] = item % div
    mod_sum = opr_cnt = sum(mod_div)
    mod_div.sort()
    for i, item in enumerate(mod_div[::-1]):
        # print(item, opr_cnt)
        mod_sum -= div
        opr_cnt += div - 2 * item
        if mod_sum == 0:
            break
    if opr_cnt <= k * 2:
        print(div)
        exit()
    # print(div, opr_cnt)

Submission status: Wrong Answer

Solution code:
from math import sqrt
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
div = []
for i in range(1, int(sqrt(s)+1)):
	if s%i == 0:
		if i*i != s:
			div.append(s//i)
		div.append(i)
div.sort(reverse=True)
#print(div)

for d in div:
	plus, minus = 0, 0
	for x in a:
		if x%d == 0:
			continue
		y, z = d-(x%d), x%d
		if plus+y <= minus+z:
			plus += y
		else:
			minus += z
	if max(plus, minus) <= k:
		print(d)
		break

Submission status: Wrong Answer

Solution code:
import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
fact=[]
for i in range(1,int(sum(a)**0.5)+1):
  if sum(a)%i==0:
    fact.append(i)
    fact.append(sum(a)//i)
fact=list(set(fact))
fact.sort()
fact.reverse()
a.sort()
a.reverse()
for i in range(len(fact)):
  a2=copy.copy(a)
  for j in range(n):
    a2[j]=a2[j]%fact[i]
  if (sum(a2)//2)<=k:
    print(fact[i])
    break

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(reverse=True)
    return divisors


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

div = make_divisors(sum(a))

for x in div:
    s = sum([ai % x for ai in a])

    if s % 2 == 1:
        s -= k

    if s % 2 == 0 and 0 <= s <= 2 * k:
        print(x)
        break

# 3 | 3 1 2 1 | 7
# 4 | 1 2 0 1 3 2 1 0 | 10

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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)
m = min(A)
jogen = m+K
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:
    if kouho>jogen:continue
    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

Submission status: Wrong Answer

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


def factorize(n: int) -> dict:
    b = 2
    fct = defaultdict(int)
    fct[n] = 1
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct[b] += 1
        b = b + 1
    if n > 1:
        fct[n] = 1
    return fct


a = min(A)
fct = factorize(sum(A))
for f in sorted(list(fct.keys()), reverse=True):
    if f <= a + K + 1:
        print(f)
        quit()

Submission status: Wrong Answer

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]
    for i in range(n)[::-1]:
        cnt += num - li[i]
        if ruiseki[i] == cnt:
            if cnt <= k:
                print(num)
                exit()

Submission status: Wrong Answer

Solution code:
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
#print(DivS)
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
        #kd<A[i]<(k+1)d
        #k=A[i]//d
        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)
    #print(d,B)
    if nowsum!=S:
        cost=sum([abs(A[i]-B[i]) for i in range(N)])
        for i in range(N):
            costtmp=cost-abs(A[i]-B[i])+abs(A[i]-(B[i]+S-nowsum))
            if costtmp<=2*K:
                ans=max(ans,d)
                break
    else:
        cost=sum([abs(A[i]-B[i]) for i in range(N)])
        if cost<=2*K:
            ans=max(ans,d)
print(ans)