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: Runtime Error

Solution code:
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))
        # does there exist a coloring so that sumpos and sumneg <= K
        @memo
        def dp(i, sumpos, sumneg):
            if sumpos > K or sumneg > K: return False
            if i == len(items): return True
            p, n = items[i]
            return dp(i+1, sumpos + p, sumneg) or dp(i+1, sumpos, sumneg + n)
        return dp(0,0,0)
    
    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: Runtime Error

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

sA = sum(A)


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 'prime number'
    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):  # 順に右にシフトさせ最下位bitのチェックを行う
            c *= lst[j]  # フラグが立っていたら bag に果物を詰める

    cnt = 0
    for a in A:
        cnt += min(a % c, c-(a % c))
    if cnt//2 <= K:
        print(c)
        exit()

print(1)

Submission status: Runtime Error

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.copy()
    idx, idx2 = 0, 0
    for i in range(n):
        b[i] %= x
        if b[i] > x // 2:
            b[i] -= x
    su = sum(b)
    mindex = b.index(min(b))
    maxdex = b.index(max(b))
    if su > 0:
        b[maxdex] -= su
    else:
        b[mindex] -= su
    abs_sum = 0
    for i in range(n):
        abs_sum += abs(b[i])
    if abs_sum // 2 <= k:
        print(x)
        break

Submission status: Runtime Error

Solution code:
import math


def check(A, d, K):
    modcnt = [0] * d
    cnt = 0
    for a in A:
        modcnt[a % d] += 1
    mx = d-1
    for i in range(d):
        while modcnt[i] > 0:
            modcnt[i] -= 1
            cnt += i
            pls = i
            while pls > 0:
                while modcnt[mx] == 0 and mx > 1:
                    mx -= 1
                if mx + pls >= d:
                    modcnt[mx] -= 1
                    pls -= d - mx
                else:
                    modcnt[mx] -= 1
                    modcnt[mx+pls] += 1
                    mx = mx+pls
                    pls = 0
    return cnt <= K


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)
    divs = [1, total]
    rt = int(math.sqrt(total))
    for i in range(2, rt+1):
        if total % i == 0:
            divs.append(i)
            if i**2 != total:
                divs.append(total//i)
    ans = 0
    for d in divs:
        if check(A, d, K):
            ans = max(ans, d)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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.copy()
    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: Runtime Error

Solution code:
from math import gcd


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: Runtime Error

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 = [], []
	for x in a:
		if x%d == 0:
			continue
		plus.append(d-(x%d))
		minus.append(x%d)
	if min(sum(plus)-max(plus), sum(minus)-max(minus)) <= k:
		print(d)
		break