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:
# -*- 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 = 1
g0 = itemgetter(0)

for d in D:
    d = 7
    x = 0
    X = []
    for i in range(N):
        X.append(A[i]%d)

    X = sorted(X)
    l = 0
    r = N-1
    while l < N and X[l] == 0:
        l += 1
    while l < N and (not (X[l] == 0 or X[l] == d)):
        m = min(X[l], d - X[r])
        x += m
        X[l] -= m
        X[r] += m
        if X[l] == 0:
            l += 1
        if X[r] == d:
            r -= 1
    if x <= K:
        ans = max(ans, d)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
A = [int(i) for i in input().split()]


def trial_division(n):
    # 素因数を格納するリスト
    factor = []
    # 2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    # リストが空ならそれは素数
    if not factor:
        return [n]
    else:
        factor.append(n)
        return factor


lst = sorted(trial_division(sum(A)))

n = len(lst)
for i in range((2 ** n)-1, 0, -1):
    c = 1
    for j in range(n):
        if ((i >> j) & 1):
            c *= lst[j]

    cnt_p, cnt_m = 0, 0
    for a in A:
        if a % c > c-(a % c):
            cnt_p += c-(a % c)
        elif a % c < c-(a % c):
            cnt_m += a % c
        else:
            if cnt_p < cnt_m:
                cnt_p += a % c
            else:
                cnt_m += a % c
    if cnt_m <= K and cnt_p <= K:
        print(c)
        exit()

print(1)

Submission status: Wrong Answer

Solution code:
import decimal,math
decimal.getcontext().prec = 100
def sum1(pre,l,r):
    l=max(l,0)
    if(l==0):
        return pre[r]
    return pre[r] - pre[l - 1]
abc=[]
def printDivisors(n) : 
      
    # Note that this loop runs till square root 
    i = 1
    while i <= math.sqrt(n): 
          
        if (n % i == 0) : 
              
            if (n / i == i) : 
                abc.append(i) 
            else : 
                abc.append(i)
                abc.append(n/i)
        i = i + 1
n,k=map(int,raw_input().split())

arr=map(int,raw_input().split())
s=sum(arr)
printDivisors(s)
abc.sort()
abc=abc[::-1]

for i in abc:
    l=0
    flag=0
    for j in arr:
        if(l>2*k):
            flag=1
            break
        l=l+(j%i)
    if(flag==0):
        print i
        exit()

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
A = [int(i) for i in input().split()]


def trial_division(n):
    # 素因数を格納するリスト
    factor = []
    # 2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    # リストが空ならそれは素数
    if not factor:
        return [n]
    else:
        factor.append(n)
        return factor


lst = sorted(trial_division(sum(A)))

n = len(lst)
for i in range((2 ** n)-1, 0, -1):
    c = 1
    for j in range(n):
        if ((i >> j) & 1):
            c *= lst[j]

    cnt_p, cnt_m = 0, 0
    for a in A:
        if a % c > c-(a % c):
            cnt_p += c-(a % c)
        elif a % c < c-(a % c):
            cnt_m += a % c
        else:
            if cnt_p < cnt_m:
                cnt_p += a % c
            else:
                cnt_m += a % c
    if cnt_m*2 <= K and cnt_p*2 <= K:
        print(c)
        exit()

print(1)

Submission status: Wrong Answer

Solution code:
import math

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

total = sum(a)
sq = int(math.sqrt(total))

memo=[]
for i in range(1,sq+1):
    if total%i==0:
        memo.append(i)
        if total != i*i:
            memo.append(total//i)

memo.sort()
# print(memo)

ans = 1

for i in memo:
    if i == 1:
        continue

    check = 0
    cnt = 0
    for j in range(n):
        mae = a[j]//i*i
        ato = mae + i
        if ato-a[j] < a[j]-mae:
            check += ato-a[j]
        else:
            check += mae-a[j]
        cnt += min(ato-a[j], a[j]-mae)
    # print(i, check, cnt)
    if cnt+abs(check)//2<=k*2:
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

sum_ = np.sum(a)
max_ = np.max(a)
for i in range(max_+k, 0, -1):
    if sum_%i != 0:
        continue
    if np.sum(np.abs(a%i))//2<= k:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a % b)


@mt
def slv(N, K, A):
    sa = sum(A)
    if K >= sa - max(A):
        return sa
    return 0


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(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()))
sumA = 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(reverse = True)  # ソート
    return divisors

