Problem:


Score : 500 points

Problem Statement

We have a sequence of N integers: A_1, A_2, \cdots, A_N.

You can perform the following operation between 0 and K times (inclusive):

Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.

Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.

Constraints

2 \leq N \leq 500

1 \leq A_i \leq 10^6

0 \leq K \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_{N-1} A_{N}

Output

Print the maximum possible positive integer that divides every element of A after the operations.

Sample Input 1

2 3
8 20

Sample Output 1

7

7 will divide every element of A if, for example, we perform the following operation:

Choose i = 2, j = 1. A becomes (7, 21).

We cannot reach the situation where 8 or greater integer divides every element of A.

Sample Input 2

2 10
3 5

Sample Output 2

8

Consider performing the following five operations:

Choose i = 2, j = 1. A becomes (2, 6).

Choose i = 2, j = 1. A becomes (1, 7).

Choose i = 2, j = 1. A becomes (0, 8).

Choose i = 2, j = 1. A becomes (-1, 9).

Choose i = 1, j = 2. A becomes (0, 8).

Then, 0 = 8 \times 0 and 8 = 8 \times 1, so 8 divides every element of A. We cannot reach the situation where 9 or greater integer divides every element of A.

Sample Input 3

4 5
10 1 2 22

Sample Output 3

7

Sample Input 4

8 7
1 7 5 6 8 2 6 5

Sample Output 4

5



Sample input:
2 3
8 20


Sample output:
7

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from heapq import heappush, heapreplace
from itertools import count, product
from functools import reduce
from math import ceil, sqrt
from collections import defaultdict, deque

