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:
import sys
input=sys.stdin.readline

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

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

S=sum(A)
lst=make_divisors(S)

ans=1
B=[0]*N
for u in lst:
    for i in range(N):
        B[i]=A[i]%u
    B.sort()
    kkk=0
    s=0
    while kkk<N and s+B[kkk]<=K:
        s+=B[kkk]
        kkk+=1
    t=0
    for i in range(kkk,N):
        t+=u-B[i]
    if s>=t:
        ans=u

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
import math
from collections import defaultdict, Counter

def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d
MOD = 10**9 + 7
INF = 10**10

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

    return divisors

def judge(anums, cand, k):
    anums = sorted([num % cand for num in anums])
    rem = sum([(cand - num) for num in anums])
    acc = [0]
    tmp = 0
    ue = 0
    # print(rem, anums)
    for num in anums:
        tmp += num
        acc.append(tmp)

    if acc[rem // cand] <= k:
        return True
    else:
        return False


def main():
    n,k = getlist()
    anums = getlist()

    candidates = make_divisors(sum(anums))
    # print(candidates)
    for cand in sorted(candidates, key=lambda x: -x):
        res = judge(anums, cand, k)
        if res:
            print(cand)
            return





if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(c) for c in input().split()]
S = sum(A)
pls = []
for i in range(1,S):
  if i*i>S:
    break
  if S%i==0:
    pls += [i]
    pls += [S//i]
pls.sort(reverse=True)
for p in pls:
    B = []
    for i in range(N):
      B += [A[i]%p]
    B.sort()
    for j in range(N):
      if B[j]!=0:
        break
    m = j
    lim = N-1
    cnt = 0
    while m<lim:
      if B[m]<p-B[-1]:
        B[-1] += B[m]
        cnt += B[m]
        B[m] = 0
        m += 1
      elif B[m]>p-B[-1]:
        cnt += p-B[-1]
        B[m] -= p-B[-1]
        B.pop()
        lim -= 1
      else:
        B.pop()
        cnt += B[m]
        B[m] = 0
        m += 1
        lim -= 1
    if B[-1]==0 and cnt<=K:
      print(p)
      break

Submission status: Accepted

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

divs = []
maxA = sum(A)
for i in range(1, int(maxA ** 0.5) + 1):
    if maxA % i == 0:
        divs.append(i)
        divs.append(maxA // i)

divs.sort(reverse=True)

for d in divs:
    rest = [a % d for a in A]
    rest.sort(reverse=True)
    restSum = sum(rest) // d
    cnt = 0
    for i in range(restSum):
        cnt += d - rest[i]
    if cnt <= K:
        print(d)
        exit()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


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

divs = []
maxA = sum(A)
for i in range(1, int(maxA ** 0.5) + 1):
    if maxA % i == 0:
        heappush(divs, -i)
        j = maxA // i
        if i != j:
            heappush(divs, -j)

while True:
    d = -heappop(divs)
    q = []
    asum = 0
    for a in A:
        rest = a % d
        asum += rest
        heappush(q, -rest)
    cnt = 0
    for i in range(asum // d):
        cnt += d - (-heappop(q))
    if cnt <= K:
        print(d)
        exit()

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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    div = sorted(divisor(sum(A)), reverse=True)
    ans = 0
    for d in div:
        mod = [0] * N
        for i in range(N):
            mod[i] = A[i] % d
        sort_mod = sorted(mod)
        cnt = float('inf')
        rsum = d * N - sum(sort_mod)
        lsum = 0
        for j in range(N):
            lsum += sort_mod[j]
            rsum -= d - sort_mod[j]
            tmp = max(lsum, rsum)
            cnt = min(cnt, tmp)
        if cnt <= K:
            print(d)
            exit()

    


if __name__ == "__main__":
    main()

Submission status: Accepted

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


ans_candidates = []
for n in range(1, int(M ** 0.5) + 1):
    if M % n == 0:
        ans_candidates.append(n)
        ans_candidates.append(M // n)


ans = 0
for X in ans_candidates:
    alpha = sorted([(a % X) for a in A])
    beta = [X - a for a in alpha]

    alpha = list(accumulate(alpha))
    beta = list(accumulate(beta))

    for i in range(N):
        if alpha[i] > K:
            break

        if alpha[i] == (beta[-1] - beta[i]):
            ans = max(ans, X)
            break

print(ans)

Submission status: Accepted

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

def divisors(n) -> list:
  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)
  res = sorted(res)[::-1]
  return res

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

div = divisors(sum(A))

for d in div:
  arr = []
  for a in A:
    if a % d != 0:
      arr.append(d - a % d)
    else:
      arr.append(0)
  arr = sorted(arr)[::-1]
  tmp = sum(arr[sum(arr) // d:])
  if tmp <= K:
    print(d)
    exit()

Submission status: Accepted

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


ans_candidates = []
for n in range(1, int(M ** 0.5) + 1):
    if M % n == 0:
        ans_candidates.append(n)
        ans_candidates.append(M // n)


ans = 0
for X in ans_candidates:
    need_plus = sorted([(X - a % X) % X for a in A])
    need_minus = [X - nm for nm in need_plus]

    need_plus = list(accumulate(need_plus))
    need_minus = list(accumulate(need_minus))

    for i in range(N):
        if need_plus[i] > K:
            break

        if need_plus[i] == (need_minus[-1] - need_minus[i]):
            ans = max(ans, X)
            break

print(ans)

Submission status: Accepted

Solution code:
#ある数gを用意して，最も近いgの倍数にするための手数を数える，プラマイの総和が0にならない限り，最も変更に要する手数が大きいところは逆転させる？
#gはAの総和の約数

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

div=make_divisors(sum(A))

ans=0
for g in div:
    near=[0]*N
    S=0
    for i in range(N):
        near[i]=a=A[i]%g
        S+=near[i]
    near.sort()
    ii=0
    while S!=0:
        S-=g
        ii-=1
    temp=sum(near[:ii])
    if temp<=K:
        ans=max(ans,g)
        
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = LI()
    s = sum(a)
    dv = set([1,s])
    for i in range(2,int(s**0.5)+5):
        if s%i == 0:
            dv.add(i)
            dv.add(s//i)

    def f(i):
        pm = []
        for c in a:
            t = c % i
            if t == 0:
                continue
            pm.append((i-t, t))
        pm.sort()
        p = pi = m = 0
        mi = len(pm) - 1
        while pi <= mi:
            if p < m:
                p += pm[pi][0]
                pi += 1
            else:
                m += pm[mi][1]
                mi -= 1
        return max(p,m) <= k

    r = 1
    for c in dv:
        if f(c):
            if r < c:
                r = c

    return r


print(main())

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    sA = sum(A)
    divs = []
    i = 1
    while i * i < sA:
        if sA % i == 0:
            divs.append(i)
            divs.append(sA // i)
        i += 1
    if i * i == sA:
        divs.append(i)
    divs.sort()
    for d in reversed(divs):
        t = [i % d for i in A]
        t.sort()
        k = sum(t[:-sum(t) // d])
        if k <= K:
            return d

print(main())

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# 約数列挙
def find_divisor(n):
    divisors=[]
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n // i)
    return divisors


def main():
    N,M = MI()
    A = LI()
    S = sum(A)
    pri = find_divisor(S)
    ans = 0
    for p in pri:
        
        B = [a%p for a in A]
        B.sort()
        B_rev = [b-p if b else 0 for b in B ]
        *cumsum, = accumulate(B)
        cumsum_rev = [0]*(N+1)
        now = 0
        for i in range(N)[::-1]:
            now += B_rev[i]
            cumsum_rev[i] = now
        
        for i in range(N):
            if (cumsum[i] + cumsum_rev[i+1]) % p == 0:
                c = max(cumsum[i], -cumsum_rev[i+1])
                if c<=M:
                    ans = max(ans, p)
    print(ans)
if __name__ == '__main__':
    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)

    return  divisors

sum_a = sum(a)
divisors = sorted(make_divisors(sum_a), reverse=True)

for div in divisors:
    if(sum_a % div != 0):
        continue

    mod_a = []
    for ai in a:
        mod_a.append(ai % div)
    mod_a = sorted(mod_a)

    sum_mod_a = sum(mod_a)
    k_min = sum(mod_a[: (n-sum_mod_a//div) ])

    if(k_min <= k):
        print(div)
        exit()

# 絶対1で割り切れるからここにはこないけど。。。
print(-1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
max_div = int(S**0.5)

# Sの約数を列挙する
small_div = []
large_div = []
for i in range(1, max_div+1):
  if S%i == 0:
    small_div.append(i)
    large_div.append(S//i)

# 約数を降順に並べる
div = large_div + small_div[::-1]

ans = 1
for d in div:
  r = []
  for a in A:
    r.append(a%d)
  
  r.sort()
  # (d-ri)足すか、ri引くか、それぞれ累積和を求めておく
  minus = [0]*(N+1)
  plus = [0]*(N+1)
  for i, ri in enumerate(r, 1):
    minus[i] = minus[i-1] + ri
  
  for i, ri in enumerate(r[::-1], 1):
    plus[i] = plus[i-1] + (d - ri)
  
  plus = plus[::-1]
  for m, p in zip(minus, plus):
    if m == p and m <= K:
      ans = d
      break
  
  else:
    continue
  
  break

print(ans)

Submission status: Accepted

Solution code:
import sys,math
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def divisorlist(z):
    if len(z)==1:
        return [z[0][0]**i for i in range(z[0][1]+1)]
    y = divisorlist(z[1:])
    s = []
    for i in range(z[0][1]+1):
        for j in y:
            s.append((z[0][0]**i)*j)
    return s

n,k = inm()
a = inl()
sm = sum(a)
zz = prime_division(sm)
z = divisorlist(zz)
z.sort(reverse=True)
ddprint(z)
for p in z:
    if p>sm+k:
        continue
    b = [ai%p for ai in a]
    b.sort()
    s = sum(b)
    m = s//p
    t = sum(b[:n-m])
    ddprint("p {} b {} s {} m {} t {}".format(p,b,s,m,t))
    if t<=k:
        print(p)
        exit()

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 = map(int,input().split())
A = list(map(int,input().split()))
for d in reversed(divisors(sum(A))):
    R = sorted(a % d for a in A)
    # print(d,R,-sum(R) // d,sum(R[:-sum(R) // d]))
    if sum(R[:-sum(R) // d]) <= K:
        print(d)
        quit()

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,K=LI()
AS=LI()
SUMM= sum(AS)

DIVS=set()
for i in range(1,40000):
    if SUMM % i == 0:
        DIVS.add(i)
        DIVS.add(SUMM//i)
# print(DIVS)

DIFF=[0]*N

res = 0
for div in DIVS:
    for i in range(N):
        DIFF[i] = AS[i]%div
    DIFF.sort()
    i = 0
    j = N-1
    sm = 0
    cost = 0
    while i <= j:
        if sm + DIFF[j] >= div:
            sm -= (div - DIFF[j])
            j -= 1
        else:
            cost += DIFF[i]
            sm += DIFF[i]
            i += 1
    # print("div:{} sum: {} cost: {}".format(div, sm, cost))
    if cost <= K: res = max(res, div)

# print(DIFF)
print(res)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,K=LI()
AS=LI()
SUMM= sum(AS)

DIVS=set()
for i in range(1,40000):
    if SUMM % i == 0:
        DIVS.add(i)
        DIVS.add(SUMM//i)
# DIVS.sort(reversed=True)
# print(DIVS)

DIFF=[0]*N
ACC=[0]*N

# res = 0

for div in sorted(DIVS, reverse=True):
    for i in range(N):
        DIFF[i] = AS[i]%div
    DIFF.sort()
    ACC[0] = DIFF[0]
    for i in range(1,N): ACC[i] = ACC[i-1] + DIFF[i]
    # print(ACC)
    for i in range(N-1):
        left = ACC[i]
        right = (N-1-i)*div-(ACC[N-1]-ACC[i])
        if left%div == right%div:
            if max(left, right) <= K:
                # print(max(left, right))
                print(div)
                exit()


# print(DIFF)
# print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
suma = sum(a)
devisor = []
for i in range(1,int(suma**0.5)+1):
  if suma%i == 0:
    devisor.extend((i,suma//i))
devisor.sort(reverse=True)
for x in devisor:
  b = [a[i]%x for i in range(n)]
  b.sort()
  sumb = list(accumulate(b))
  for y in range(n-1):
    bf = sumb[y]
    bl = sumb[n-1]-sumb[y]
    if bf%x == (x-(bl%x))%x:
      if k>=max(bf,(n-1-y)*x-bl):
        print(x)
        exit()
      else:
        continue

Submission status: Accepted

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

sumA = sum(A)

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

div = make_divisors(sumA)
#print(div)

for d in div:
  tmp = []
  for a in A:
    tmp.append(a % d)
  tmp.sort()
  tmp = tmp[::-1]
  sum_tmp = sum(tmp)
  
  if sum(tmp[sum_tmp // d:]) <= K:
    print(d)
    exit()

Submission status: Accepted

Solution code:
def get_divisor(num, max_val):
    ret = []
    num_sq = int(num**0.5)
    for k in range(1, num_sq+1):
        if num % k == 0:
            if k <= max_val: ret.append(k)
            if num//k <= max_val: ret.append(num//k)
            
    return ret

# 下からmodが低いのを取ってきてマッチングを取る
def solve():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    sum_A = sum(A)
    max_A = max(A)
    div = get_divisor(sum_A, max_A+K)
    ret = 1
    for d in div:
        sum_k = 0
        red_k = 0
        flag = True
        mod_d = [a%d for a in A]
        mod_d.sort()
        # print(d, mod_d)
        for a in mod_d:
            if sum_k+a <= K:
                sum_k += a
            else: 
                red_k += d-a
            if sum_k-red_k < 0:
                break

        if (sum_k-red_k)%d == 0: ret = max(ret, d)
            
    print(ret)
    
solve()

Submission status: Accepted

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

divisors = []
for i in range(1,int(s**0.5)+1):
    if s%i==0:
        divisors.append(i)
        divisors.append(s//i)
divisors = list(set(divisors))
divisors.sort(reverse=True)

def possible(n):
    a = []
    for i in range(N):
        if A[i]%n != 0:
            a.append(A[i]%n)
    a.sort()
    k = 0
    while k <= K and a:
        m = a[0]
        M = a[-1]
        if m <= n-M:
            k += m
            a[-1] = (M+m)%n
            a[0] = 0
        else:
            k += n-M
            a[0] = (m-n+M)%n
            a[-1] = 0
        if a[0]==0:
            a = a[1:]
        if a[-1]==0:
            a = a[:-1]
        a.sort()
    return k<=K

for n in divisors:
    if possible(n):
        ans = n
        break

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
num=sum(A)
L=[]
cnt=0
for i in range(2,10**5+1):
    while num%i==0:
        num//=i
        cnt+=1
    if cnt>0:
        L.append([i,cnt])
        cnt=0
if num>1:
    L.append([num,1])
#print(L)
import copy
L1=[1]
L2=[]
for i in range(len(L)):
    for j in range(len(L1)):
        for k in range(L[i][1]+1):
            L2.append(L1[j]*L[i][0]**k)
    L1=copy.deepcopy(L2)
    L2=[]
L1.sort(reverse=True)
#print(L1)

for i in range(len(L1)):
    C=[]
    for j in range(N):
        C.append(A[j]%L1[i])
    C.sort(reverse=True)
    D=sum(C)
    E=0
    cnt=0
    for k in range(len(C)):
        if D==E:
            break
        else:
            D-=(C[k])
            E+=(L1[i]-C[k])
    if E<=K:
        print(L1[i])
        exit()
    #print(D,E,L1[i],C)

Submission status: Accepted

Solution code:
import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    np.cumsum(mods, out=mods)
    idx = mods[n-1] // div
    count = mods[-1-idx]
    if count <= k:
        print(div)
        exit()

Submission status: Accepted

Solution code:
import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    subcum = np.cumsum(mods)
    idx = subcum[n-1] // div
    count = subcum[-1-idx]
    if count <= k:
        print(div)
        exit()

Submission status: Accepted

Solution code:
import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    add = div - mods

    addcum = np.cumsum(add)
    subcum = np.cumsum(mods)
    for i in range(n):
        addcount = addcum[n-1] - addcum[i]
        subcount = subcum[i]
        if addcount == subcount and addcount <= k:
            print(div)
            exit()

Submission status: Accepted

Solution code:
import numpy as np


# 約数の列挙
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(list(divisors))


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

A = np.array(A, np.int64)
d = make_divisors(A.sum())

for i in d[::-1]:
    r = A % i
    r = r[r.nonzero()]
    l = r.size
    if l == 0:
        print(i)
        exit()
    else:
        n = np.arange(l - 1, 0, -1)
    r.sort()
    np.cumsum(r, out=r)
    if np.any((r[:-1] == i * n - (r[-1] - r[:-1])) & (r[:-1] <= K)):
        print(i)
        exit()

Submission status: Accepted

Solution code:
import numpy as np


# 約数の列挙
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(list(divisors))


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

A = np.array(A, np.int64)
d = make_divisors(A.sum())

for i in d[::-1]:
    r = A % i
    r = r[r != 0]
    l = r.size
    if l == 0:
        print(i)
        exit()
    else:
        n = np.arange(l - 1, 0, -1)
    r.sort()
    np.cumsum(r, out=r)
    if np.any((r[:-1] == i * n - (r[-1] - r[:-1])) & (r[:-1] <= K)):
        print(i)
        exit()

Submission status: Accepted

Solution code:
import numpy as np


# 約数の列挙
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(list(divisors))


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

A = np.array(A, np.int64)
d = make_divisors(A.sum())

for i in d[::-1]:
    r = A % i
    r = r[r != 0]
    l = r.size
    if l == 0:
        print(i)
        exit()
    else:
        n = np.arange(l - 1, 0, -1)
    r.sort()
    np.cumsum(r, out=r)
    equal = np.where(r[:-1] == i * n - (r[-1] - r[:-1]))[0]
    if np.any(r[equal] <= K):
        print(i)
        exit()

Submission status: Accepted

Solution code:
import numpy as np


# 約数の列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort()
    return divisors


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

A = np.array(A, np.int64)
d = make_divisors(A.sum())

for i in d[::-1]:
    r = A % i
    r.sort()
    r = r[r != 0]
    if r.size == 0:
        print(i)
        exit()
    else:
        n = np.arange(r.size - 1, 0, -1)

    np.cumsum(r, out=r)
    equal = np.where(r[:-1] == i * n - (r[-1] - r[:-1]))[0]
    if np.any(r[equal] <= K):
        print(i)
        exit()

Submission status: Accepted

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

M = sum(A)
L = []
i = 1
while i <= M**0.5:
    if M%i == 0:
        L.append(i)
        L.append(M//i)
    i += 1
    
L.sort(reverse=True)

for i in L:
    temp = [0]*N
    for j in range(N):
        temp[j] = A[j]%i
    temp.sort()
    cnt = 0
    l = 0
    r = N-1
    while l < r:
        if temp[l] == 0:
            l += 1
            continue
        if temp[r] == 0:
            r -= 1
            continue
        t = temp[l]
        temp[l] = 0
        cnt += t
        while l < r and temp[r]+t > i:
            t -= i-temp[r]
            temp[r] = 0
            r -= 1
        temp[r] += t
        temp[r] %= i
            
    if cnt <= K:
        ans = i
        break

print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
As = list(map(int, input().split()))
rs = []
a = sum(As)
for i in range(a):
    i += 1
    if a % i == 0:
        rs.append(i)
        rs.append(a//i)
    if a < i**2:
        break
rs = sorted(rs)[::-1]
for r in rs:
    Bs = sorted([A%r for A in As])
    sum1 = 0
    sum2 = r*N - sum(Bs)
    R = None
    for b in Bs:
        sum1 += b
        sum2 -= r - b
        if abs(sum1 - sum2) % r == 0:
            if max(sum1, sum2) > K:
                continue
            R = r
            break
    if R:
        break
print(R)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10 ** 7)

def answer_is_X(X):
    mod = deque(sorted([i%X for i in A if i%X != 0]))
    answer = 0
    while mod:
        Amin = mod.popleft()
        answer += Amin
        while Amin > 0:
            # ポップできない場合
            if not mod:
                return False
            Amax = mod.pop()
            sub = X - Amax
            if sub <= Amin:
                Amin -= sub
            else:
                Amax += Amin
                mod.append(Amax)
                Amin = 0

    if answer <= K:
        return True
    else:
        return False

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

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

sumA_divisors = make_divisors(sum(A))

answer = 0
for i in sumA_divisors:
    if answer_is_X(i):
        answer = i

print(answer)

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):
        B=[a%d for a in A]
        B.sort()
        res=INF
        for i in range(n):
            minus=sum(B[:i])
            plus=sum(d-b for b in B[i:])
            res=min(res,max(minus,plus))
        return res<=k

    print(max(d for d in D if(check(d))))
resolve()