ansList = divisors(sumA)
ans = 1

for div in ansList :
    posCount = 0
    negCount = 0
    middleCount = 0

    for a in A :
        b = a % div  # 倍数までの距離
        if b < (div - b) :
            negCount += b
        elif b > (div - b) :
            posCount += (div - b)
        else :
            middleCount += b

    if (posCount + negCount + middleCount) <= 2 * K :
        if (posCount - negCount) % 2 == 0 :
            ans = div
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt

N, K = map(int, input().split())
A = [int(s) for s in input().split()]
A.sort()
S = sum(A)
c = 0
ist = 0
for i in range(N):
    if A[i] > K:
        ist = i
        break
    c += A[i]
    K -= A[i]
    A[i] = 0
if A[-2] == 0:
    print(S)
    exit()
dl = []
dr = []
for i in range(1, round(sqrt(S)) + 1):
    if S % i != 0:
        continue
    dl.append(i)
    dr.append(S // i)
ds = dr + list(reversed(dl))
for i in ds:
    cnt = 0
    ok = True
    for v in A[ist:]:
        if v >= i:
            break
        cnt += i - v
        if cnt > c + K:
            ok = False
            break
    if ok:
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
def getDivisor(x):
    ans = []
    for d in range(1, int(x**0.5)+1):
        if x%d == 0:
            ans.append(d)
            if x//d != d:
                ans.append(x//d)
    return sorted(ans)


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

sumA = sum(As)
divisors = getDivisor(sumA)
#print(divisors)

def f(d):
    sumAdd = sumSub = 0
    maxAdd = maxSub = 0
    nAdd = nSub = 0
    d2 = d//2
    for i, A in enumerate(As):
        BmodD = A%d
        if BmodD == 0:
            pass
        elif BmodD <= d2:
            # 減らす
            sumSub += BmodD
            if BmodD > maxSub:
                maxSub = BmodD
            nSub += 1
        else:
            # 増やす
            sumAdd += d-BmodD
            if d-BmodD > maxAdd:
                maxAdd = d-BmodD
            nAdd += 1

    if sumSub == sumAdd:
        return sumSub <= K and sumAdd <= K
    elif sumSub > sumAdd:
        # 減らし過ぎ
        if nSub == N:
            sumSub -= maxSub
            sumAdd += d-maxSub
        return sumSub <= K and sumAdd <= K
    else:
        # 増やし過ぎ
        if nAdd == N:
            sumSub += d-maxAdd
            sumAdd -= maxAdd
        return sumSub <= K and sumAdd <= K


for d in reversed(divisors):
    ret = f(d)
    if ret:
        print(d)
        break
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumA = 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(reverse = True)  # ソート
    return divisors

ansList = divisors(sumA)
ans = 1

for div in ansList :
    posCount = 0
    negCount = 0
    middleCount = 0

    for a in A :
        b = a % div  # 倍数までの距離
        if b < (div - b) :
            negCount += b
        elif b > (div - b) :
            posCount += (div - b)
        else :
            middleCount += b

    if (posCount + negCount + middleCount) <= 2 * K :
        if posCount - negCount == 0 :
            ans = div
            break

print(ans)

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:
n,k = map(int,input().split())
a = list(map(int,input().split()))

s = 2
l = [0]*n
maxs = 0
while s < min(a)+k:
    for i in range(n):
        l[i] = a[i]%s
    l.sort()
    sml = sum(l)
    ns = sml//s
    if sml%s == 0 and -sum(l[len(l)-ns:len(l)])+ns*s<=k:
        maxs = s
    s = s + 1
print(maxs)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
A = sum(a)
fact = []

for i in range(1, 10 ** 6):
  if A % i == 0:
    fact.append(i)
    fact.append(A//i)
fact = list(set(fact)) 
fact.sort(reverse=True)

#print(fact)

for i in fact:
  L = [a[_]%i for _ in range(n)] 
  L.sort(reverse=True)
  #print(L)
  if sum(L[1::]) <= k:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
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 = 1
g0 = itemgetter(0)

for d in D:
    x = 0
    X = []
    for i in range(N):
        X.append(A[i]%d)

    X = sorted(X)
    l = 0
    r = N-1
    while l < N and X[l] == 0:
        l += 1
    while l < N and (not (X[l] == 0 or X[l] == d)):
        m = min(X[l], d - X[r])
        x += m
        X[l] -= m
        X[r] += m
        if X[l] == 0:
            l += 1
        if X[r] == d:
            r -= 1
    if d <= K:
        ans = max(ans, d)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from heapq import heappush, heapreplace
from itertools import count, product
from functools import reduce
from math import ceil, sqrt
from collections import defaultdict, deque

class Primes_C(object):
    def b_search(L,t):
        #増大列LについてL[:+1]の要素すべてがt以下であるような最大のi<len(L)を返す。
        search_range = [-1, len(L)]
        update_range = lambda mid: search_range.__setitem__(t<L[mid], mid)
        for _ in range(search_range[1].bit_length()):
            update_range(sum(search_range)//2)
        return search_range[0]
    
    def __init__(self):
        self.P = [2]
        self.Pappend = self.P.append
        self.Q = deque([])
        self.Qappend = self.Q.append
        self.Qpopleft = self.Q.popleft
        self.hq = [] 
        self.integer = count(3,2)
        self.current_i = 2
        self.valid_range = 1
        self.iter_index = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.iter_index >= len(self.P):
            self.step_calc(1)
        self.iter_index += 1
        return self.P[self.iter_index-1]
        pass

    def iter_reset(self, index=0):
        self.iter_index = index

    def list(self, max_int=None):
        if max_int is None:
            return self.P[:]

        if  max_int <= self.current_i:
            return self.P[:Primes_C.b_search(self.P,max_int)+1]

        else:
            self.calc(max_int)
            return self.P[:]

    def extend(self, i):
        if i >= self.valid_range:
            if self.Q:
                q = self.Qpopleft()
                heappush(self.hq, (q**2,q))
            self.valid_range = self.Q[0]**2 if self.Q else i**2

    def check_update(self,i):
        m,r = self.hq[0] if self.hq else (0,0)
        flag =  (i != m)
        if flag:
            self.Pappend(i)
            self.Qappend(i)
        while m == i:
            heapreplace(self.hq, (m+2*r, r))
            m,r = self.hq[0]
        return flag

    def calc(self, max_int):
        for i in self.integer:
            self.extend(i)
            self.check_update(i) 
            self.current_i = i+1
            if max_int <= self.current_i:
                break

    def step_calc(self, step):
        for i in self.integer:
            self.extend(i)
            step -= self.check_update(i) 
            self.current_i = i+1
            if not step:
                break

    def factorization(self, m, F=defaultdict(int)):
        max_int = ceil(sqrt(max(m, 0)))
        index0 = len(self.P)
        index = 0
        p = self.P[0]
        while m > 1 and p <= max_int:
            while not m%p:
                m //= p
                F[p] += 1

            index += 1
            if index >= index0:
                self.step_calc(1)
            p = self.P[index]

        if m > 1:
            F[m] += 1

        return F



def solve():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    Primes = Primes_C()

    F = Primes.factorization(sum(A))
    res = 1
    for q in product(*[[p**m for m in range(F[p]+1)] for p in F]):
        d = reduce(int.__mul__, q)
        B = [a%d for a in A]
        if sum(B)-max(B) <= K:
            res = max(res, d)
            
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumA = 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(reverse = True)  # ソート
    return divisors

ansList = divisors(sumA)
ans = 1

for div in ansList :
    posCount = 0
    negCount = 0
    middleCount = 0

    for a in A :
        b = a % div  # 倍数までの距離
        if b < (div - b) :
            negCount += b
        elif b > (div - b) :
            posCount += (div - b)
        else :
            middleCount += b

    if (posCount + negCount + middleCount) <= 2 * K :
        if middleCount % 2 == 0 :
            if posCount - negCount == 0 :
                ans = div
                break


print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [ int(v) for v in input().split() ]
num_list = [ int(v) for v in input().split() ]

max_candidate = sum(num_list) // n


def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list
        
divisor_list = make_divisor_list(sum(num_list))

ans = 1
for i in divisor_list:
    num_list_mod_i = sorted([ j % i for j in num_list])


    if sum(num_list_mod_i) <= k*2:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N, K = [int(i) for i in input().split()]
a_ls = [int(i) for i in input().split()]

sum_a = sum(a_ls)
cnt = 1
while True:
    if sum_a % cnt == 0:
        target = sum_a / cnt
    else:
        cnt += 1
        continue
    if target == 1:
        break
    a_ls = [a % target for a in a_ls]
    small2large = a_ls.copy()
    large2small = [target-a for a in a_ls]
    heapq.heapify(small2large)
    heapq.heapify(large2small)
    small = heapq.heappop(small2large)
    large = heapq.heappop(large2small)
    new_cnt = 0
    flg = False
    _sum = 0
    while True:
        if small < large:
            large -= small
            small = heapq.heappop(small2large)
            new_cnt += 1
            _sum += small
        elif small == large:
            new_cnt += 2
            _sum += small
            if _sum > K:
                break
            if new_cnt == len(a_ls):
                flg = True
                break
            large = heapq.heappop(large2small)
            small = heapq.heappop(small2large)
        else:
            small -= large
            large = heapq.heappop(large2small)
            new_cnt += 1
            _sum += large
        if len(large2small) == 0 or len(small2large) == 0:
            flg = True
            break
        if _sum > K:
            break
    if flg:
        break
    cnt += 1
print(int(target))

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, raw_input().split())
A = map(int, raw_input().split())

sum_A = sum(A)
D = make_divisors(sum_A)
D.sort()
D.reverse()

ans = 1
for d in D:
    pos = True
    sum_k = 0
    stock_k = 0
    for a in A:
        mod_a = a % d
        min_k = min(abs(mod_a), abs(d - mod_a), abs(d + mod_a))
        if mod_a + min_k == 0:
            stock_k += min_k
        else:
            stock_k -= min_k

        sum_k += min_k
        if K * 2 < sum_k:
            pos = False
            break

    if pos:
        mod_s = stock_k % d
        min_s = min(abs(mod_s), abs(d - mod_s), abs(d + mod_s))
        if sum_k + min_s <= K * 2:
            ans = d
            break

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
def divisor_list(N): #素因数分解
    res = []
    i = 1
    while i*i < N:
        if N%i == 0:
            res.append(i)
            res.append(N//i)
        i += 1
    if i*i == N: res.append(i)
    return sorted(res)

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,k = [int(i) for i in readline().split()]
aaa = [int(i) for i in readline().split()]


l = list(reversed(divisor_list(sum(aaa))))


def check(x):
    res = []
    for ai in aaa:
        c = ai%x
        d = ai%x-x
        if abs(c) > abs(d): res.append(d)
        else: res.append(c)
    res.sort(key = abs)
    
    d = sum(res)
    if d > 0:
        idx = -1
        while d > 0:
            if res[idx]>0:
                d -= x
                res[idx] -= x
            idx -= 1
    elif d < 0:
        idx = -1
        while d < 0:
            if res[idx]<0:
                d += x
                res[idx] += x
            idx -= 1
                
    c = sum([i for i in res if i > 0])        

    print(x,c,res)
    return (c <= k)



for x in l:
    if check(x):
        print(x)
        exit()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
A = sum(a)
fact = []

for i in range(1, int(A**(1/2))+2):
  if A % i == 0:
    fact.append(i)
    fact.append(A//i)
fact = list(set(fact)) 
fact.sort(reverse=True)

#print(fact)

for i in fact:
  L = [a[_]%i for _ in range(n)] 
  L.sort(reverse=True)
  #print(L)
  if sum(L[1::]) <= k:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
from math import ceil
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()))

a_sum = sum(a)

if a_sum - max(a) <= k:
    print(a_sum)

else:
    l = make_divisors(sum(a))
    m = len(l)
    ans = 1

    for gcd in l:
        mod = 0
        k_s = 0
        for a_ in a:
            mod_ = a_ % gcd
            k_s += min(mod_, gcd - mod_)
            mod += mod_
        if int(k_s/2) + 1 < k:
            ans = max(ans, gcd)

    print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

def decompose(n):
	if n == 1:
		return []
	
	if n % 2 == 0:
		return decompose(n // 2) + [2]
	
	for i in range(3, math.floor(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			return decompose(n // i) + [i]
	return [n]

def check(a_list, p):
	total_m = 0
	total_p = 0
	for a in a_list:
		a_f = a - (a % p)
		a_c = a_f + p
		minus = a - a_f
		plus = a_c - a
		if minus > plus:
			total_p += plus
		else:
			total_m += minus
	
	return (total_p + total_m) // 2

total = sum(a_list)
checked = set()
for p in [total] + decompose(total):
	if p in checked:
		continue
	checked.add(p)
	if check(a_list, p) <= K:
		print(p);
		exit(0)
print(1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def main():
    N, K = LI()
    a_list = LI()
    a_list = sorted(a_list)
    total = sum(a_list)

    pfactors = prime_factors(total)
    from collections import Counter
    c = Counter(pfactors)
    dprint(c)

    factor_list = []
    for f, c in c.items():
        k_list = list(range(0, c+1))
        factor_list.append([f**k for k in k_list])

    dprint(factor_list)
    ans_list = []
    from itertools import product
    for tup in product(*factor_list):
        ans = 1
        for t in tup:
            ans *= t
        ans_list.append(ans)

    ans_list = sorted(ans_list, reverse=True)
    dprint(ans_list)

    def check(ans):
        ope = 0
        for a in a_list:
            if a % ans == 0:
                continue
            na = a//ans
            near_up = ans * (na + 1)
            near_down = ans * (na)
            dope = min(abs(a-near_up), abs(a-near_down))
            ope += dope
            #dprint(a, dope)
        ope /= 2
        dprint(ans, ope)
        if ope <= K:
            return True
        else:
            return False

    for ans in ans_list:
        flag = check(ans)
        dprint(ans, flag)
        dprint()
        if flag:
            print(ans)
            return


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()
    return divisors
N, K = map(int, input().split())
nums = list(map(int, input().split()))
sum_n = sum(nums)
# divisors = make_divisors(sum_n)
if sum_n//N == sum_n/N:
  print(sum_n//N)
else:
  print(1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumA = 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(reverse = True)  # ソート
    return divisors

ansList = divisors(sumA)
ans = 1

for div in ansList :
    posCount = 0
    negCount = 0

    for a in A :
        b = a % div
        if b < (div - b) :
            negCount += b
        else :
            posCount += (div - b)

    if negCount + posCount <= 2 * K and ((negCount - posCount) % 2 == 0) :
        ans = div
        break

print(ans)

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 = sorted([a % cand for a in A])
        counter = 0
        left = 0
        while left < N and modA[left] == 0:
            left += 1
        right = N-1
        while left < right and counter < K:
            smaller = min(modA[left], cand - modA[right])
            modA[left] -= smaller
            modA[right] += smaller
            counter += smaller
            if modA[left] == 0:
                left += 1
            if modA[right] == cand:
                right -= 1
        if counter <= 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:
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
    total = 0
    for j in range(n-1):
        if a[j] % i < i - (a[j] % i):
            kaisu += a[j] % i
            total += a[j] % i
        else:
            kaisu += (i - (a[j] % i))
            total -= (i - (a[j] % i))
    if (kaisu+abs(total))/2<=k:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumA = 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(reverse = True)  # ソート
    return divisors

ansList = divisors(sumA)
ans = 1

for div in ansList :
    posCount = 0
    negCount = 0

    for a in A :
        b = a % div
        if b < (div - b) :
            negCount += b
        else :
            posCount += (div - b)

    if negCount <= K and posCount <= K :
        ans = div
        break

print(ans)