class Primes_C(object):
    def b_search(L,t):
        #増大列LについてL[:+1]の要素すべてがt以下であるような最大のi<len(L)を返す。
        search_range = [-1, len(L)]
        update_range = lambda mid: search_range.__setitem__(t<L[mid], mid)
        for _ in range(search_range[1].bit_length()):
            update_range(sum(search_range)//2)
        return search_range[0]
    
    def __init__(self):
        self.P = [2]
        self.Pappend = self.P.append
        self.Q = deque([])
        self.Qappend = self.Q.append
        self.Qpopleft = self.Q.popleft
        self.hq = [] 
        self.integer = count(3,2)
        self.current_i = 2
        self.valid_range = 1
        self.iter_index = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.iter_index >= len(self.P):
            self.step_calc(1)
        self.iter_index += 1
        return self.P[self.iter_index-1]
        pass

    def iter_reset(self, index=0):
        self.iter_index = index

    def list(self, max_int=None):
        if max_int is None:
            return self.P[:]

        if  max_int <= self.current_i:
            return self.P[:Primes_C.b_search(self.P,max_int)+1]

        else:
            self.calc(max_int)
            return self.P[:]

    def extend(self, i):
        if i >= self.valid_range:
            if self.Q:
                q = self.Qpopleft()
                heappush(self.hq, (q**2,q))
            self.valid_range = self.Q[0]**2 if self.Q else i**2

    def check_update(self,i):
        m,r = self.hq[0] if self.hq else (0,0)
        flag =  (i != m)
        if flag:
            self.Pappend(i)
            self.Qappend(i)
        while m == i:
            heapreplace(self.hq, (m+2*r, r))
            m,r = self.hq[0]
        return flag

    def calc(self, max_int):
        for i in self.integer:
            self.extend(i)
            self.check_update(i) 
            self.current_i = i+1
            if max_int <= self.current_i:
                break

    def step_calc(self, step):
        for i in self.integer:
            self.extend(i)
            step -= self.check_update(i) 
            self.current_i = i+1
            if not step:
                break

    def factorization(self, m, F=defaultdict(int)):
        max_int = ceil(sqrt(max(m, 0)))
        index0 = len(self.P)
        index = 0
        p = self.P[0]
        while m > 1 and p <= max_int:
            while not m%p:
                m //= p
                F[p] += 1

            index += 1
            if index >= index0:
                self.step_calc(1)
            p = self.P[index]

        if m > 1:
            F[m] += 1

        return F



def solve():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    Primes = Primes_C()

    F = Primes.factorization(sum(A))
    res = 1
    for q in product(*[[p**m for m in range(F[p]+1)] for p in F]):
        d = reduce(int.__mul__, q)
        B = sorted([a%d for a in A])
        if sum(B)-sum(B[-(sum(B)//d):]) <= K:
            res = max(res, d)

    return str(res)

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

Submission status: Accepted

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

total = 0
for _a in a:
    total += _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[::-1] # larget -> small

d_all = make_divisors(total)

for d in d_all:
    resid = []
    for i in range(n):
        resid.append(a[i] % d)
    resid_sum = sum(resid)
    resid.sort()
    x = resid_sum // d

    if x > 0:
        resid_sum2 = sum(resid[:-x]) + x * d - sum(resid[-x:])
        if resid_sum2 <= k * 2: 
            ans = d
            break
    else:
        ans = d
        break

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter, deque
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys
#input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().split()))

N, K = inpl()
A = inpl()

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 = sorted(make_divisors(sum(A)))

ans = 1
g0 = itemgetter(0)

for d in D:
    x = 0
    X = []
    for i in range(N):
        X.append(A[i]%d)

    X = sorted(X)
    l = 0
    r = N-1
    while l < N and X[l] == 0:
        l += 1
    while l < N and (not (X[l] == 0 or X[l] == d)):
        m = min(X[l], d - X[r])
        x += m
        X[l] -= m
        X[r] += m
        if X[l] == 0:
            l += 1
        if X[r] == d:
            r -= 1
    if x <= K:
        ans = max(ans, d)

print(ans)

Submission status: Accepted

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

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

    divisors.sort(reverse=True)
    return divisors
d=make_divisors(sum(a))
l=len(d)

x=0
for i in range(l):
    b=[]
    c=[]
    x=d[i]
    for j in range(n):
        if x-a[j]%x>a[j]%x:
            b.append(a[j]%x)
        else:
            c.append(x-a[j]%x)
    b.sort()
    c.sort()
    bs=sum(b)
    cs=sum(c)
    if bs<cs:
        bufl=b
        b=c
        c=bufl
        buf=bs
        bs=cs
        cs=buf

    while(bs>cs):
        y=b.pop(-1)
        bs-=y
        cs+=(x-y)
        c.append(y)
    if bs-cs==0 and bs<=k:
        print(x)
        sys.exit()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
INF = (10 ** 6)*500

M = 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(reverse=True)
    return divisors

T = make_divisors(M)

ans = INF
for t in T:
    p = []
    for a in A:
        p.append(a - a//t * t)
    p.sort()
    s, w = 0, 0
    for h in p:
        if s + h <= K:
            s += h
        else:
            w += t - h
    if s >= w:
        ans = t
        break

print(ans)

Submission status: Accepted

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

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

d_.sort()
for d in d_[::-1]:
  b=[]
  B=0
  for i in range(n):
    b.append(a[i]-d*(a[i]//d))
    B+=b[-1]
  b.sort()
  
  flag=False
  for k in range(n+1):
    if sum(b[0:k])<=min(K,K+B-d*(n-k)):
      flag=True
      break
  if flag:
    break
print(d)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
S=sum(A)
DivS=set()
index=1
while(index*index<=S):
    if S%index==0:
        DivS.add(index)
        DivS.add(S//index)
    index+=1
#print(DivS)
ans=1
for d in DivS:
    B=[A[i] for i in range(N)]
    for i in range(N):
        if A[i]%d==0:
            continue
        #kd<A[i]<(k+1)d
        #k=A[i]//d
        tmp1=(A[i]//d)*d
        tmp2=tmp1+d
        if abs(tmp1-A[i])<=abs(tmp2-A[i]):
            B[i]=tmp1
        else:
            B[i]=tmp2
    nowsum=sum(B)
    #print(d,B)
    if nowsum!=S:
        C=sorted(range(N),key=lambda i:abs(A[i]-B[i]),reverse=True)
        if nowsum>S:
            k=0
            need=(nowsum-S)//d
            for i in C:
                if B[i]>A[i]:
                    B[i]-=d
                    k+=1
                if k>=need:
                    break
        if nowsum<S:
            k=0
            need=(S-nowsum)//d
            for i in C:
                if B[i]<A[i]:
                    B[i]+=d
                    k+=1
                if k>=need:
                    break
    #print(d,A,B)
    cost=sum([abs(A[i]-B[i]) for i in range(N)])
    if cost<=2*K:
        ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


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


def solve(N: int, K: int, A: "List[int]"):
    tot = sum(A)
    divs = make_divisors(sum(A))

    m = 1
    for cand in divs[1:]:
        modA = sorted([a % cand for a in A])
        counter = 0
        left = 0
        while left < N and modA[left] == 0:
            left += 1
        right = N-1
        while left < right:
            smaller = min(modA[left], cand - modA[right])
            modA[left] -= smaller
            modA[right] += smaller
            counter += smaller
            if modA[left] == 0:
                left += 1
            if modA[right] == cand:
                right -= 1
        if counter <= K:
            m = cand

    print(m)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sm = sum(a)

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

answer = 1

for _ in range(len(div)):
    ans = div.pop()
    b = sorted(list(map(lambda x: x%ans, a)))

    lenb = len(b)
   
    l = 0
    r = ans*len(b) - sum(b)

    for i in range(lenb):
        l += b[i]
        r -= ans - b[i]
        if l <= k and l >= r and (l-r) %2 ==0:
            print(ans)
            exit()

Submission status: Accepted

Solution code:
import math
import sys

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

s=sum(a)
s_factors=[]

l=int(math.sqrt(s))

for i in range(1,l+1):
    if s%i==0:
        s_factors.append(i)
        s_factors.append(s//i)

s_factors.sort()

for f in s_factors[::-1]:
    b=[a[i]%f for i in range(n)]
    c=[f-a[i]%f for i in range(n)]
    
    b.sort()
    c.sort()
    c=c[::-1]

    sb=[0 for i in range(n)]
    sc=[0 for i in range(n)]
    
    sb[0]=b[0]
    sc[0]=c[0]

    for i in range(1,n):
        sb[i]=sb[i-1]+b[i]

    for i in range(1,n):
        sc[i]=sc[i-1]+c[i]

    for i in range(n):
        if sb[i]==sc[n-1]-sc[i]:
            if sb[i]<=k:
                print(f)
                sys.exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    print(c - min(b + c, a) + b)
    return

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

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

#D
def D():
    s = S()
    lens = len(s)
    ans = [0] * len(s)
    i = 0
    while i != len(s):
        for j in range(i, lens):
            if s[j] == "R":
                continue
            break
        R = j - i
        for i in range(j, lens):
            if s[i] == "L":
                continue
            break
        else:
            i += 1
        L = i - j
        ans[j] = R // 2 + (L+1) // 2
        ans[j - 1] = L // 2 + (R+1) // 2

    print(*ans)
    return

#E
def E():
    def make_divisor(n):
        res = []
        for i in range(1, int(math.sqrt(n))+1):
            if n % i == 0:
                res.append(i)
                res.append(n // i)
        if n == math.sqrt(n)** 2:
            res.append(int(math.sqrt(n)))
        return res
    n, k = LI()
    a = LI()
    x = sum(a)
    maxa = max(a)
    lis = make_divisor(x)
    lis.sort(reverse=True)
    for li in lis:
        l1 = list(map(lambda x: x % li, a))
        l2 = list(map(lambda x: - x % li, a))
        l1.sort()
        l2.sort()
        c = 0
        while 0 in l1:
            l1.remove(0)
            c += 1
        while 0 in l2:
            l2.remove(0)
        l = 0
        r = 0
        b = 0
        rx = 0
        lx = 0
        while l + r < n - c:
            if b < 0:
                b += l2[r]
                rx += l2[r]
                r += 1
            else:
                b -= l1[l]
                lx += l1[l]
                l += 1
        if b == 0 and rx <= k:
            print(li)
            return
    return

#F
def F():
    return

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def divisor_list(N): #素因数分解
    res = []
    i = 1
    while i*i < N:
        if N%i == 0:
            res.append(i)
            res.append(N//i)
        i += 1
    if i*i == N: res.append(i)
    return sorted(res)

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,k = [int(i) for i in readline().split()]
aaa = [int(i) for i in readline().split()]


l = list(reversed(divisor_list(sum(aaa))))


def check(x):
    res = []
    for ai in aaa:
        c = ai%x
        d = ai%x-x
        if abs(c) > abs(d): res.append(d)
        else: res.append(c)
    res.sort(key = abs)
    
    d = sum(res)
    if d > 0:
        idx = -1
        while d > 0:
            if res[idx]>0:
                d -= x
                res[idx] -= x
            idx -= 1
    elif d < 0:
        idx = -1
        while d < 0:
            if res[idx]<0:
                d += x
                res[idx] += x
            idx -= 1
                
    c = sum([i for i in res if i > 0])        

#    print(x,c,res)
    return (c <= k)



for x in l:
    if check(x):
        print(x)
        exit()

Submission status: Accepted

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

mint = sum(a)
divs = []
for i in range(1, int(mint ** 0.5) +1):
    if mint % i == 0:
        divs.append(i)
        if i != mint // i:
            divs.append(mint // i)
divs.sort()
divs = divs[::-1]
result = 1
for i in range(len(divs)-1):
    cur = divs[i]
    sums = 0
    divList = []
    for j in range(n):
        numi = a[j] % cur
        sums += numi
        divList.append(numi)
    divList.sort()
    divList = divList[::-1]
    count = sums
    countV = 0
    for j in range(n):
        count -= divList[j]
        countV += cur - divList[j]
        if count == countV:
            break
    if count <= k:
        result = cur
        break

print(result)

Submission status: Accepted

Solution code:

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

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

sumA = sum(A)

now = 1
yaku = []

while True:

    if now ** 2 > sumA:
        break

    if sumA % now == 0:
        yaku.append(now)
        yaku.append(sumA // now)

    now += 1

yaku.sort()

nowK = 0
nowX = 0
flag = True
ans = 0
for i in yaku:

    nowK = 0
    nowX = 0
    flag = True
    nlis = []
    for a in A:

        nowK += a % i
        nlis.append(a%i)

    nlis.sort()
    nlis.reverse()

    for j in range(nowK // i):

        nowX += i - nlis[j]

    if nowX > K:
        flag = False
        


            
    if flag:
        ans = max(ans,i)

print (ans)

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

divs = make_divisors(sumA)

for i in divs:
    mod = []
    for j in range(N):
        mod.append(A[j] % i)
    mod.sort(reverse=True)
    tmp = sum(mod) // i # -する数
    tmp = tmp * i - sum(mod[:tmp])  # -する合計数
    if tmp <= K:
        ans = i
        break

print(ans)

Submission status: Accepted

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

    # divisors.sort()
    return divisors

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

s = sum(a)

divs = make_divisors(s)
divs.sort(reverse=True)

#print(divs)
divstimes = len(divs)

for i in range(divstimes):
    nowd = divs[i]
    rems = [a[j]%nowd for j in range(n)]
    rems.sort(reverse=True)
    time = sum(rems)//nowd
    #print(rems)
    #print(time)
    total = sum(rems[time:n])
    #print("tot",sum(rems[time:n]))
    #print()
    if(total <= k):
        ans = nowd
        break
    
    
print(ans)

Submission status: Accepted

Solution code:
# E

import sys

n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
l = []

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

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

for b in l:
    check(b)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A_sum = 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(reverse=True)
    return divisors

cand = make_divisors(A_sum)
temp = 0
for i in range(len(cand)):
    c = cand[i]
    abs_sum = 0
    temp = []
    for j in range(len(A)):
        temp.append(A[j] % c)
        
    temp_sum = sum(temp)
    num = temp_sum // c
    temp.sort(reverse=True)
    for i in range(num):
        temp[i] = c - temp[i]

    abs_sum = sum(temp)
    if abs_sum <= 2*K:
        print(c)
        exit()

print(1)

Submission status: Accepted

Solution code:

N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
# N,K = 500,10**9
# A = [10**6-1 for i in range(N)]
# A = [10**6 for i in range(N)]

# N,K = 8,7
# A = [1,7,5,6,8,2,6,5]

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

dvs = make_divisors(sum(A))

AA = [None for i in range(N)]
ok = 1
for dv in dvs:
    for i in range(N):
        AA[i] = A[i]%dv
    AA = sorted(AA)
    # print(dv, AA)
    l,r = 0,N-1
    while l < N-1 and AA[l] == 0:
        l+=1
    while r > 0 and AA[r] == 0:
        r-=1
    kcnt = 0
    while l<r and r>0 and l<N-1:
        # print(dv, l,r,AA[l],AA[r], kcnt)
        # print(dv, kcnt, l,r,"===",AA)
        if AA[l] == 0:
            l+=1
        if AA[r]%dv == 0:
            r-=1
        else:
            mv = max(min([AA[l],dv-AA[r],K-kcnt]),0)
            kcnt += mv
            AA[l]-=mv
            AA[r]+=mv
        if mv == 0:
            # print("dame")
            break
    if l>=r:
        ok = max(ok, dv)

# print(len(dvs))

# print("ok")
print(ok)

Submission status: Accepted

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

x = []
for i in range(1, s+1):
    if i * i > s:
        break
    if s % i == 0:
        x.append(i)
        x.append(s//i)

ans = 0
for xi in x:
    b = []
    for i in range(n):
        if a[i] % xi != 0:
            b.append(a[i] % xi)

    b.sort()
    b = deque(b)

    c = 0
    r = 0
    while b:
        q = b.pop() + r

        while q < xi:
            p = b.popleft()
            q += p
            c += p

        r = q - xi

    if c <= k:
        ans = max(ans, xi)
    # print(xi, b, c)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(reverse=True)
divisors=[]
aa=sum(A)
for i in range(1,int(aa**0.5)+1):
  if aa%i==0:
    divisors.append(i)
    if i!=n//i:
      divisors.append(aa//i)
divisors.sort(reverse=True)

def f(d):
  count=0
  res1,res2=[],[]
  q=aa//d
  for i in range(n):
    if A[i]%d<(A[i]//d+1)*d-A[i]:
      count+=A[i]//d
      res2.append(A[i]%d)
    else:
      count+=A[i]//d+1
      res1.append((A[i]//d+1)*d-A[i])
  if count==q:
    return sum(res1)
  elif count<q:
    r2=len(res2)
    res2.sort(reverse=True)
    if r2==0:
      return sum(res1)+d*(q-count)
    else:
      if r2>q-count:
        return sum(res1)+d*(q-count)-sum(res2[:q-count])
      else:
        return sum(res1)+d*(q-count)-sum(res2)
  else:
    r1=len(res1)
    res1.sort(reverse=True)
    if r1==0:
      return sum(res2)+d*(count-q)
    else:
      if r1>q-count:
        return sum(res2)+d*(count-q)-sum(res1[:count-q])
      else:
        return sum(res2)+d*(count-q)-sum(res1)

ans=1
for d in divisors:
  if f(d)<=k:
    ans=d
    break
print(ans)

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

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

sum_a = sum(a)
div = make_divisors(sum_a)
ans = []
for i in div:
    mod_list = sorted([j%i for j in a],reverse=True)
    x = int(sum(mod_list)/i)
    mod_list = mod_list[:x]
    change = sum([i-j for j in mod_list])
    if change <= k:
        ans.append(i)
print(max(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a_list=list(map(int,input().split()))
S=sum(a_list)
import sys
i=1
while i**2<=S:
    if S%i==0:
        x=S//i
        temp=[]
        s=0
        for j in range(n):
            if (a_list[j]%x)!=0:
                s+=x-a_list[j]%x
                temp.append(a_list[j]%x)
        temp.sort()
        num=sum(temp[:s//x])
        if num<=k:
            print(x)
            sys.exit()
        temp=[]
        s=0
        for j in range(n):
            if (a_list[j]%i)!=0:
                s+=i-a_list[j]%i
                temp.append(a_list[j]%i)
        temp.sort()
        num=sum(temp[:s//i])
        if num<=k:
            ans=i
    i+=1
print(ans)

Submission status: Accepted

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

A_sum = sum(A)
A_sum_div = []
div = 1
while div ** 2 <= A_sum:
    if A_sum % div == 0:
        A_sum_div.append(div)
        if div ** 2 != A_sum:
            A_sum_div.append(A_sum // div)
    div += 1
A_sum_div.sort(reverse=True)

for i in range(len(A_sum_div)):
    M = A_sum_div[i]
    A_mod = [0] * N
    for j in range(N):
        A_mod[j] = A[j] % M
    A_mod.sort(reverse=True)
    A_mod_sum = sum(A_mod)
    need = 0
    if A_mod_sum != 0:
        for j in range(N):
            need += M - A_mod[j]
            A_mod_sum -= M
            if A_mod_sum == 0:
                break
    if need <= K:
        print(M)
        break

Submission status: Accepted

Solution code:

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

s = sum(a)
d = []
for i in range(1, s):
    if s % i == 0:
        d.append(i)
    if s <= i * i:
        break
    if s % i == 0:
        d.append(s // i)
d = list(reversed(sorted(d)))

for di in d:
    b = []
    for ai in a:
        b.append(ai % di)
    b = list(sorted(b))
    cnt = 0
    il = 0
    ir = n - 1
    while il < ir:
        if b[il] <= di - b[ir]:
            cnt += b[il]
            b[ir] += b[il]
            b[il] = 0
            il += 1
        else:
            cnt += di - b[ir]
            b[il] -= di - b[ir]
            b[ir] = di
            ir -= 1
    if cnt <= k:
        print(di)
        break

Submission status: Accepted

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

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()

    cump = [0]
    for m in mods:
        cump.append(cump[-1] + m)
    cumm = [0]
    for m in reversed(mods):
        cumm.append(cumm[-1] + (d-m))
    for i in range(1,N):
        if cump[i] == cumm[N-i] and cump[i] <= K:
            print(d)
            exit()

Submission status: Accepted

Solution code:
from fractions import gcd

n, k = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())

S = sum(a)

div = []
for d in xrange(1, int(S ** 0.5) + 1):
    if S % d == 0:
        div.append(d)
        if d * d != S:
            div.append(S // d)

g = 0
for i in xrange(n):
    g = gcd(g, a[i])

ans = g
for d in div:
    if d < g: continue
    
    X = 0
    liz = []
    for i in xrange(n):
        x = a[i] % d
        if (x != 0): y = d - x
        else: y = 0
        
        X += y
        liz.append(y)
    liz.sort()

    q = X // d
    op = 0
    for i in xrange(len(liz) - 1, len(liz) - q - 1, -1):
        liz[i] -= d
        assert(liz[i] < 0)
        op += abs(liz[i])

    if op <= k:
        ans = max(ans, d)

print ans