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:
# -*- coding: utf-8 -*-


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


if __name__ == '__main__':
    n, k = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))
    divisors = make_divisors(sum(A))
    for divisor in divisors:
        remainders = sorted(map(lambda x: x % divisor, A))
        idx = n - sum(remainders) // divisor
        ope_num = sum(remainders[:idx])
        if ope_num <= k:
            print(divisor)
            break

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
sun = sum(a)
cd = []
rcd = []
for i in range(1,int(sun**0.5)+1):
  if sun % i == 0:
    cd.append(i)
    rcd.append(sun//i)
rcd.reverse()
if cd[-1] == rcd[0]:
  del cd[-1]
gcd = cd + rcd
gcd.reverse()
count = 0
while True:
  g = gcd[count]
  b = list(map(lambda x: x%g, a))
  moon = sum(b) // g
  b.sort()
  luna = sum(b[:n-moon])
  if luna <= k:
    print(g)
    break
  count += 1

Submission status: Accepted

Solution code:
def yakusu(n):
    m = 1
    re = []
    while m ** 2 < n:
        a, md = divmod(n, m)
        if md == 0:
            re.append(m)
            re.append(a)
        m += 1
    if m ** 2 == n:
        re.append(m)
    return re

n, k = map(int, input().split())
aa = list(map(int, input().split()))
yk = yakusu(sum(aa))
yk.sort(reverse=True)
for y in yk:
    rs = [a % y for a in aa if a % y]
    if not rs:
        print(y)
        exit()
    if len(rs)==1:continue
    rs.sort()
    l = 0
    sl = rs[0]
    r = len(rs) - 1
    sr = y - rs[r]
    while 1:
        if l + 1 == r:
            if sl == sr and sl <= k:
                print(y)
                exit()
            else:
                break
        if sl > sr:
            r -= 1
            sr += y - rs[r]
            if sr > k: break
        else:
            l += 1
            sl += rs[l]
            if sl > k: break
print(1)

Submission status: Accepted

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

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

S = sum(A)
L = []
for s in range(1, S+1):
    if s > math.sqrt(S) + 1:
        break
    if S % s == 0:
        L.append(S//s)
        L.append(s)
L.sort(reverse = True)

for l in L:
    T = [a%l for a in A]
    T.sort()
    ans = False
    R = []
    r = 0
    for t in T:
        r += t
        R.append(r)
    #print(l, R)
    for i in range(N):
        #print(i, R[-1])
        if R[i] > K:
            break
        if R[N-1] == l*(N-i-1):
            ans = True
            break
        
    if ans:
        print(l)
        break

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
As  = list(map(int, input().split()))
# 約数
As = sorted(As)
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

divs = sorted(make_divisors(sum(As)),reverse=True)

from itertools import accumulate
for div in divs:
    # 足す側と引かれる側を分け
    # 小さい順にソートして、足し引きのプラマイが0になれば良い。
    # ただし、足す大きさ(=引く大きさ)がKを超えるといけない
    bs_plus = sorted([a%div for a in As])
    bs_minus = [(div-a)%div for a in bs_plus]
    acc_bs_p = list(accumulate(bs_plus))
    acc_bs_m = list(accumulate(bs_minus))
    for i in range(N):
        plus = acc_bs_p[i]
        minus = acc_bs_m[N-1]-acc_bs_m[i]
        if plus == minus and plus <= K:
            # print("ok",div,plus,minus)
            print(div)
            exit(0)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
D = []
i = 1
while i * i <= S:
    if S % i == 0:
        D.append(i)
        if S // i != i:
            D.append(S // i)
    i += 1

D = sorted(D, reverse=True)

for d in D:
    mod = [a % d for a in A]
    mod = sorted(mod)
    s = sum(mod)
    if sum(mod[:-s//d]) <= K:
        print(d)
        exit()

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())
xs = list(map(int,input().split()))
divs = divisible(sum(xs))

for div in divs :
    test = [x % div for x in xs]
    test.sort()
    sum_test = sum(test)
    change = sum(test[:-sum_test//div])
    if change <= K :
        ans = div
        break
print(ans)

Submission status: Accepted

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) : 
    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]
ans=1
for i in abc:
    l=0
    flag=0
    c=[]
    for j in arr:
        c.append(j%i)
    c.sort()
    if(sum(c[:-sum(c)/i])<=k):
        print i
        exit()

Submission status: Accepted

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

def main():
  n, k = map(int, input().split())
  alist = list(map(int, input().split()))
  suma = sum(alist)
  i = 1
  yaku = []
  while i*i<=suma:
    if suma % i == 0:
      yaku.append(i)
      if suma//i != i:
        yaku.append(suma//i)
    i += 1

  for d in sorted(yaku, key=lambda x: -x):
    rem = [a%d for a in alist]
    rem = list(sorted(rem))
    sumr = d*len(rem) - sum(rem)
    kc = 0
    for _r in rem:
      kc += _r
      sumr = sumr - (d-_r)
      if max(kc, sumr) <= k:
        print(d)
        sys.exit(0)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
s=sum(a)
b=[]
for i in range(1,30000):b+=[s//i,i]*(s%i<1)
m=1
for i in b:c=sorted(j%i for j in a);m=max(m,i*(sum(c[:-sum(c)//i])<=k))
print(m)

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
s=sum(l)
L=[]
for i in range(1,30000):L+=[i,s//i]*(s%i<1)
t=1
for d in L:a=sorted([m%d for m in l]);t=max(t,d*(sum(a[:-sum(a)//d])<=k))
print(t)

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
s=sum(l)
L=[]
for i in range(1,30000):L+=[i,s//i]*(s%i<1)
L.sort()
for d in L[::-1]:
 a=sorted([m%d for m in l])
 if sum(a[:n-sum(a)//d])<=k:print(d);exit()

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
s=sum(a)
b=[]
for i in range(1,int(s**.5)+1):b+=[s//i,i]*(s%i<1)
m=1
for i in b:c=sorted(j%i for j in a);m=max(m,i*(sum(c[:-sum(c)//i])<=k))
print(m)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
s,m=sum(a),1
for i in sum([[s//i,i]for i in range(1,int(s**.5)+1)if s%i<1],[]):
  p=[0]+sorted(j%i for j in a)
  for j in range(n):p[j+1]+=p[j]
  f=t=0
  for j in range(n):
    f|=t==p[~j]<=k
    t+=i-p[~j]+p[-j-2]
  m=max(m,i*f)
print(m)

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split());s=sum(l);L=[]
for i in range(1,int(s**0.5)+1):
  if s%i==0:L+=[i,s//i]
for d in sorted(L)[::-1]:
  a=sorted([m%d for m in l])
  if sum(a[:n-sum(a)//d])<=k:print(d);exit()

Submission status: Accepted

Solution code:
import sys
import math

def get_divisor(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

def main():
    _, K = map(int, input().split())
    *A, = map(int, input().split())

    aSum = sum(A)
    divs = get_divisor(aSum)

    for d in divs:
        r = [a % d for a in A]
        r.sort()

        sumRm = d*len(r) - sum(r)

        tmpSum = 0
        for _r in r:
            tmpSum += _r
            sumRm = sumRm - (d-_r)
            op = max(tmpSum, sumRm)
            if op <= K:
                print(d)
                sys.exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def dprint(*args):
  pass
# print(*args)

N, K = [int(x) for x in input().split()]
As = [int(x) for x in input().split()]
S = sum(As)
Ds = []
for i in range(1, 1+int(math.sqrt(S))):
  if S % i == 0:
    Ds.append(i)
    Ds.append(S//i)
Ds = sorted(set(Ds))

for d in Ds[::-1]:
  if d == 1:
    print(1)
    exit()
  dprint(d)
  rs = []  # Max 500 elements
  for a in As:
    rs.append(a % d)
  rs = sorted(rs)
  dprint(rs)
  total = sum(rs)
  n = total//d
  num = 0
  for i in range(N - n, N):
    rs[i] -= d
    num -= rs[i]
  dprint(rs)
  dprint(num)
  if num <= K:
    print(d)
    exit()
    
  
# 1 2 3 4/-3 -2 -1

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
s=sum(l);L=[]
for i in range(1,int(s**0.5)+1):
	if s%i==0:L+=[i,s//i]
L.sort()
for d in L[::-1]:
	a=sorted([m%d for m in l])
	if sum(a[:n-sum(a)//d])<=k:print(d);exit()

Submission status: Accepted

Solution code:
n,k,*l=map(int,open(0).read().split())
def f(n):
	d=[]
	for i in range(1,int(n**0.5)+1):
		if n%i== 0:
			d+=[i]
			if i!=n//i:
				d+=[n//i]
	d.sort()
	return d[::-1]
for d in f(sum(l)):
	a=sorted([m%d for m in l])
	if sum(a[:n-sum(a)//d])<=k:
		print(d);exit()

Submission status: Accepted

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

s = sum(A)
i = 1
q1 = []
q2 = []
while i * i <= s :
    if s % i == 0 :
        q1.append(i)
        if i * i != s :
            q2.append(s//i)
    i += 1
prime = q2 + q1[::-1]

def solve() :
    for p in prime :
        m = [a%p for a in A]
        m.sort()
        
        dpl = [0] * N
        dpr = [0] * N
        
        dpl[N-1] = p - m[N-1]
        dpr[0] = m[0]
        for i in range(N-2, -1, -1) :
            dpl[i] = dpl[i+1] + p - m[i]
        for i in range(1, N) :
            dpr[i] = dpr[i-1] + m[i]
        n = float('inf')
        for i in range(1, N) :
            n = min(n, max(dpl[i], dpr[i-1]))
        if n <= K :
            return p
            
print(solve())

Submission status: Accepted

Solution code:
from fractions import gcd
from copy import deepcopy as dc
N, K = map(int, input().split())
A = list(map(int, input().split()))
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
div = divisors(sum(A))
def check(g):
  Atemp = dc(A)
  for i in range(N):
    Atemp[i] %= g
  Atemp.sort()
  i = len(A) - sum(Atemp) // g
  #print(g, i, max(sum(Atemp[: i]), len(Atemp[i: ]) * g - sum(Atemp[i: ])))
  if max(sum(Atemp[: i]), len(Atemp[i: ]) * g - sum(Atemp[i: ])) <= K:
    return True
  else:
    return False

res = 1
for d in div:
  if check(d) == True:
    res = d
print(res)

Submission status: Accepted

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

S = sum(A)

def divisor(n):
    res = []
    rn = int(n**0.5) + 1 
    for i in range(1, rn):
        if n % i == 0:
            res.append(i)
            if i != n / i:
                res.append(int(n / i))
    return sorted(res)

Y = divisor(S)

ans = 1
for i in range(len(Y)-1, 0, -1):
    cnt = []
    for j in range(N):
        cnt.append(A[j] % Y[i])

    cnt = sorted(cnt)

    cnt_s = [0]
    tmp = 0
    for j in range(N):
        tmp += cnt[j]
        cnt_s.append(tmp)
    minc = 10**10
    for j in range(N+1):
        M = cnt_s[j]
        P = (N-j)*Y[i] - (cnt_s[N]-cnt_s[j])
        minc = min(max(M,P),minc)
    if minc <= K:
        ans = Y[i]
        break

print(ans)

Submission status: Accepted

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in yakusu(sum(A)):
    M = sorted(map(lambda x: [x % i, (i-x % i)%i], A), key=lambda x: x[0])
    s = sum(map(lambda x: x[1], M))
    sm = 0
    for j, (m, m2) in enumerate(M):
        sm += m
        s -= m2
        if sm == s and s <=K:
            ans = max(ans, i)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x):
  l = []
  for i in range(N):
    l.append(a[i]%x)
  l.sort()

  aa = 0
  bb = 0
  for i in l:
    tmp = i
    if aa + tmp > K:
      bb += x-tmp
      if bb > K:
        return False
    else:
      aa += tmp
  else:
    return True

N,K = IL()
a = IL()
num = sum(a)
ans = []

for i in range(1,int(math.sqrt(num)+1)):
  if num%i == 0:
    if judge(i):
      ans.append(i)
    if judge(num//i):
      ans.append(num//i)

print(max(ans))

Submission status: Accepted

Solution code:
inf = float('inf')

from math import floor
# 約数全列挙(ソート済み)
# n = 24 -> [1,2,3,4,6,8,12,24]
def divisor(n):
    left = [1]
    right = [n]
    sup = floor(pow(n,1/2))
    for p in range(2,sup+1):
        if n % p == 0:
            if p == n//p:
                left.append(p)
                continue
            left.append(p)
            right.append(n//p)
    res = left + right[::-1]
    return res

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r] - cs[l]

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

S = sum(A)
for d in divisor(S)[::-1]:
    nA = sorted([a % d for a in A])
    accmulate(nA)
    cnt = inf
    for i in range(N+1):
        minus = -query(0,i)
        plus = d*(N-i) - query(i,N)
        if minus + plus == 0:
            cnt = min(cnt, plus)
    if cnt <= K:
        print(d)
        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(reverse=True)
    return divisors

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

for d in make_divisors(sum(A)):
  if d==1:
    print(d)
    exit()
  A_ = [a%d for a in A if a%d]
  if max(A_)+K < d:
    continue  
  A_.sort()
  lSum, rSum = 0, 0
  K_need = 1e9
  for a in A_:
    rSum += d - a
  for a in A_:
    lSum += a
    rSum -= d - a
    K_need = min(K_need, max(lSum,rSum))
  if K_need <= K:
    print(d)
    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)
    return divisors


def main():
    n, k = map(int, input().split())
    *a, = map(int, input().split())

    asum = sum(a)
    divs = make_divisors(asum)
    ans = 1
    for d in divs:
        r = sorted([aa % d for aa in a])
        j = n - 1 - sum(r) // d
        if sum(r[:j+1]) <= k:
            ans = max(ans, d)
    print(ans)


main()

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

sum_A = sum(A)
d_candidate = make_divisors(sum_A)

for d in d_candidate:
    R = [a % d for a in A]
    R.sort()
    sum_R = sum(R)

    X, mod = divmod(sum_R, d)
    if mod != 0:
        continue

    if sum(R[:N-X]) <= K and (X * d - sum(R[-X:])) <= K:
        print(d)
        break

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
ans = 1
C = []
for i in range(1,int(S**0.5+1)):
    if S%i == 0:
        C.append(i)
        C.append(S//i)
for c in C:
    B = []
    for i in A:
        B.append(i%c)
    B.sort()
    hoge = 0
    sum_b = sum(B)
    for i in range(N):
        hoge += B[i]
        sum_b -= B[i]
        if hoge <= K and hoge == c*(N-i-1)-sum_b:
            ans = max(ans,c)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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


# candidates of the GCD
total = sum(A)
divisor = []
divisor2 = []
for i in range(1, int(total ** 0.5) + 1):
    if total % i == 0:
        divisor.append(i)
        divisor2.append(total // i)
    if total ** 0.5 == int(total ** 0.5):
        divisor.append(int(total ** 0.5))
divisor2.reverse()
divisor += divisor2

while divisor:
    d = divisor.pop()
    remainder = []
    for i in range(N):
        if A[i] % d != 0:
            remainder.append(A[i] % d)
    remainder.sort()
    remainder = deque(remainder)

    times = 0
    while remainder:
        pre = remainder.popleft()
        times += pre
        remainder[-1] += pre

        while remainder != deque([]) and remainder[-1] >= d:
            post = remainder.pop()
            if remainder != deque([]):
                remainder[-1] += post - d
            else:
                continue
    
    if times <= K:
        print(d)
        exit()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


def get_fact(N):
  ret = set([N])
  for i in range(2,int(N**0.5)+2):
    if N%i == 0:
      ret.add(i)
      ret.add(N//i)
  return ret


def main():
  ## input
  N,K = map(int, input().split())
  An = list(map(int, input().split()))

  ## Solve
  fset = get_fact(sum(An))
  ans = 1
  for f in fset:
    Amod = [a%f for a in An]
    Amod = sorted(Amod)
    for i in range(len(Amod)):
      if sum(Amod[:i])==f*(N-i)-sum(Amod[i:]) and sum(Amod[:i])<=K:
        ans = max(ans,f)
  return ans


if __name__ == "__main__":
  ans = main()
  print(ans)

Submission status: Accepted

Solution code:
n, k =  map(int,input().split())
a_list = list(map(int,input().split()))
total = sum(a_list)

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

div_list = make_divisors(total)
for div in div_list:
    b_list = [a%div for a in a_list]
    b_list.sort()
    change = sum(b_list[:(-sum(b_list)//div)])
    if change <=k:
        print(div)
        break

Submission status: Accepted

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

sum_A = sum(A)
max_A = max(A)

def make_divisor(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

div_list = make_divisor(sum_A)
div_list.sort(reverse=True)

for d in div_list:
    R = [a % d for a in A]

    sum_r = sum(R)
    if sum_r % d != 0:
        continue

    R.sort()
    #print("%d: %s" % (d, R))
    flag = False 

    sub = 0
    flag = True
    for i in range(N):
        if flag and sub + R[i] > K:
            flag = False
            #print("%d, i: %d" % (d, i))

        if flag:
            sub += R[i]
        else:
            sub -= (d - R[i])

    #print("%d, sub: %d" % (d, sub))

    if not flag and sub < 0:
        continue

    print(d)
    exit()

Submission status: Accepted

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 divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


@mt
def slv(N, K, A):
    S = sum(A)
    D = [n for n in divisor(S)]
    D.sort()

    ans = 0
    for d in D:
        r = []
        for a in A:
            r.append(a % d)
        r.sort()
        rr = [d - n for n in r]
        sr = [0]
        srr = [0]
        for i in range(N):
            sr.append(sr[-1] + r[i])
            srr.append(srr[-1] + rr[i])
        
        for i in range(N):
            e = sr[i+1] - sr[0]
            f = srr[N]-srr[i+1]
            if e == f and e <= K:
                ans = max(ans, d)
                break
    return ans



def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    from math import sqrt, ceil
    N,K = LMIIS()
    A = LMIIS()
    suma = sum(A)
    dL = [0] * N
    dU = [0] * N
    ds = []
    for x in range(1,ceil(sqrt(suma))+1):
        
        if suma % x != 0:
            continue

        d = suma // x 
        ds.append(x)
        for i in range(N):
            dL[i] = A[i] % d
        dL.sort()
        for i in range(N):
            dU[i] = d - dL[i]

        c = 0
        l = 0
        r = N-1
        while l < r:
            #print(l,r)
            if dL[l] == dU[r]:
                c += dL[l]
                if c > K:
                    break
                l += 1
                r -= 1
                if l >= N or r < 0:
                    break
            elif dL[l] < dU[r]:
                c += dL[l]
                if c > K:
                    break
                dU[r] -= dL[l]
                l += 1
                if l >= N:
                    break
            else:
                c += dU[r]
                if c > K:
                    break
                dL[l] -= dU[r]
                r -= 1
                if r < 0:
                    break
            
            
        if l >= r:
            print(d)
            return

    for i  in range(len(ds)-1,-1,-1):
        d = ds[i]
        for i in range(N):
            dL[i] = A[i] % d
        dL.sort()
        for i in range(N):
            dU[i] = d - dL[i]

        c = 0
        l = 0
        r = N-1
        while l < r:
            #print(l,r)
            if dL[l] == dU[r]:
                c += dL[l]
                if c > K:
                    break
                l += 1
                r -= 1
                if l >= N or r < 0:
                    break
            elif dL[l] < dU[r]:
                c += dL[l]
                if c > K:
                    break
                dU[r] -= dL[l]
                l += 1
                if l >= N:
                    break
            else:
                c += dU[r]
                if c > K:
                    break
                dL[l] -= dU[r]
                r -= 1
                if r < 0:
                    break
            
            
        if l >= r:
            print(d)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

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

for i in make_divisors(sum(A)):
	# print(i)
	r = sorted([x%i for x in A if x%i != 0])
	# print(r)
	if r == []:
		print(i)
		break
	acc = list(accumulate(r))
	for j in range(len(r)-1):  # しきり
		down = acc[j]
		up = i*(len(r)-j-1)-(acc[-1]-acc[j])
		if abs(up-down)%i != 0:
			continue
		else:
			if max(up, down) <= K:
				print(i)
				sys.exit(0)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
As = list(map(int, input().split()))
As.sort()
S = sum(As)
#print(S)
ds = []
for d in range(1, 30000):
  if S%d == 0:
    ds.append(d)
    ds.append(S//d)
ds.sort()
#print(ds)
for d in reversed(ds):
  Rs = [a%d for a in As]
  Rs.sort()
  s = sum(Rs)
  count = s//d
  r = 0
  for i in range(N-count):
    r += Rs[i]
  if r <= K:
    print(d)
    exit()

Submission status: Accepted

Solution code:
import math
from itertools import accumulate
a,b=map(int,input().split())
c=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
d=make_divisors(sum(c))


m=1
for i in d:
  e=[]
  for j in range(a):
    e.append(c[j]%i)
  e.sort()
  acc_m = list(accumulate(e))
  e=[i-e[j] for j in range(a)]
  acc_p = list(accumulate(e))
  for j in range(a):
    k=acc_m[j]
    l=acc_p[-1]-acc_p[j]
    if k==l and k+l<=b*2:
      print(i)
      exit()

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    S = sum(A)
    divs = set()
    for d in range(1, int(S**(0.5) + 1)):
        if S % d != 0:
            continue
        divs.add(d)
        divs.add(S // d)

    ans = 0
    cost = 0
    for d in divs:
        mods = []
        for a in A:
            mods.append(a % d)
        mods.sort()
        total = sum(mods)
        sub = 0
        for i, m in enumerate(mods, start=1):
            sub += m
            add = d*(N-i) - (total - sub)
            if add == sub:
                cost = sub
                break     
        if cost <= K:
            ans = max(ans, d)

    return ans


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

Submission status: Accepted

Solution code:
import fractions
import math
import sys

fastinput = sys.stdin.readline
gcd = fractions.gcd
N,K=map(int,fastinput().split())
A = [int(i) for i in fastinput().split()]
S = sum(A)
yakusu = []
for i in range(1,math.floor(math.sqrt(S))+1):
    if not S%i:
        yakusu.append(i)
        yakusu.append(S//i)

yakusu.sort(reverse = True)
for kouho in yakusu:
    amaris =[a%kouho for a in A]
    amaris.sort()
    amarisum= sum(amaris)
    y=amarisum // kouho
    if y==0:
        print(kouho)
        break
    else:
        yakuwa = 0
        for i in range(N-y):
            yakuwa += amaris[i]
        if yakuwa <= K:
            print(kouho)
            break

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
x = [1, S]
for i in range(2, int(S**0.5)+1):
    if S % i == 0:
        x.append(i)
        x.append(S//i)
x.sort(reverse = 1)
for g in x:
    B = [a%g for a in A]
    B.sort()
    S1 = sum(B)
    S2 = 0
    for i in range(N)[::-1]:
        S1 -= B[i]
        S2 += g-B[i]
        if (S1-S2)%g == 0:
            if S2 < S1 and S1 <= K:
                print(g)
                exit()
            elif S1 <= S2 and S2 <= K:
                print(g)
                exit()