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
import math
INF = 1 << 20

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print("%d" % solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    divisor = 1
    # list all possible divisors
    while divisor * divisor <= total:
        if total % divisor == 0:
            candidates.append(divisor)
            candidates.append(total/divisor)
        divisor += 1
    candidates = sorted(candidates, reverse=True)

    for divisor in candidates:
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()
        A = sum(mods)

        need = INF
        index = math.floor(-1 * A/divisor)
        need = sum(mods[0:index])
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = 0

for i in divisors:
    listA = [0]*N
    for j in range(N):
        listA[j] = A[j] % i
    listA.sort()
    sumlist = sum(listA)


    if sum(listA[:-sumlist // i]) <= K:
        ans = max(ans,i)
            
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC136 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,k = map(int,input().split())
a = list(map(int,input().split()))
s = sum(a)
lst = []
for i in range(1,int(math.sqrt(s))+1):
    if s % i == 0:
        if i != s//i:
            lst.append(i)
            lst.append(s//i)
        else:
            lst.append(i)
lst.sort()
for i in lst[::-1]:
    x = [[j%i,-j%i] for j in a]
    x.sort()
    b = [j for j,k in x]
    c = [k for j,k in x]
    #+1をするリスト
    b = list(accumulate(b))
    #-1をするリスト
    c = list(accumulate(c))
    for j in range(n-1):
        if b[j] == c[-1]-c[j]:
            ans = b[j]
            break
    if ans <= k:
        print(i)
        break

Submission status: Accepted

Solution code:
import math
N,K = map(int,input().split())
A_s = list(map(int,input().split()))
S = sum(A_s)
divs = []
for i in range(1, round(math.sqrt(S)+1) ):
    if S%i==0:
        divs.append(i)
        divs.append(S//i)
answer = 1
for div in divs:
    r_s = []
    for A in A_s:
        r_s.append(A%div)
    r_s.sort()
    if sum(r_s[:-sum(r_s)//div]) <= K and answer < div:
        answer = div
    # for i,r in enumerate(r_s[-sum(r_s)//div:]):
    #     r_s[i] = 

print(answer)

Submission status: Accepted

Solution code:
# ABC 136 E
import math

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

P = [1,S]
for k in range(2,math.floor(math.sqrt(S))+1):
    if S % k == 0:
        P.append(k)
        P.append(S//k)
P = sorted(P)[::-1]

for e in P:
    t = []
    u = []
    for a in A:
        if a%e != 0:
            t.append(a%e)
            u.append(e-a%e)
    t = sorted(t)
    if len(t) == 0:
        print(e)
        exit(0)
    else:
        p = [f for f in t]
        for k in range(1,len(t)):
            p[k] += p[k-1]
        m = [e-f for f in t]
        for k in range(1,len(t)):
            m[-k-1] += m[-k]
        for k in range(len(t)-1):
            if p[k] == m[k+1] and p[k] <= K:
                print(e)
                exit(0)

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())

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

# print(A_array)

A_sum = sum(A_array)

candidate_array = []

for i in range(1, int(math.sqrt(A_sum))+1):
    if A_sum % i == 0:
        candidate_array.append(i)
        if A_sum // i != i:
            candidate_array.append(A_sum//i)

candidate_array.sort()

ans = 0

for check_num in candidate_array:
    q_array = [a % check_num for a in A_array]
    q_array.sort()
    # print(q_array)
    start = 0
    rest = N * check_num - sum(q_array)
    for q in q_array:
        start += q
        rest -= (check_num-q)
        # print(start,rest)
        if start == rest:
            break
    if start <= K:
        ans = max(ans, check_num)

print(ans)

Submission status: Accepted

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

sum1 = 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)

    return divisors

li = make_divisors(sum1)

ans = 0

for i in li:
    b = sorted(list(map(lambda x: x % i,a)))
    count = 0
    flag = -1
    for j in range(len(b)):
        if b[j] % i != 0:
            count += b[j]
            while b[j] > 0:
                if b[j] + b[flag] < i:
                    b[flag] += b[j]
                    b[j] = 0
                else:
                    b[j] -= i - b[flag]
                    b[flag] = i
                    flag -= 1
    if count <= k:
        ans = max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

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


def ok(x):
    b = [i % x for i in a]
    b.sort(reverse=True)
    t = int(sum(b) / x)
    if t == 0:
        return True
    return True if sum(b[t:]) <= k else False


s = sum(a)
sqs = int(math.sqrt(s))
ans = 1
for x in range(1, sqs + 1):
    if s % x != 0:
        continue
    if ok(x):
        ans = max(ans, x)
    if ok(int(s / x)):
        ans = max(ans, int(s / x))

print(ans)

Submission status: Accepted

Solution code:
import sys
import math

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


def ok(x):
    b = []
    for an in a:
        b.append(an % x)
    b.sort(reverse=True)
    print(x, a, b, file=sys.stderr)
    t = int(sum(b) / x)
    print(t, sum(b[t:]), file=sys.stderr)
    if t == 0:
        return True
    return True if sum(b[t:]) <= k else False


s = 0
for an in a:
    s += an

ans = 1
for x in range(1, int(math.sqrt(s)) + 1):
    if s % x != 0:
        continue
    if ok(x):
        ans = max(ans, x)
    if ok(int(s / x)):
        ans = max(ans, int(s / x))

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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


# Aの要素をK回以下の操作ですべてdの倍数にできるならば真を返す関数
def f(d):
    B = sorted(a % d for a in A)
    C = [d - b for b in B]
    X = list(accumulate(B))
    Y = list(accumulate(C))
    return any(
        X[j] == (Y[-1] - Y[j]) <= K
        for j in range(N)
    )


# 解の候補はsum(A)の約数である
S = sum(A)
ans = max(
    (
        S // d if f(S // d) else
        d if f(d) else
        0
    )
    for d in range(1, int(S**0.5) + 2)
    if S % d == 0
)

print(ans)

Submission status: Accepted

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

asum = sum(a)
gcdmax = int(math.sqrt(asum))
li = []
for i in range(2,gcdmax+1):
    if asum%i==0:
        li.append(i)
for i in range(gcdmax,0,-1):
    if asum%i==0:
        li.append(asum//i)


ans = 1
# print(li)

for i in li:
    b = [a[ii] % i for ii in range(n)]
    b.sort()
#     print(i,b)
    l = 0
    r = 0
    x = 0
    y = n-1
    while x<=y:
        if r>=l:
            l += b[x]
            x += 1
        else:
            r += i - b[y]
            y -= 1
#         print(l,r)
    if max(l,r) <= k and (l-r)%i==0 :
        ans = i

print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = sum(A)
flag = False
def make_divisors(n):
    divisors = []
    for i in range(int(n**0.5), 0, -1):
        if n%i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    return sorted(divisors, reverse=True)
divs = make_divisors(s)
for x in divs:
    if flag:
        break
    sortedA = sorted([a%x for a in A])
    sumA = sum(sortedA)
    index_len = len(sortedA)
    sump = 0
    for i, a in enumerate(sortedA):
        sump += a
        summ = x*(index_len - (i+1)) - (sumA - sump)
        if sump == summ and sump <= K:
            print(x)
            flag = True
            break

Submission status: Accepted

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
S=sum(A)
facts=set()
for i in range(1,int(S**0.5)+1):
    if S%i==0:
        facts.add(i)
        facts.add(S//i)
for f in sorted(facts,key=lambda x:-x):
    rs = [i%f for i in A]
    rs2=sorted(rs)
    rsr = [f-r for r in rs2]
    if f-rs2[-1]>K and rs2[-1]>K:
        continue
    cum=0
    ruiseki=[0]*(N)
    tmp=0
    for i,a in enumerate(rs2):
        cum+=a
        ruiseki[i]=cum
    for i in range(N-1):
        s_l=ruiseki[i]
        s_h = f*(N-i-1)-(ruiseki[-1]-s_l)
        if max(s_l,s_h)<=K:
            print(f)
            break
    else:
        continue
    break

Submission status: Accepted

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


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


def solve(B, f):
    cost = sum(B)
    cost = sum(B[:-cost//f])
    return cost


fct = divisors(sum(A))
for f in sorted(fct, reverse=True):
    B = sorted([b % f for b in A])
    cost = solve(B, f)
    if K >= cost:
        print(f)
        quit()

Submission status: Accepted

Solution code:
import numpy as np
import sys
# from numba import njit


def solve(A, K, div):
    for d in range(div.shape[0] - 1, 0, -1):
        res = div[d]
        B = np.sort(A % res)
        if B[B.shape[0] - 1] == 0:
            return res
        i = 0
        j = B.shape[0] - 1
        cost = res - B[j]
        scost = 0
        while j - i > 0:
            for n in range(i, j):
                scost += B[n]
                if scost >= cost:
                    while scost > cost:
                        j -= 1
                        cost += res - B[j]
                    i = n + 1
                    break
            else:
                i = j
        if K >= cost:
            return res
    return 1


def divisor(d, div):
    r = int(d ** 0.5 - 0.0000001) + 1
    ind = 0
    for i in range(1, r):
        if d % i == 0:
            div[ind] = i
            ind += 1
            div[ind] = d // i
            ind += 1
    if d % r == 0:
        div[ind] = r
        ind += 1
    return ind


line = sys.stdin.readline
N, K = map(int, line().split())
A = np.fromstring(line(), dtype=np.int64, sep=' ')
d = A.sum()
div = np.empty(10 ** 6, dtype=np.int64)
num = divisor(d, div)
div = np.sort(div[:num])
print(solve(A, K, div))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# A.sort()
totalA = sum(A)
# print (totalA)

def make_divisors(n): #nの約数をO(root(n))で全列挙、sortして取り出すときはO(root(n) log(n))
    import math
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0: #割り切れるとき
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    divisors.sort(reverse = True)
    return divisors

divisors_lst = make_divisors(totalA)
# print (divisors_lst)
for i in divisors_lst: #答えの候補を全探索
    lst = []
    for j in A:
        lst.append(j % i)
    lst.sort()
    total_lst = 0
    for j in lst:
        total_lst += i - j
    tmp = 0
    for k in lst:
        tmp += k
        total_lst -= (i - k)
        if max(tmp, total_lst) <= K:
            print (i)
            exit()

Submission status: Accepted

Solution code:
import math
def check(n,a):
    l1 = []
    l2 = []
    count1 = 0
    count2 = 0
    for i in range(len(a)):
        if a[i]%n > n - a[i]%n:
            count1 = count1 + n - a[i]%n
            l1.append(n-a[i]%n)
        else:
            count2 = count2 + a[i]%n
            l2.append(a[i]%n)
    b = (count2 - count1) // n
    l1.sort(reverse=True)
    l2.sort(reverse=True)
    if b == 0:
        return count1
    elif b > 0:
        for i in range(b):
            count2 = count2 - l2[i]
        return count2
    else:
        for i in range(-1*b):
            count1 = count1 - l1[i]
        return count1
n,k = map(int,input().split())
a = list(map(int,input().split()))
p = sum(a)
l = []
for i in range(1,int(math.sqrt(p))+1):
    if p%i == 0:
        l.append(i)
        if i != p//i:
            l.append(p//i)
l.sort(reverse=True)
for i in range(len(l)):
    if check(l[i],a) <= k:
        print(l[i])
        break

Submission status: Accepted

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

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

s = sum(a)

dlist = []
for p in range(1,int(s**(1/2))+1):
    if s % p == 0:
        dlist.append(p)
        dlist.append(int(s/p))

anslist = []

for d in dlist:
    r = [a[_] % d for _ in range(n)]
    r.sort()

    w = [r[0]]#累積和
    for i in range(1,n):
        w.append(w[-1]+r[i])
    
    can = "no"
    for j in range(0,n):
        if max(w[j],d*(n-j-1)-w[n-1]+w[j])<=k:
            can = "yes"
            break
    if can == "yes":
        anslist.append(d)

print(max(anslist))

Submission status: Accepted

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

    # divisors.sort()
    return divisors

input1 = input()
input2 = input()

N = int(input1.split()[0])
K = int(input1.split()[1])

nums = [int(s) for s in input2.split()]

divs = make_divisors(sum(nums))

possible = []

for i in divs:
    nord = [s%i for s in nums]
    nord.sort()
    mt_size = sum(nord) // i
    moves = sum(nord[0:N-mt_size])
    if moves <= K:
        possible.append(i)

print(int(max(possible)))

Submission status: Accepted

Solution code:
import math

def facts(n):
    sqrt_n = int(math.sqrt(n))
    fs = []
    fs_rev = []
    
    for i in range(1, sqrt_n + 1):
        if n % i == 0:
            fs.append(i)
            if n != i ** 2:
                fs_rev.append(n // i)
    
    fs.reverse()
    return fs_rev + fs

n, k = map(int, input().split())
ll = list(map(int, input().split()))
s = sum(ll)
fs = facts(s)

for f in fs:
    ll_f = list(map(lambda x: x % f, ll))
    ll_f.sort(reverse = True)
    ignore = sum(ll_f) // f
    keep = sum(ll_f[ignore:])

    if keep <= k:
        print(f)
        break

Submission status: Accepted

Solution code:
import sys

def input():
  return sys.stdin.readline()[:-1]

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

sumA = sum(A)
kouho = make_divisors(sumA)

for i in kouho:
  if sumA%i != 0:
    continue
  r = [0]*N
  for j in range(N):
    r[j] = A[j]%i
  sumr = sum(r)
  if sumr%i != 0:
    continue
  r.sort(reverse=True)
  num = 0
  for k in range(sumr//i):
    num += i-r[k]
  if num <= K:
    print(i)
    exit()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
def divisor(n):
    d0=[]
    d1=[]
    for i in range(1,int(n**.5)+1):
        x,y=divmod(n,i)
        if y==0:
            d0.append(i)
            d1.append(x)
    if d1[-1]==d0[-1]:
        d1=d1[:-1]
    return d0+d1[::-1]
D=divisor(sum(A))
r=1
for d in D[::-1]:
    x=sorted([a%d for a in A])
    for i in range(len(A)-1):
        x[i+1]+=x[i]
    if x[-1]%d==0 and x[-1-x[-1]//d]<=K:
        r=d
        break
print(r)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

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 = II()
A = III()

sumA = sum(A)
kouho = make_divisors(sumA)

for i in kouho:
  if sumA%i != 0:
    continue
  r = [0]*N
  for j in range(N):
    r[j] = A[j]%i
  sumr = sum(r)
  if sumr%i != 0:
    continue
  r.sort(reverse=True)
  num = 0
  for k in range(sumr//i):
    num += i-r[k]
  if num <= K:
    print(i)
    exit()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def factors(N): #約数を全て求める。ただし、順不同
    from collections import deque
    ret = deque()
    middle = int( N**(1/2))
    for i in range(1, middle):
        if N%i == 0:
            ret.append(i)
            ret.append(N//i)
            
    if N%middle == 0:
        ret.append(middle)
        if middle != N//middle:
            ret.append(N//middle)
    return ret

def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    sa = sum(A)
    R = factors(sa)
    l = len(R)
    E = [0]*l
    ans = 0
    for r in R:
        cnt = 0
        E = list( map( lambda x:x%r, A))
        E.sort()
        s = sum(E)
        now = 0
        if s - E[-1] <= K:
            if ans < r:
                ans = r
            continue
        if s == 0:
            continue
        v = 0
        w = N-1
        cnt = 0
        while w-v != 0:
            if E[v] == 0:
                v += 1
                continue
            if E[w] == 0:
                w -= 1
                continue
            if E[v] + E[w] >= r:
                E[v] -= r - E[w]
                cnt += r - E[w]
                E[w] = 0
                w -= 1
            else:
                E[w] += E[v]
                cnt += E[v]
                E[v] = 0
                v += 1
        if cnt <= K:
            if r > ans:
                ans = r
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
AL=list(map(int,input().split()))
summ=0
for i in range(N):
  summ+=AL[i]
candidate=set()
for i in range(1,int(summ**0.5)+1):
  if summ%i==0:
    candidate.add(i)
    candidate.add(summ/i)
ans=0
for x in candidate:
  need=0
  r=[0]*N
  for i in range(N):
    r[i]=AL[i]%x
  r.sort()
  rsum=0
  for i in range(N):
    rsum=rsum+r[i]
  rindex=int(rsum/x)
  lindex=N-int(rsum/x)
  for i in range(lindex):
    need+=r[i]
  if need<=K:
    ans=max(ans,x)
print(int(ans))

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
candidate=set()
result=0
x=1
while x**2<=(sum(a)+1):
	if sum(a)%x==0:
		candidate.add(x)
		candidate.add(int(sum(a)/x))
	x+=1
# print(candidate)
for i in candidate:
	b=[0]*len(a)
	for j in range(len(a)):
		b[j]=int(a[j]%i)
	b.sort()
	if sum(b[:int(len(b)-sum(b)/i)])<=k:
		result=max(result,i)

	# need=0
	# need+=sum(b)/i
	# if need<=k:
print(result)

Submission status: Accepted

Solution code:
import math
def divisors(n, sort=True, reverse=False):
    sqn = math.sqrt(n)
    sqn_int = int(sqn)
    div_list = []
    if sqn == sqn_int:
        div_list.append(sqn_int)
        loop = range(1,sqn_int)
    else:
        loop = range(1,sqn_int + 1)
    for i in loop:
        if n % i == 0:
            div_list.append(i)
            div_list.append(n//i)
    if sort:
        div_list.sort(reverse=reverse)
    return div_list

inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
S = sum(A)
div = divisors(S, reverse=True)
for d in div:
    mods = [ a % d for a in A ]
    mods.sort()
    Sm = sum(mods)
    h = Sm // d
    minK = min(d*(h+1) - sum(mods[N-h-1:]), sum(mods[:N-h]))
    if minK <= K:
        print(d)
        break

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

for x in div:
    r = sorted([i%x for i in a])
    sr = sum(r)
    if sr == 0:
        print(x)
        exit()
    cr = list(accumulate(r))
    for i, j in enumerate(cr):
        if j == x*(n-i-1) - (sr-j) and j <= k:
            print(x)
            exit()

Submission status: Accepted

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

N, K = [int(item) for item in input().split()]
A = [int(item) for item 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()
    return divisors


d_cand = make_divisors(sum(A))
d_cand.sort()
d_cand.reverse()

for d in d_cand:
    r = [a % d for a in A]
    rp_sum = sum(r)
    rm_sum = 0
    if rp_sum % d != 0:
        continue
    r.sort()

    for i in range(N):
        # index i まで r-, i+1から r+
        rp_sum -= r[i]
        rm_sum += r[i]

        n_min = max(0, -(rm_sum + rp_sum) / d + (N - i - 1))
        n_max = (K - rm_sum) / d
        if n_min <= n_max and (n_min % 1 == 0 or n_max % 1 == 0 or int(n_min) != int(n_max)):
            print(d)
            break
    else:
        continue
    break

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 = map(int, input().split())
a = list(map(int, input().split()))

arr = np.array(a)
wa = sum(arr)
divisors = make_divisors(wa)

ans = 1
for div in divisors:
    lst = [0] * n
    for i in range(n):
        lst[i] = a[i] % div
    lst.sort()
    lst = [i for i in lst if i != 0]
    if lst == []:
        ans = max(ans, div)
    arr = np.array(lst)
    arr_amari = np.cumsum(arr)
    arr_reversed = arr[::-1]
    arr_husoku = np.cumsum(div - arr_reversed)[::-1]
    for i in range(len(arr_amari)-1):
        if arr_amari[i] == arr_husoku[i+1] and arr_amari[i] <= k:
            ans = max(ans, div)

print(ans)

Submission status: Accepted

Solution code:
def e_max_gcd(N, K, A):
    def divisor_list(n):
        """n の正の約数のリスト"""
        ret = []
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                ret.append(k)
                if k != n // k:
                    ret.append(n // k)
        ret.sort()
        return ret

    ans = 1  # 任意の整数は1の倍数
    for c in divisor_list(sum(A)):  # sum(A)の約数が解の candidate
        r = sorted([a % c for a in A])
        # rをある位置で左右に分けたとき、「左」には-1、「右」には+1する操作を
        # 行って全要素をcの倍数にしたい。このとき、「左」の要素の和の分だけ
        # 操作してよいが、それはKを超えてはならない。
        # 最初、すべての要素を「左」に入れる。
        # 「左」の要素の関数値A(-1してcの倍数にするための操作回数)は最初sum(r)とし、
        # 「右」の要素の関数値B(+1してcの倍数にするための操作回数)は最初0とする。
        # ここで「左」の要素eを右から順に「右」に入れていくとすると、1つ入れるごとに
        # A の値は e だけ減り、B の値は c - e だけ増える。
        # よって A-B の値は1つ「右」に入れるごとに c だけ減る。
        # ゆえに、「右」に何個の要素を入れるべきかは sum(r)//c からわかる。
        if sum(r[:N - sum(r) // c]) <= K:
            ans = max(ans, c)
    return ans

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

Submission status: Accepted

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

    S = sum(A)
    divisors = make_divisors(S)
    
    for d in divisors:
        R = list(map(lambda x: x % d, A))
        R = [r for r in R if r != 0]
        R.sort()
        cnt_m, cnt_p = 0, 0
        for r in R:
            if cnt_m <= K - r:
                cnt_m += r
            else:
                cnt_p += d - r
        if cnt_m <= K and cnt_p <= K:
            print(d)
            exit()

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

A.sort(reverse=True)

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

P = make_divisors(sum(A))
P.sort(reverse=True)

for p in P:
    z = 0
    for i in range(N):
        z += A[i] % p
    if z % p == 0:
        B = [i % p for i in A]
        B.sort(reverse=True)
        q = z//p
        j = 0
        for i in range(q):
            j += p-B[i]
        if K >= j:
            print(p)
            exit()
            
print(p)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(i) for i 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


lst = make_divisors(sum(A))

for l in lst:
    cnt_m, cnt_p = 0, 0
    ml = sorted([i % l for i in A])
    for m in ml:
        if cnt_m <= K-m:
            cnt_m += m
        else:
            cnt_p += l-m
    if cnt_m <= K and cnt_p <= K:
        print(l)
        exit()
print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
AA = np.array(inpl())
S = sum(AA)

koho = set()
for i in range(1,int(math.sqrt(S))+3):
    if S%i == 0:
        koho.add(i)
        koho.add(S//i)

koho = sorted(list(koho))
ans = 0
for k in koho:
    AA_modk = sorted(AA%k)
    #print(k,AA_modk)

    Ln = Rn = 0
    L = 0
    R = N-1
    while L <= R:
        if Ln <= Rn:
            Ln += AA_modk[L]
            L += 1
        else:
            Rn += k - AA_modk[R]
            R -= 1

    #print(Ln,Rn)

    if K >= Ln:
        ans = max(k,ans)

print(ans)

Submission status: Accepted

Solution code:
import math

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

candidates = []
sumA = sum(A)

i = 1
while i <= math.sqrt(sumA):
    if sumA % i == 0:
        candidates.append(i)
        candidates.append(int(sumA / i))
    i += 1
    
candidates = sorted(candidates, reverse = True)
end = 0
# candidates loop
for i in range(len(candidates)):
    if end:
        break
    # A loop
    T = [0] * len(A)
    for j in range(len(A)):
        T[j] = A[j] % candidates[i]
    T = sorted(T)
    left = sum(T)
    right = 0
    need = max(left, right)
    for l in range(len(T) - 1, -1, -1):
        left -= T[l]
        right += candidates[i] - T[l]
        need = min(need, max(left, right))
    if need <= K:
        print(candidates[i])
        end = 1

Submission status: Accepted

Solution code:
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
div = []
A_sum = sum(A)
i = 1
while i ** 2 < A_sum:
    if A_sum % i == 0:
        div.append(i)
        div.append(A_sum // i)
    i += 1

div.sort(reverse=True)

for j in div:
    mod = [a % j for a in A]
    mod.sort()
    s = sum(mod)
    if sum(mod[:-s // j]) <= K:
        print(j)
        break

Submission status: Accepted

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

s = sum(a)
dl = []
k = 1
while k ** 2 <= s:
  if s % k == 0:
    dl.append(k)
    dl.append(s // k)
  k += 1
  
cand = []
for d in dl:
  op = 0
  b = [n % d for n in a]
  b.sort()
  b.reverse()
  summod = sum(b)
  for i in range(summod // d):
    op += d - b[i]
  if op <= K:
    cand.append(d)
    
print(max(cand))

Submission status: Accepted

Solution code:
from itertools import accumulate

def divisors(n):
    divs = []
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            divs.append(i)
            divs.append(d)
    divs.sort(reverse=True)
    return divs

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

for div in divs:
    m = [ x % div for x in a ]
    m.sort()
    l = [0] + list(accumulate(m))
    r = list(reversed([0] + list(accumulate(reversed([div - x for x in m])))))
    for i in range(len(l)):
        if l[i] == r[i]:
            if l[i] <= k:
                print(div)
                exit()
            break
        elif l[i] > r[i]:
            break