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:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter #sort 
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # put inputs between specific values (almost as quickly)
        # ex) S = [-INF] + [int(r()) for _ in range(A)] + [INF]
        # open(0).read() is sometimes useful:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')
        
    # ----------------------------------
    # main

    N, K = R()
    A = R()
    A.sort(reverse=True)
    A_sub = [0] * N
    sumA = sum(A)
    
    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
    
    divisors = make_divisors(sumA)
    for divisor in divisors:
        for i in range(N):
            A_sub[i] = A[i] % divisor
        A_sub.sort()
        A_sub_zero = A_sub.count(0)
        A_sub_total = (N-A_sub_zero) * divisor
        SUM_A_sub = sum(A_sub)
        UNDER_SUM_A = A_sub_total - SUM_A_sub
        k = 0
        count = 0
        for i in A_sub:
            A_sub_total = A_sub_total - i
            count += i
            UNDER_SUM_A -= abs(divisor-i)
            if i >= UNDER_SUM_A:
                if k >= count:
                    print(divisor)
                    exit()
                else:
                    break
        
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # three methods for loop: keys(), values(), items()
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    # to make binary digits text
    >>> a = 5
    >>> bin_str_a = format(a, '#06b')
    >>> print(bin_str_a)
    0b0101 # first 2 strings (='0b') indicates it is binary
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

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+1:
    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:
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)
len_d = len(divisors)
if len_d%2 == 0:
  print(divisors[len_d//2])
else:
  num1 = divisors[len_d//2]
  num2 = divisors[len_d//2+1]
  if abs(num1-sum_n//N) > abs(num2-sum_n//N):
    print(num2)
  else:
    print(num1)

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
            if mod_ <= gcd - mod_:
                k_s += mod_
                mod += mod_
            else:
                k_s += (gcd - mod_)
                mod -= (gcd - mod_)

        if int(k_s/2) + 1 < k and mod == 0:
            ans = max(ans, gcd)

    print(ans)

Submission status: Wrong Answer

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

sss = sum(a)
mmm = max(a)

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

if (sss - mmm >= k):
    print(sss)
else:
    ddd = make_divisors(sss)
    # for di in ddd:
    #     for ai in a:
    print(max(ddd))

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
            if mod_ <= gcd - mod_:
                k_s += mod_
                mod += mod_
            else:
                k_s += (gcd - mod_)
                mod -= (gcd - mod_)

        if int(k_s/2) + 1 < k and mod % gcd == 0:
            ans = max(ans, gcd)

    print(ans)

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
        diff = 0
        for a in a_list:
            if a % ans == 0:
                continue
            na = a//ans
            near_up = ans * (na + 1)
            near_down = ans * (na)
            dup = abs(a-near_up)
            ddn = abs(a-near_down)
            dope = min(dup, ddn)
            if dup <= ddn:
                diff += dope
            else:
                diff -= dope
            ope += dope
            dprint(a, dope, diff)
        ope /= 2
        dprint(ans, ope, diff)
        if ope + abs(diff)%ans <= 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:
import sys
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

sumA = sum(A)
maxA = max(A)

if sumA - maxA <= K:
    print(sumA)
    sys.exit(0)

ans = 1
for j in range(1, min(int(sumA/N)+1, sumA - maxA)):
    if sumA % j == 0:
        ans = j
print(ans)

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 == middleCount % 2 :
            ans = div
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

arr = np.array(a)
wa = sum(arr)
divisors = make_divisors(wa)

ans = 1
for div in divisors:
    cnt = 0
    for i in range(n):
        cnt += min(a[i] % div, div - a[i] % div)
    if cnt % 2 == 0 and cnt / 2 <= k:
        ans = div

print(ans)

Submission status: Wrong Answer

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

A_sum = sum(A)

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

factors = prime_factors(A_sum)

if min(A) < K:
  print(sum)
else:
  print(max(factors))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def factorize(n):
    d = 2
    ans = []
    while d * d <= n:
        e = 0
        while n % d == 0:
            n /= d
            e += 1
        if e:
            ans.append((d,e))
        d += 1 + d%2
    if n > 1:
        ans.append((n, 1))
    return ans

from itertools import product
def divisors(N):
    facs = factorize(N)
    bases, expos = zip(*facs)
    for es in product(*[range(e+1) for e in expos]):
        ans = 1
        for i, e in enumerate(es):
            ans *= bases[i] ** e
        yield ans

def memo(f):
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)

def solve(N, K, A):
    S = sum(A)
    def check(g):
        items = []
        for x in A:
            positive = (-x)%g
            negative = g + x if x < g else x % g
            items.append((positive, negative))
        items.sort()
        possum = sum(p for p,n in items)
        negsum = sum(n for p,n in items)
        while items and possum > K:
            possum -= items.pop()[0]
        while items:
            negsum -= items.pop()[1]
        #print 'aa',possum,negsum
        return K >= possum and K >= negsum
    
    for g in sorted(divisors(S), reverse = True):
        if check(g): return g
    return 1
        


N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
print solve(N, K, A)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
checkA = [0]*len(A)

sumA = sum(A)
maxA = A[-1]
minA = A[0]


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

divs = md(sumA)

cnt = 0

for div in divs:
    if div >= maxA: continue
    else:
        print(div)
        exit()

Submission status: Wrong Answer

Solution code:
import math
import copy

#n = int(input())
n, k = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
list = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
#s = [input() for i in range(n)]
#s = input()
#list = list(s)
#temp = [[0 for _ in range(13)] for _ in range(13)]

tempmax = max(list) + k
list2 = copy.deepcopy(list)
ans = 1
m = n // 2

for i in range(tempmax, 1 , -1) :
    for j in range(n) :
        list2[j] = list[j] % i
    total = sum(list2)
    list2.sort()
    total2 = 0
    j = 0
    while(2 * (total2 + list2[j]) <= total):
        total2 += list2[j]
        j += 1


    if((total == i * (n - j)) and (total2 < 2 * k)) :
        ans = i
        break

print(ans)

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 and middleCount % 2 == 0 :
            ans = div
            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(reverse = True)
    return divisors

if __name__ == "__main__":
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    max = A[N-1]
    S = sum(A)
    divs = make_divisors(S)
    ans = 1
    D = len(divs)
    for i in range(D):
        d = divs[i]
        B = [a%d for a in A]
        C = [(d-a%d) for a in A]
        B.sort()
        b = 0
        c = sum(C)
        for i in range(N):
            b += B[i]
            c -= C[i]
            if b >= c :
                break
        if K < (b+c)//2:
            continue
        else:
            ans = d
            break
print(ans)

Submission status: Wrong Answer

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

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

for l in reversed(range(1,max(Xs)+K+1)):
    vari = []
    for x in Xs:
        #if abs(2*x%l-l) > K:
        #    vari = []
        #    break
        vari.append( (x%l, l-x%l) )
    if vari != []:
        sum1 = sum([v[0] for v in vari])
        sum2 = sum([v[1] for v in vari])
        max2 = min([v[1] for v in vari])
        if sum1 == sum2 and max2 <= K and len(Xs) == 2:
            print(l)
            #print(l, vari, sum1, sum2)
            exit()
        elif sum1 != sum2 and sum1%l == 0 and sum2%l == 0:
            print(l)
            #print(l, vari, sum1, sum2)
            exit()
        #print(l, vari, sum1, sum2)

Submission status: Wrong Answer

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

sumA = sum(A)
maxA = max(A)

if sumA - maxA <= K:
    print(sumA)
    sys.exit(0)

ans = 0
for j in range(1, min(int(sumA/N)+1, sumA - maxA)):
    if sumA % j == 0:
        ans = j
print(ans)

Submission status: Wrong Answer

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

List = []
List2 = []
A_sum = sum(A)
for i in range(1,int(A_sum**0.5)):
    if A_sum%i == 0:
        List.append(i)
for j in range(len(List)):
    a = A_sum//List[-1-j]
    if a in List:
        a = 0
    else:
        List2.append(a)

List = List + List2
ans = A_sum
for i in range(len(List)):
    num = 0
    for j in range(N):
        num += abs(List[i]-A[j])
    if num//2 <= K:
        ans = List[i]
        
print(ans)

Submission status: Wrong Answer

Solution code:
def calc(N, K, A):
    x = []
    sumA = sum(A)
    for i in range(1, int(sumA ** 0.5) + 1):
        if (sumA % i == 0):
            x += [i]
            if (i != sumA // i):
                x += [sumA // i]
    x.sort()
    x.reverse()
    for y in x:
        m = 0
        for a in A:
            m += min((a - (a // y) * y, (a // y + 1) * y - a))
        if (m <= K):
            return y
    return 1


(N, K) = tuple([int(s) for s in input().split(' ')])
A = [int(s) for s in input().split(' ')]
print(calc(N, K, A))

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 += (dat[i] % ds)
        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))
    if t < (k * 2):
        res = ds
        break
print(ds)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=sum(A)
GL=set()
for i in range(1,int(S**0.5)+1):
    if S%i==0:
        GL.add(i)
        GL.add(S//i)
GL=sorted(GL)

ans=1
for d in GL[1:]:
    M=0
    UD=[]
    pm=0
    for k,i in enumerate(A):
        div=i//d
        up = d * (div + 1) - i
        down = i - d * div
        if up<=down:
            M+=up
            pm+=up
            UD.append([k,up,down,1])
        else:
            M+=down
            pm-=down
            UD.append([k, up, down, 0])
    UD=sorted(UD, key=lambda x: abs(x[1]-x[2]))
    while pm!=0:
        i=0
        if pm>0:
            while i<N and UD[i][3]==1:i+=1
            if i==N:
                M=10**9
                break
            UD[i][3]=0
            pm-=d
            M+=abs(UD[i][1]-UD[i][2])

        else:
            while i<N and UD[i][3]==0:i+=1
            if i==N:
                M=10**9
                break
            UD[i][3]=1
            pm+=d
            M += abs(UD[i][1] - UD[i][2])
    M//=2
    if M<=K:
        ans=d
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
sum_a = sum(a)
def divisor(n): #約数全列挙
    ans = [1,n]
    i = 2
    while i**2 <= n:
        if n%i == 0:
            ans.append(i)
            if i**2 < n:
                ans.append(n//i)
        i += 1
    ans.sort()
    return ans
anslist = divisor(sum_a)
def solve(x):
    b =[a[i]%x for i in range(n)]
    b.sort()
    count = 0
    i = 0
    j = n-1
    now = 0
    while j > i:
        count += b[i]
        now += b[i]
        i += 1
        if now+b[j]>=x:
            now -= x-b[j]
            j -= 1
    if count > k:
        return False
    else:
        return True



ng = len(anslist)
ok = 0
s = 0
while abs(ng-ok)>1:
    middle = (ok+ng)//2
    if(solve(anslist[middle])):
        ok = middle
    else:
        ng = middle
    s += 1


print(anslist[ok])