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:
# https://atcoder.jp/contests/abc136/submissions/6708242

def solve():
    n, k = map(int, input().split())
    a = tuple(sorted(map(int, input().split()), reverse=True))

    sum_a = sum(a)
    e = set()
    divisor = 1
    while divisor * divisor <= sum_a:
        if sum_a % divisor == 0:
            e.add(divisor)
            e.add(sum_a // divisor)
        divisor += 1

    e = sorted(e, reverse=True)
    # 約数降順

    for cand in e:
        r = tuple(sorted(x % cand for x in a if x % cand != 0))

        accm = [0]
        t = 0
        for x in r:
            t += x
            accm.append(t)

        accp = [0]
        t = 0
        for x in r:
            t += cand - x
            accp.append(t)

        m = len(r)
        for i in range(m + 1):
            if (accm[i] == (accp[m] - accp[i])) and (accm[i] <= k):
                return cand
    return -1


print(solve())

# 操作で総和は不変

Submission status: Accepted

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

asum=sum(a)


def 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()
    return divisors
div=divisor(asum)
#print(div)
b=[0]*n

ans=0
for d in div:
    count=0
    #print(d)
    #print(a)
    for i in range(n):
        b[i]=a[i]%d
    b.sort()
    #print(b)
    que=deque(b)
    #print(que)
    while que:
        s=que.popleft()
        if s==0:
            continue
        if len(que)==0:
            count=0
            break
        g=que.pop()
        #print(s,g)
        if s==d-g:
            count+=s
        if s<d-g:
            que.append(s+g)
            count+=s
        if s>d-g:
            que.appendleft(s-d+g)
            count+=(d-g)
    #print(d,count)
    if count<=k:
        ans=d
print(ans)

Submission status: Accepted

Solution code:
n,k=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
s=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()
    return divisors
l=make_divisors(s)
ans=1
from itertools import accumulate
for i in l[::-1]:
    ll=[]
    for j in a:
        ll.append(j%i)
    ll.sort()
    if sum(ll[:n-sum(ll)//i])<=k:
        print(i)
        exit()

Submission status: Accepted

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

def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(40000)

lis = []
for p in plis:
    if S%p == 0:
        lis.append([p,1])
        S = S//p
        while S%p == 0:
            lis[-1][1] += 1
            S = S//p
    if S == 1:
        break
if S != 1:
    lis.append([S,1])

yakulis =[1]
for l in lis:
    for j in range(len(yakulis)):
        for k in range(l[1]):
            n = yakulis[j]
            yakulis.append(l[0]**(k+1)*n)
yakulis.sort(reverse=True)

s = True
for r in yakulis:
    B = [i%r for i in A]
    B.sort()
    le = -1
    ri = N
    while ri-le > 1:
        mid = (le+ri)//2
        pl = sum(B[:mid+1])
        mi = r*(N-1-mid) - sum(B[mid+1:])
        if pl > mi:
            ri = mid
        else:
            le = mid
    k = sum(B[:le+1])
    if k <= K:
        s = False
        print(r)
        break
if s:
    print(1)

Submission status: Accepted

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

all_sum = sum(A)

# 答え（約数）の候補リスト
divisors = []

# 全整数を足した値の約数が答えの候補
for i in range(1,all_sum+1):
    if i * i > all_sum:
        break
    if all_sum % i != 0:
        continue
    divisors.append(i)
    if all_sum // i != i:
        divisors.append(all_sum // i)

# 大きい値から順番に探索
divisors.sort(reverse=True)

def ok(d):
    # 答えの候補dで全値を割った余り
    a = [x % d for x in A]
    
    # 値を大きくする対象の整数の数（dを基準として、それより大きい/小さいの数を求める）
    move = n - sum(a) // d
    a.sort()
    # dで割り切れる値まで変化させる（大きく/小さくする）対象の整数について、
    # 目標の値まで値を変化させる合計値が、k以内に収まるか？
    return sum(a[:move]) <= k

for d in divisors:
    if ok(d):
        print(d)
        break

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys

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

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

divisors = sorted(make_divisors(sum(al)), reverse=True)

for i in divisors:
    point = 0
    div_l = sorted([a%i for a in al if a%i > 0])
    while div_l:
        if div_l[0] < i - div_l[-1]:
            div_l[-1] += div_l[0]
            point += div_l[0]
            div_l.pop(0)
        else:
            div_l[0] -= (i - div_l[-1])
            point += i - div_l[-1]
            div_l.pop(-1)
            
    
    if point <= k:
        print(i)
        sys.exit()

Submission status: Accepted

Solution code:
from itertools import accumulate

def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

N, K, *A = map(int, open(0).read().split())

for d in reversed(divisors(sum(A))):
    R = [0] + list(accumulate(sorted(a % d for a in A)))
    for i in range(N):
        l = R[i]
        r = (N - i) * d - (R[N] - R[i])
        if max(l, r) <= K:
            print(d)
            quit()

Submission status: Accepted

Solution code:
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(p)
    check(b)
l.reverse()

for b in l:
    check(b)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    D=divisors(sum(A))
    def check(d):
        P=[]
        N=[]
        for i in range(n):
            r=A[i]%d
            if(not r): continue
            P.append(d-r)
        P.sort()
        l=len(P)
        N=[d-p for p in P]
        N.reverse()
        PS=[0]*(l+1)
        NS=[0]*(l+1)
        for i in range(l):
            PS[i+1]=PS[i]+P[i]
            NS[i+1]=NS[i]+N[i]
        NS.reverse()
        res=INF
        for i in range(l):
            res=min(res,max(PS[i],NS[i+1]))
        return res<=k
    ans=1
    for d in D:
        if(check(d)): ans=d
    print(ans)
resolve()

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

import heapq
#from collections import deque
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
#mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
A = LI()
cou = int(0)
sumA = sum(A)
anscandi = make_divisors(sumA)
#print(anscandi)

for i in anscandi:
    Smod = int(0)
    que = []
    for j in range(N):
        que.append((A[j] % i) *(-1))
        Smod += A[j] % i
    need = Smod//i
    heapq.heapify(que)
    for _ in range(need):
        heapq.heappop(que) * (-1)
    if K>=(sum(que)*(-1)):
        ans = i
        break


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

s=sum(A)
n=int(s**0.5)

#約数のリスト
cd=[]

for i in range(1,n+2):
	if s%i==0:
		cd.append(i)
		cd.append(s/i)

cd.sort(reverse=True)

def check(t):
	if t==1: return True
	A_temp=[]
	for x in A:
		A_temp.append(x%t)

	A_temp.sort()

	#Aの配列をmod tした配列A_tempの累積和
	A_temp_sum=[]

	for i,x in enumerate(A_temp):
		if i==0: A_temp_sum.append(x)
		else: A_temp_sum.append(A_temp_sum[-1]+x)

	#配列の前半は、数字をマイナスしていく
	p1=min(bisect_left(A_temp_sum,K),N-2)
	if A_temp_sum[p1]<=K:
		k1=A_temp_sum[p1]
	else:
		#配列の項数p1の値がKを超えている場合は、p1の1個手前の値をとる
		p1-=1
		k1=A_temp_sum[p1]


	#配列の後半で、数字をどれだけプラスする必要があるか
	k2=t*(N-p1-1)-(A_temp_sum[-1]-A_temp_sum[p1])

	#プラスする量が、マイナスする量より少なければ成立
	if k2<=k1:
		return True
	else:
		return False

for x in cd:
	if check(x):
		print x
		quit()

Submission status: Accepted

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue



# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def main():
    n, k = map(int, raw_input().split())
    da = map(int, raw_input().split())
    sm = sum(da)
    mx = max(da)
    ans = 1
    for i in range(1, int(math.sqrt(sm))+1):
        if sm%i==0:
            def check(p):
                l = []
                for num in da:
                    l.append(num%p)
                ssm = n*p - sum(l)
                l.sort()
                ps = 0
                uk = 0
                for num in l:
                    uk += num
                    ssm -= p-num
                    if ssm == uk and uk <= k:
                        return True
                return False
            # print check(7), 7777777
            if check(i):
                ans = max(ans, i)
            if check(sm/i):
                ans = max(ans, sm/i)

    print ans






main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(10**7)

show_flg=False
#show_flg=True
def devisors(x):
    rt=[1,x]
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            rt.append(i)
            if x//i!=i:rt.append(x//i)
    return rt
    
n,k=MI()
a=LI()
A=sum(a)
ds=devisors(A)
ans=1

for d in ds:
    r=[j%d for j in a]
    show(r,d)
    if sum(r)%d!=0:
        continue
    r.sort()
    ac=[0]
    for j in range(n):
        ac.append(ac[-1]+r[j])
    for j in range(1,n):
        if ac[j]==(n-j)*d-(ac[n]-ac[j]) and ac[j]<=k:
            ans=max(d,ans)
            show(j,d,ans)

print(ans)
show(ds)

Submission status: Accepted

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

a_sum = sum(a)

rt_sm = int(a_sum**(1/2) + 0.01)

fct = []
fct2 = []

for p in range(1,rt_sm+1):
    if a_sum%p == 0:
        fct.append(p)
        fct2.append(a_sum//p)

if fct[-1] == fct2[-1]:
    fct.pop() 

fct += fct2
fct.sort(reverse=True)


for f in fct:
    tmp = []
    for t in a:
        tmp.append(t%f)
    tmp_sum = sum(tmp)
    cnt = 0

    sb = tmp_sum // f
    tmp.sort()
    for i in range(n-sb,n):
        tmp[i] -= f

    if sum(tmp[:n-sb]) <= k:
        ans = f 
        break

print(ans)

Submission status: Accepted

Solution code:
import math

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

S = sum(As)
l = []
i = 1
ans = 1

while i*i <= S:
  if S % i == 0:
    l.append(i)
    l.append(S//i)
  i += 1

l.sort(reverse=True)

for i in l:
  ext = 0
  exts = []
  for j in As:
    exts.append(j % i)
    ext += (j % i)
  if ext % i != 0:
    continue
  else:
    p = 0
    exts.sort()
    cnt = ext//i
    for k in range(0, N - cnt):
      p += exts[k]
    if p <= K:
      ans = i
      break

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a_sum=sum(a)
def devisor(x):
    lst=[]
    i=1
    y=x
    while i**2<=y:
        if x%i==0:
            lst.append(i)
            if i!=x//i:
                lst.append(x//i)
        i+=1
    lst.sort()
    return lst
re=devisor(a_sum)
re.sort(reverse=True)
for u in re:
    w=[]
    for v in a:
        w.append(v%u)
    w.sort()
    b=sum(w)
    count=0
    for i in range(b//u):
        w[-i-1]-=u
    for i in w:
        if i>=0:
            count+=i
        else:
            break
    if count<=k:
        print(u)
        break

Submission status: Accepted

Solution code:
import itertools
import bisect
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in 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


divisors = make_divisors(sum(A))
for d in divisors:
    b = []
    for a in A:
        b += [a % d]
    b.sort()
    c = [0] + list(itertools.accumulate(b))
    il = bisect.bisect_left(c, K)
    if il >= len(c) or d * (len(c) - il - 1) - (c[-1] - c[il]) <= K:
        print(d)
        exit()

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

#初期化
N, K = getlist()
A = getlist()
S = sum(A)
n = int((S ** 0.5) // 1) + 1
gcd = []
for i in range(1, n):
	if S % i == 0:
		gcd.append(i)
x = len(gcd)
for i in range(x):
	gcd.append(S // gcd[i])
gcd = sorted(gcd)

#計算
ans = 1
for i in gcd:
	P = []
	for j in A:
		x = j % i
		if x != 0:
			P.append([x, i - x])
	P = sorted(P)
	a = 0
	b = 0
	for j in range(len(P)):
		a += P[j][0]
	s = 0
	for j in range(len(P)):
		a -= P[-1 - j][0]
		b += P[-1 - j][1]
		s += P[-1 - j][1]
		if a == b:
			break
	if s <= K:
		ans = i

print(ans)

Submission status: Accepted

Solution code:
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

def main():
    N, K, *A = map(int, open(0).read().split())

    for d in reversed(divisors(sum(A))):
        R = sorted(a % d for a in A)
        if sum(R[:-sum(R) // d]) <= K:
            print(d)
            quit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

N, K, *A = map(int, open(0).read().split())

for d in reversed(divisors(sum(A))):
    R = sorted(a % d for a in A)
    if sum(R[:-sum(R) // d]) <= K:
        print(d)
        quit()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

s = sum(a)
d = []
for i in range(1, int(s**0.5)+1):
    if s % i == 0:
        heappush(d, -i)
        if i != s // i:
            heappush(d, -(s // i))

while len(d) > 0:
    x = - heappop(d)
    r = list(map(lambda b:b%x, a))
    r.sort()
    L = -1
    for i in range(n):
        if r[i] != 0:
            L = i
            break
    if L == -1:
        if k % x == 0:
            print(x)
            exit()
        else:
            continue
    H = n - 1
    temp = r[L] - (x - r[H])
    count = r[L] + (x - r[H])
    L += 1
    H -= 1
    while L <= H:
        if temp <= 0:
            temp += r[L]
            count += r[L]
            L += 1
        else:
            temp -= x - r[H]
            count += x - r[H]
            H -= 1
        if count > 2 * k:
            break
    #print(x, count, temp, L, H)
    if count > 2 * k:
        continue
    if temp % (2 * x) == 0:
        print(x)
        exit()

print(1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
x = sum(A)
ls = []
for i in range(1, int(x**0.5)+1):
  if x%i==0:
    ls += [i]
    if i != x//i:
      ls += [x//i]
ls.sort(reverse=True)
for i in ls:
  B =[]
  for j in A:
    heappush(B, -1*(j%i))
  y = sum(B)
  while y<0:
    u = heappop(B)
    u += i
    heappush(B,u)
    y += i
  m = 0
  for j in B:
    if j>0:
      m += j
  if m>K:
    continue
  else:
    print(i)
    break

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
x = sum(A)
ls = []
for i in range(1, int(x**0.5)+1):
  if x%i==0:
    ls += [i]
    if i != x//i:
      ls += [x//i]
ls.sort(reverse=True)
for i in ls:
  B =[]
  for j in A:
    heappush(B, -1*(j%i))
  y = sum(B)
  while y<0:
    u = heappop(B)
    u += i
    heappush(B,u)
    y += i
  m = 0
  for j in B:
    if j>0:
      m += j
  if m>K:
    continue
  else:
    print(i)
    break

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n, k = LI()
L = LI()


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 gcd in make_divisors(sum(L)):
    remainder_l = sorted([i % gcd for i in L if i % gcd])
    remainder_u = [gcd - i for i in remainder_l]
    a = list(accumulate(remainder_l))
    b = list(reversed(list(accumulate(reversed(remainder_u)))))
    if not a:
        print(gcd)
        break
    ng = len(a) - 1
    ok = 0
    while ng > ok + 1:
        mid = (ok + ng) // 2
        if a[mid] > b[mid+1]:
            ng = mid
        elif a[mid] < b[mid+1]:
            ok = mid
        else:
            ok = mid
            break
    if a[ok] <= k:
        print(gcd)
        break

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def get_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            heappush(divisors, -i)
            if i != n // i:
                heappush(divisors, -(n // i))

    return divisors


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

    sum_A = sum(A)

    divisors = get_divisors(sum_A)
    n = len(divisors)
    for _ in range(n):
        h = -heappop(divisors)
        sub_list = []
        for a in A:
            sub_list.append(a % h)

        x = sum(sub_list)
        sub_list.sort()
        
        if sum(sub_list[:-x // h]) <= K:
            print(h)
            exit()

    print(0)


if __name__ == '__main__':
    p_e()

Submission status: Accepted

Solution code:
def divisors(n):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i**2 != n:
                div.append(n//i)
    div.sort()
    return div

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

d = divisors(sum(a))
d.reverse()

for x in d:
    b = []
    for i in range(n):
        b.append(x-a[i]%x)
    b.sort()
    c = sum(b)//x
    if sum(b[:-c]) <= k:
        print(x)
        exit()

Submission status: Accepted

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


A_sum = sum(A)
ans_candidates = []
for n in range(1, int(A_sum ** 0.5) + 1):
    if A_sum % n == 0:
        ans_candidates.append(n)
        ans_candidates.append(A_sum // n)
ans_candidates.sort(reverse=True)


for z in ans_candidates:
    need_add = [(z - a % z) % z for a in A]
    need_add.sort()
    need_minus = [z - na for na in need_add]

    need_add = list(accumulate(need_add))
    need_minus = list(accumulate(need_minus))

    for i in range(N):
        if (need_add[i] == need_minus[-1] - need_minus[i]) and (need_add[i] <= K):
            print(z)
            exit()

Submission status: Accepted

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

import math

Asum = sum(A)
candidates = []
for i in range(1, int(math.sqrt(Asum)) + 1):
    if Asum % i == 0:
        candidates.append(i)
        candidates.append(Asum // i)
candidates.sort()

# print("#", Asum)
# print("#", candidates)

ans = 1
for targ in candidates:
    if targ == 1: continue
    A_tmp = [(Ai % targ) for Ai in A]
    # A_tmp.sort(key=lambda x: min((x % targ), ((targ - x) % x)))
    A_tmp.sort()
    idx_l = 0
    idx_r = N - 1
    cnt = 0
    while sum(A_tmp) > 0 and idx_l < idx_r:
        cap_l = A_tmp[idx_l]
        cap_r = targ - A_tmp[idx_r]
        A_tmp[idx_l] = (A_tmp[idx_l] - min(cap_l, cap_r)) % targ
        A_tmp[idx_r] = (A_tmp[idx_r] + min(cap_l, cap_r)) % targ
        cnt += min(cap_l, cap_r)
        if A_tmp[idx_l] == 0:
            idx_l += 1
        if A_tmp[idx_r] == 0:
            idx_r -= 1
    #
    if cnt <= K and sum(A_tmp) == 0: ans = targ

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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


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

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

def f(d):
    Bs = [A%d for A in As]
    Bs.sort()
    sumB = sum(Bs)
    accBs = list(accumulate(Bs))
    for i in range(1, N):
        numSub = accBs[i-1]
        numAdd = d*(N-i) - (sumB-accBs[i-1])
        if numSub <= K and numAdd <= K and (numSub-numAdd)%d == 0:
            return True
    return False


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

Submission status: Accepted

Solution code:
N , K = map(int, input().split())
A = list(map(int, input().split()))
s = sum(A)
divisor = []
n = 1
while n ** 2 <= s:
    q, r = divmod(s, n)
    if r == 0:
        divisor.append(q)
        divisor.append(n)
    n += 1
ans = 1
for d in divisor:
    m = []
    for a in A:
        m.append(a % d)
    m.sort(reverse=True)
    l = sum(m) // d
    a = l * d - sum(m[:l])
    if a <= K:
        ans = max(ans, d)
print(ans)

Submission status: Accepted

Solution code:
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

n,k = map(int,input().split())
A = list(map(int,input().split()))
d_max= sum(A)
div = divisor(d_max)[::-1]

for ans in div:
    b = [a%ans for a in A]
    b.sort()
    s = sum(b)
    if sum(b[:-s//ans]) <=k:
        print(ans)
        exit()

Submission status: Accepted

Solution code:
import math
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    tot = sum(A)

    cand = helper(tot)
    for i in cand:
        rems = []
        for j in range(N):
            r = A[j] % i
            if r > 0:
                rems.append(r)
        rems.sort()

        tot = sum(rems)
        prefixneg = [0]
        for j in range(len(rems)):
            prefixneg.append(prefixneg[-1] + rems[j])

        for j in range(len(rems)+1):
            pos = (len(rems)-j)*i - (tot - prefixneg[j])
            neg = prefixneg[j]
            if max(pos, neg) <= K:
                return i

    return 1


def helper(n):
    div = set()
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            div.add(i)
            div.add(n//i)
    return sorted(list(div), reverse = True)

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

Submission status: Accepted

Solution code:
import math
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    tot = sum(A)

    cand = helper(tot)
    # print("here", cand)
    for i in cand:
        rems = []
        for j in range(N):
            r = A[j] % i
            if r > 0:
                rems.append(r)
        rems.sort()
        # print(rems)
        tot = sum(rems)
        prefixneg = [0]
        for j in range(len(rems)):
            prefixneg.append(prefixneg[-1] + rems[j])
        # print(prefixneg)
        for j in range(len(rems)+1):
            pos = (len(rems)-j)*i - (tot - prefixneg[j])
            neg = prefixneg[j]
            # print(i, pos, neg)
            if max(pos, neg) <= K:
                return i

    return 1


def helper(n):
    div = set()
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            div.add(i)
            div.add(n//i)
    return sorted(list(div), reverse = True)

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

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    total = sum(A)
    candidate = []
    
    for i in range(1, int(total**0.5)+1):
        if not total % i:
            candidate.extend([i, total//i])
    
    ans = 0
    
    for c in candidate:
        d = sorted([a % c for a in A])
        j = N - sum(d) // c
        
        if sum(d[:j]) <= K:
            ans = max(ans, c)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    N,K = map(int , input().split())
    A = list(map(int , input().split()))
    max_total = 22361 # sqrt(10**6 * 500)
    total = sum(A)
    search_space = set([])

    max_d = 1
    for d in range(1, min(total, max_total) ):
        if total % d == 0:
            search_space.add(d)
            search_space.add(total // d)
    
    # print(search_space)
    
    for d in search_space:
        if total % d == 0:
            remainders = [a%d for a in A]
            remainders = sorted(remainders)
            # print(d, remainders)
            positive_rem = 0
            negative_rem = 0
            flag = True
            for rem in remainders:
                if positive_rem+rem <= K:
                    positive_rem += rem
                elif negative_rem+(d-rem) <=K:
                    negative_rem += (d-rem)
                else: 
                    flag = False
                    break

            if flag and d > max_d:
                # print(d, remainders, positive_rem, negative_rem)
                max_d = d
            
    print(max_d)
    
solve()

Submission status: Accepted

Solution code:
#56 ABC136E
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a)

res=[]
for d in range(1,int(s**0.5)+1):
	if s%d==0:
		res.append(d)
		res.append(s//d)
ans=[]
for d in res:
	r1=[t%d for t in a]
	r1.sort()
	r2=[(d-t)%d for t in r1]
	r2=r2[::-1]
	x=[r1[0]]
	_=[x.append(x[-1]+r1[i]) for i in range(1,n)]
	y=[r2[0]]
	_=[y.append(y[-1]+r2[i]) for i in range(1,n)]
	#print(r1,r2,d,x,y)
	for i in range(n-1):
		#print(x[i],y[-i-2])
		if x[i]==y[-i-2] and x[i]<=k:
			ans.append(d)
			break
print(max(ans))