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: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, A: "List[int]"):
    s = sum(A)
    A.sort()
    i = 1
    #print(s)
    #print(A)
    ret = 1
    def is_ok(n):
        downs = []
        for v in A:
            downs.append(v % n)
        downs.sort()
        #print(n, downs)
        cnt = float('inf')
        for i in range(1, N):
            left = 0
            right = 0
            for l in range(i):
                left += downs[l]
            for r in range(i, N):
                right += (n - downs[r])
            tmp = max(left, right)
            cnt = min(cnt, tmp)
            #print(i, left, right, cnt)
        #print(cnt)
        if cnt <= K:
            return True
        return False

    while i * i <= s:
        if s % i == 0:
            if is_ok(s // i):
                ret = max(ret, s // i)
            if is_ok(i):
                ret = max(ret, i)
        i += 1
    print(ret)
    return


def _solve(N: int, K: int, A: "List[int]"):
    s = sum(A)
    A.sort()
    i = 1
    print(s)
    print(A)
    ret = 1
    def is_ok(n):
        cnt = 0
        ls = 0
        us = 0
        bs = 0
        for v in A:
            tmp = v // n
            l = abs(v - n * (tmp))
            u = abs(v - n * (tmp + 1))
            if l < u:
                ls += l
            elif l > u:
                us += u
            else:
                bs += l
        cnt = max(ls, us)
        #cnt = min(ls, us)
        #rest = abs(ls - us)
        #if rest >= bs:
        #    rest -= bs
        #    cnt += bs + rest
        print(n, ls, us, cnt)
        if cnt <= K:
            return True
        return False

    while i * i <= s:
        if s % i == 0:
            if is_ok(s // i):
                ret = max(ret, s // i)
            if is_ok(i):
                ret = max(ret, i)
        i += 1
    print(ret)
    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: Accepted

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

summ = sum(nums)
divisors = []

for d in range(1, summ):
	if d * d > summ:
		break
	if summ % d == 0: #約数
		divisors.append(d)
		divisors.append(int(summ // d))

divisors.sort(reverse = True)

# print(divisors)

for d in divisors:

	residues = [0] * n
	for i in range(n):
		residues[i] = nums[i] % d

	residues.sort(reverse = True)

	init_sum = sum(residues)
	num_reverse = init_sum // d

#	times_operation = 0
#	for i in range(num_reverse):
#		times_operation -= num_reverse
	times_operation = d * num_reverse - sum(residues[0:num_reverse])

# 	print(d, residues, num_reverse,  times_operation)

	if times_operation <= k:
		print(d)
		exit()

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
n,k = words(int)
xs = words(int)

def divisor (x):
    ans = []
    for i in range(1, int(x**0.5)+1):
        if x % i == 0:
            ans.append(i)
            if i != x // i:
                ans.append(x//i)
    ans.sort()
    return list(reversed(ans))

s = sum(xs)
#print(s)
ds = divisor(s)
ans = 1
#print(ds)
for d in ds:
    ms = []
    for x in xs:
        ms.append(x%d)
    ms.sort()
    #print(d,ms)
    f = 0
    f_ttl = ms[f]
    b = len(ms)-1
    b_ttl = d - ms[b]
    while f != b:
        if f_ttl >= b_ttl:
            b -= 1
            b_ttl += d - ms[b]
        else:
            f += 1
            f_ttl += ms[f]
    if k >= f_ttl:
        ans = d
        break
print(ans)

Submission status: Accepted

Solution code:
# an = list(map(int, input().split()))
# n, m = map(int, input().split())
# n = int(input())

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

sa = sum(an)
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
div = make_divisors(sa)

for d in div[::-1]:
  if d == 1:
    print(1)
    break
  bn = [a % d for a in an if a % d != 0]
  bn.sort()
  sb = sum(bn)
  sb_l = sum(bn[:-1*(sb//d)])
  if sb_l <= k:
    print(d)
    break

Submission status: Accepted

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()
else:
  print(1)

Submission status: Accepted

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 = (i - k)
    else:
      if c + (i - k) <= K:
        c += (i - k)
      else:
        break
  else:
    print(i)
    break

Submission status: Accepted

Solution code:
submit = True


def solve_e(test=False, n=2, k=3, a_list=[8, 20]):

    if not test:
        n, k = map(int, input().split())
        a_list = list(map(int, input().split()))

    a_sum = sum(a_list)
    q_list = []

    for i in range(1, int(a_sum ** 0.5)+1):
        if a_sum % i == 0:
            q_list.append(i)
            if i != a_sum // i:
                q_list.append(a_sum // i)

    res = 1
    for q in q_list:
        r_list = [0] * n
        for i in range(n):
            r_list[i] = a_list[i] % q
        r_list_s = sorted(r_list)
        cnt = 0
        right = n - 1
        for i in range(n):
            if r_list_s[i] == q:
                break
            r = r_list_s[i]
            cnt += r
            while r > 0:
                d = q - r_list_s[right]
                if r >= d:
                    r -= d
                    r_list_s[right] = q
                    right -= 1
                else:
                    r_list_s[right] += r
                    r = 0
            r_list_s[i] = 0
        if cnt <= k:
            if q > res:
                res = q

    print(res)


if __name__ == "__main__":
    if submit:
        solve_e()
    else:
        solve_e(test=True, n=2, k=3, a_list=[8, 20])
        solve_e(test=True, n=2, k=10, a_list=[3, 5])
        solve_e(test=True, n=4, k=5, a_list=[10, 1, 2, 22])
        solve_e(test=True, n=8, k=7, a_list=[1, 7, 5, 6, 8, 2, 6, 5])

Submission status: Accepted

Solution code:
def divi(n):
    res = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n//i)
    return res
N, K = map(int, input().split())
A = list(map(int, input().split()))

SA = sum(A)
D = divi(SA)
D.sort(reverse = True)
ans = 0
for d in D:
    P = []
    for a in A:
        P.append(-(-a//d)*d - a)
    P.sort()
    ups = sum(P)
    if ups <= K:
        ans = d
        break
    ss = ups
    for i in range(1, N+1):
        ss -= P.pop()
        if max(ss, i*d -ups + ss) <= K:
            ans = d
            break
    else:
        continue
    break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial


def divisor(n): #nの約数を全て求める
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    table.sort(reverse=True)
    return table


def check(data, ele, num, k):
    plus, minus = 0, 0
    amari_dic = defaultdict(int)
    for i in range(num):
        now_num = data[i]
        amari = now_num % ele
        amari_dic[amari] += 1
        # if now_num >= ele:
        #     plus += now_num - ele
        # else:
        #     minus += ele - now_num

    amari_dic = sorted(amari_dic.items(), key=lambda x: x[0])

    for amari, kosuu in amari_dic:
        if amari == 0:
            continue
        ikeru = min((k - plus) // amari, kosuu)
        plus += ikeru * amari
        minus += (kosuu - ikeru) * (ele - amari)


    # print(ele, plus, minus, amari_dic)
    if max(plus, minus) <= k:
        return 1
    else:
        return 0

def main():

    num, k = map(int, input().split())
    data = list(map(int, input().split()))

    sum_num = sum(data)
    yakusuu_list = divisor(sum_num)

    # print(yakusuu_list)

    for ele in yakusuu_list:
        if check(data, ele, num, k):
            print(ele)
            sys.exit()







if __name__ == '__main__':
    main()

Submission status: Accepted

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]
        tank.sort()

        p = 0
        q = n-1

        s = tank[0]
        t = e-tank[-1]
        while p != q-1:
            if s > t:
                q -= 1
                t += e-tank[q]
            else:
                p += 1
                s += tank[p]


        if s <= k:

            print(e)
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

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()
            continue
        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: Accepted

Solution code:
n, k = 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(reverse=True)
    return divisors


s = sum(a)
divisors = make_divisors(s)

for d in divisors:
    reminders = [ai % d for ai in a]
    reminders.sort()
    for i in range(n - sum(reminders) // d, n):
        reminders[i] -= d

    se = sum(abs(r) for r in reminders)
    if se <= 2 * k:
        print(d)
        break

Submission status: Accepted

Solution code:
# E

import sys

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

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

s = sum(a)

l = []

def check(b) :
    r1 = [x % b for x in a]
    r1.sort()
    s1 = sum(r1)
    
    mn = 1e9
    s2 = 0
    for i in range(n):
        s2 += r1[i]
        mn = min(max(s2, (n-1-i)*b - (s1-s2)), mn)
        
    if mn <= k :
        print(int(b))
        sys.exit(0)
        

for p in range(1,int((s+1)**0.5+1)) :
    if s % p != 0:
        continue
    b = s // p
    l.append(b)
    check(b)
    
l.reverse()

for p in l:
    b = s // p
    check(b)

Submission status: Accepted

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

sA = sum(A)

div_list = []

for i in range(1,int(sA**0.5)+1):
    if sA%i==0:
        if i!=sA**0.5:
            div_list.append(i)
            div_list.append(sA//i)
        else:
            div_list.append(i)


div_list.sort(reverse=True)

for d in div_list:
    count=0
    count_list = []
    l = 0
    for a in A:
        n=a%d
        if n!=0:
            l+=1
            count+=n
            count_list.append(n)

    if count%d==0:
        if count//d<l:
            count_list.sort()
            if sum(count_list[:l-count//d])<=K:
                break

print(d)

Submission status: Accepted

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:
    aa = [ai % x for ai in a]
    aa.sort()
    ss = aa[:len(aa) - sum(aa) // x]
    s = sum(ss)

    if 0 <= s <= k:
        print(x)
        break

# 2 | 3 5 | 8 _ 3
# 3 | 3 1 2 1 | 7 _ 4
# 4 | 1 2 0 1 3 2 1 0 | 10 _ 5

Submission status: Accepted

Solution code:
import math
n,k = map(int,input().split())
lis = list(map(int,input().split()))
li = []
num = sum(lis)
for i in range(1,math.ceil(math.sqrt(num))+1):
    if num % i == 0:
        li.append(i)
        li.append(num // i)
li.sort(reverse = True)


for numb in li:
    liss = []
    for i in lis:
        if i % numb == 0:
            liss.append(numb)
        else:
            liss.append(i % numb)
    liss.sort(reverse=True)
    co = 0
    numm = sum(liss)

    for i in range(numm//numb):
        co += numb-liss[i]
    if co <= k:
        print(numb)
        exit()

Submission status: Accepted

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

n, k = map(int, input().split())
alist = list(map(int, input().split()))
nagaa = len(alist)
wa = sum(alist)
yakusu=make_divisors(wa)
ng=len(yakusu)

for i in range(ng):
    nowyaku=yakusu[ng-i-1]
    amalist=[]
    for al in alist:
        amalist.append(al%nowyaku)
    amalist=sorted(amalist)
    amawa=sum(amalist)
    hidari=amawa
    migi=0
    j=0
    while hidari!=migi:
        #try:
        nowama=amalist[nagaa-j-1]
        hidari-=nowama
        migi+=(nowyaku-nowama)
        j+=1
    #print(hidari, nowyaku)
    if hidari<=k:
        print(nowyaku)
        exit()
    #print(hidari, nowyaku)

Submission status: Accepted

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 = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
li = make_divisors(sum(A))
for i in li[::-1]:
    cnt = 0
    B = [x%i for x in A]
    B.sort(reverse=True)
    now_all = sum(B)
    for j in B:
        if(now_all==0):break
        if(j!=0):
            cnt += i-j
            now_all -= i
    if(cnt<=K):
        print(i)
        break

Submission status: Accepted

Solution code:
def divisible(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())
arr = list(map(int, input().split()))
divs = divisible(sum(arr))

for div in divs:
    test_arr = [x % div for x in arr]
    test_arr.sort()
    sum_test_arr = sum(test_arr)
    change = sum(test_arr[:-sum_test_arr // div])
    if change <= k:
        print(div)
        exit()

Submission status: Accepted

Solution code:

# 素因数分解
from collections import Counter
from itertools import product
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield n

from functools import reduce
import operator
int_product = lambda it: reduce(operator.mul,it,1)


def divisors(n):
    factors = prime_factors(n)
    factors = Counter(factors)
    pows = tuple(factors.values())
    factors = tuple(factors.keys())
    for pp in product(*(range(p+1) for p in pows)):
        yield int_product(f**p for f,p in zip(factors,pp))


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

def check(m):
    cost = 0
    S = sorted(a%m for a in A)
    total = sum(S)//m
    # print(m,S, total)
    return (sum(s for s in S[:N-total]) + sum(m-s for s in S[N-total:]))//2

for d in sorted(divisors(sum(A)), reverse=True):
    # print(d,check(d))
    if check(d) <= K:
        print(d)
        break

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
S = sum(A)
P = []
_P = []
for i in range(1, int(math.sqrt(S)) + 1):
  if S % i:
    continue
  P.append(S // i)
  _P.append(i)
P += _P[::-1]
for p in P:
  _A = sorted([a - p * (a // p) for a in A], reverse=True)
  n = sum(_A) // p
  if sum(_A) - sum(_A[:n]) <= K:
    print(p)
    break

Submission status: Accepted

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]):
        if mod_sum == 0:
            break
        # print(item, opr_cnt)
        mod_sum -= div
        opr_cnt += div - 2 * item
    if opr_cnt <= k * 2:
        print(div)
        exit()
    # print(div, opr_cnt)

Submission status: Accepted

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]%=fact[i]
  a2.sort()
  a2.reverse()
  ct=0
  for m in range(sum(a2)//fact[i]):
    ct+=a2[m]
  if (sum(a2)-ct)<=k:
    print(fact[i])
    break

Submission status: Accepted

Solution code:
# @author 

import sys

class EMaxGCD:
    def solve(self):
        n, k = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]
        a.sort()
        s = sum(a)
        ans = 1
        for u in range(1, int(s ** .5) + 1):
            if s % u:
                continue
            v = s // u
            for d in [u, v]:
                b = sorted([x % d for x in a])
                need = 0
                l, r = 0, n - 1
                while l < r:
                    m = min(b[l], d - b[r])
                    need += m
                    b[l] -= m
                    b[r] += m
                    if b[r] % d == 0:
                        r -= 1
                    if b[l] % d == 0:
                        l += 1
                # for x in b:
                #     if x <= d - x:
                #         need += x
                # print(d, need, b)
                if need <= k:
                    ans = max(ans, d)

        print(ans)


solver = EMaxGCD()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y, x%y)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        # nを合う数字で割り切れたら、その割った数と商をリストに追加する。
        # nが平方数のとき、同じ数字が2回追加されてしまうので3行したのif文がある
        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 = list(map(int,input().split()))

sums = sum(a_list)
divisors = make_divisors(sums)
divisors.reverse()

def func():
    for d in divisors:
        amaris = [a%d for a in a_list]
        amaris.sort()
        amaris.reverse()
        amari_sum = sum(amaris)
        hanten_cnt = int(amari_sum / d)
        sousa_cnt = 0
        for i in range(hanten_cnt):
            sousa_cnt += d - amaris[i]
        if sousa_cnt <= K:
            return d

result = func()

print(result)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b,c = LI()
    c -= a-b
    print(max(0,c))
    return

#B
def B():
    n = I()
    ans = 0
    for i in range(1,n+1):
        s = str(i)
        if len(s)%2:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    h = LI()
    h[0] -= 1
    for i in range(n-1):
        if h[i+1] < h[i]:
            print("No")
            return
        if h[i+1] > h[i]:
            h[i+1] -= 1
    print("Yes")
    return

#D
def D():
    s = S()
    n = len(s)
    ans = [0]*n
    l = 0
    i = 0
    while i < n:
        if s[i] == "L":
            j = i
            while i < n and s[i] == "L":
                i += 1
                l += 1
            if l:
                if (l+j-i)%2:
                    ans[j-1] = l-l//2
                    ans[j] = l//2
                else:
                    ans[j-1] = l//2
                    ans[j] = l-l//2
            l = 0
        else:
            l += 1
            i += 1
    print(*ans)
    return

#E
def E():
    def factor(n):
        if n == 1:
            return [1]
        if n < 4:
            return [1,n]
        i = 2
        res = [1]
        while i**2 <= n:
            if n%i == 0:
                res.append(i)
                if n//i != i:
                    res.append(n//i)
            i += 1
        res.append(n)
        res.sort()
        return res

    n,k = LI()
    a = LI()
    s = sum(a)
    f = factor(s)
    for i in f[::-1]:
        s = 0
        b = [[a[j]%i,-a[j]%i] for j in range(n)]
        b.sort()
        for j in range(n-1):
            b[j+1][0] += b[j][0]
            b[j+1][1] += b[j][1]
        for j in range(n-1):
            if b[j][0] == b[n-1][1]-b[j][1]:
                break
        s = b[j][0]
        if s <= k:
            print(i)
            return
    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

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

def get_divisor(n):
    a,b = [],[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            a.append(i)
            b.append(n//i)
    if a[-1]==b[-1]:b.pop()
    a.extend(b[::-1])
    return a

div_list = get_divisor(sum(A))

for n in div_list[::-1]:
    d = [0]*N
    for i,a in enumerate(A):
        if a%n <= n//2:
            d[i] = -(a%n)
        else:
            d[i] = (-a)%n
    Sd = sum(d)
    if Sd != 0:
        d.sort()
        i = 0
        while Sd<0:
            d[i] += n
            Sd += n
            i+=1
        i = N-1
        while Sd>0:
            d[i] -= n
            Sd -= n
            i -=1
    check = sum(t for t in d if t>0)
    if check<=K:
        print(n)
        break

Submission status: Accepted

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

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

x=sum(A)
import math
xr=math.ceil(math.sqrt(x))

LIST=[]
for i in range(1,xr+1):
    if x%i==0:
        LIST.append(i)
        LIST.append(x//i)

ANS=1

for l in LIST:
    count=0

    B=[a%l for a in A]
    B.sort()

    i=0
    j=N-1

    for i in range(N):
        if B[i]%l==0:
            continue
        else:
            count_temp=B[i]
            count+=count_temp
            B[i]=0

            while count_temp:
                while B[j]%l==0:
                    j-=1
                MINUS=min(count_temp,l-B[j])
                B[j]+=MINUS
                count_temp-=MINUS

    if count<=K:
        ANS=max(ANS,l)

print(ANS)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def factors(n):
    L = []
    for i in range(1, n+1):
        if i * i > n:
            break
        if n % i == 0:
            L.append(i)
            if n // i != i:
                L.append(n // i)
    return L


def solve(N: int, K: int, A: "List[int]"):
    facts = factors(sum(A))
    facts.sort(reverse=True)
    for f in facts:
        B = sorted([a % f for a in A])
        d_m = []
        d_p = []
        for b in B:
            diff_minus = b
            diff_plus = f - diff_minus
            d_m.append(diff_minus)
            d_p.append(diff_plus)
        s_m = 0
        s_p = sum(d_p)
        for i in range(N):
            if s_m == s_p:
                break
            if s_m > s_p:
                print('okashii')
                break
            s_m += d_m[i]
            s_p -= d_p[i]
        if s_m <= K:
            print(f)
            return
            
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Accepted

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: Accepted

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

def chk(x):
    D = []
    c = 0
    for a in A:
        y = a % x
        D.append(y)
    D.sort()
    s = sum(D)
    e = 0; r = N*x - s
    for d in D:
        e += d
        r -= x - d
        if e == r and e <= K:
            return 1
    return 0

ans = 1
S = sum(A)
for x in range(1, int(S**.5)+1):
    if S % x == 0:
        if chk(x):
            ans = max(ans, x)
        if chk(S // x):
            ans = max(ans, S // x)
print(ans)

Submission status: Accepted

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:
        C=sorted(range(N),key=lambda i:abs(A[i]-B[i]),reverse=True)
        if nowsum>S:
            k=0
            need=(nowsum-S)//d
            for i in C:
                if B[i]>A[i]:
                    B[i]-=d
                    k+=1
                if k>=need:
                    break
        if nowsum<S:
            k=0
            need=(S-nowsum)//d
            for i in C:
                if B[i]<A[i]:
                    B[i]+=d
                    k+=1
                if k>=need:
                    break
    #print(d,A,B)
    cost=sum([abs(A[i]-B[i]) for i in range(N)])
    if cost<=2*K:
        ans=max(ans,d)
print(ans)