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:
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

    def enum_divisors(n):
        # 約数列挙
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        if d == 1:
            print(d)
            return
        diff_n = []
        for a in A:
            if a % d != 0:
                diff_n.append(a % d)
        diff_n.sort()
        diff_p = []
        for dn in diff_n:
            diff_p.append(d - dn)
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        M = len(S_n) - 1
        if min(S_n[i] for i in range(1, M)
               if (S_n[i] - (S_p[M] - S_p[i])) == 0) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def is_ok(x):
  P = DD(int)
  for a in A:
    if a%x:
      P[a%x] += 1
  c = 0
  while P and max(P[k] for k in P):
    k = min(k for k in P)
    if not P[k]:
      del P[k]
      continue
    c += k
    P[k] -= 1
    while P and k:
      t = max(k for k in P)
      if not P[t]:
        del P[t]
        continue
      if k >= x-t:
        k -= x-t
        P[t] -= 1
      else:
        P[t] -= 1
        P[t+k] += 1
        break
    if c > K: return False
  return True

N,K = IL()
A = IL()
S = sum(A)

L = make_divisors(S)
L.sort(reverse = True)
for x in L:
  if is_ok(x):
    print(x)
    exit()

Submission status: Accepted

Solution code:
import heapq

def divisor(i):
    s = []
    for j in range(1, int(i ** (1 / 2)) + 1):
        if i % j == 0:
            s.append(i // j)
            s.append(j)
    return sorted(set(s))

n, k = map(int, input().split())
a = list(map(int, input().split()))
suma = sum(a)
s = divisor(suma)
for i in range(1, len(s) + 1):
    x = s[-i]
    y = suma // x
    h = []
    heapq.heapify(h)
    for j in a:
        y -= j // x
        heapq.heappush(h, -(j % x))
    cnt = 0
    for _ in range(y):
        cnt += (heapq.heappop(h) % x)
    if cnt <= k:
        print(x)
        exit()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, K = map(int, input().split())
A = list(sorted(map(int, input().split())))
s = sum(A)
i = 2
cands = [s]
while i ** 2 <= s:
    if s % i == 0:
        cands.append(i)
        cands.append(s // i)
    i += 1
cands = sorted(cands)

ans = 1
for cand in cands:
    B = deque(list(sorted(map(lambda x: x % cand, A), reverse=True)))
    k = 0
    while len(B) > 0:
        x = B.popleft()
        while x % cand != 0:
            y = B.pop()
            z = x + y
            if z > cand:
                k += cand - x
                x = cand
                y = z - cand
                B.append(y)
            else:
                k += y
                x = z
    if k <= K:
        ans = max(ans, cand)
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    #約数列挙
    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
    mod=10**9+7
    N,K=MI()
    A=LI()
    S=sum(A)
    
    div=make_divisors(S)
    N2=len(div)
    
    ans=1
    for g in div:
        L=[0]*N
        for i in range(N):#とりあえず，マイナス分だけ考えて，全部gの倍数に寄せる
            diff=A[i]%g
            L[i]=diff
        S=sum(L)
        L.sort(reverse=True)
        
        #ここから足していく
        cost=0#かかった手数
        ii=0#Lの大きい順に見ていく
        while S!=0:#プラスとマイナスで合計が0になるようにする
            b=g-L[ii]
            cost+=b
            S-=g#g*1だけ合計値をあげたから
            ii+=1
        # print(g,L,cost)
            
        if cost<=K:
            ans=g
            break
        
    print(ans)

    
    
    

main()

Submission status: Accepted

Solution code:
import itertools
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
divlis = make_divisors(sum(A))

for res in divlis:
    tmp = [i%res for i in A]
    tmp.sort()
    tmp_l = [0]+list(itertools.accumulate(tmp))
    tmp_r = [0]*(n+1)
    
    for i in range(n-1,-1,-1):
        tmp_r[i] = tmp_r[i+1] + res-tmp[i]

    for i in range(n+1):
        if(tmp_l[i]==tmp_r[i] and tmp_l[i]<=k):
            print(res)
            exit()

Submission status: Accepted

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
D=make_divisors(sum(A))
ans=1
for i in D:
  E=[]
  for j in A:
    d=j%i
    if d!=0:
      E.append(d)
  if len(E)==0:
    ans=i
  E=sorted(E)
  cn=0
  e=sum(E)
  left,right=e,0
  #print(i,E)
  for k in range(len(E)):
    left-=E[-1-k]
    right+=(i-E[-1-k])
    if left==right:
      if left<=K:
        ans=i
      break
print(ans)

Submission status: Accepted

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

s=sum(A)
import math
def yakusu(n):
  ans_local=set()
  for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
      ans_local = ans_local | set([i,n//i]) #setなので平方数でもOK
  return list(ans_local)  #必要に応じてsort

yaku=sorted(yakusu(s), reverse=1)
#print(yaku)
for mod in yaku:
    B=[i%mod for i in A if i%mod!=0]
    if B==[] : print(mod);exit()
    if len(B)==1:
        q=B[0]
        if 0<=q<=k or mod-k<=q: print(mod);exit()
        else:continue
    B.sort()
    r=[B[0]]*len(B)
    for i in range(len(B)-1):
        r[i+1]= r[i]+B[i+1]
    now=float("INF")
    for i in range(1,len(B)): #切り方
        if r[i-1] ==  mod*(len(B)-i)-(r[-1]-r[i-1]) and r[i-1]<=k:
            print(mod);exit()

Submission status: Accepted

Solution code:
def max2(x,y):
    return x if x > y else y

def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
D = divisors(S)
D.sort()
res = 0
for k in D:
    B = []
    for a in A:
        B.append(a%k)
    B.sort()
    cnt = sum(B)//k
    if k*cnt - sum(B[-cnt:]) <= K:
        res = max2(res, k)

print(res)

Submission status: Accepted

Solution code:
def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

import sys
input = sys.stdin.readline

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

def test(x):
    k = D[x]
    B = []
    for a in A:
        B.append(a%k)
    B.sort()
    cnt = sum(B)//k
    return k*cnt - sum(B[-cnt:]) <= K

p = binary_search_int(0,len(D),test)
q = binary_search_int(p+1,len(D),test)
print(max(D[p],D[q]) if q != p+1 else D[p])

Submission status: Accepted

Solution code:
def max2(x,y):
    return x if x > y else y

def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table

import numpy as np
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
S = sum(A)
D = divisors(S)
D.sort()
res = 0
for k in D:
    B = A%k
    B.sort()
    cnt = sum(B)//k
    if k*cnt - sum(B[-cnt:]) <= K:
        res = max2(res, k)

print(res)

Submission status: Accepted

Solution code:
def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

import numpy as np
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
S = sum(A)
D = divisors(S)
D.sort()

def test(x):
    k = D[x]
    B = A%k
    B.sort()
    cnt = sum(B)//k
    return k*cnt - sum(B[-cnt:]) <= K

p = binary_search_int(0,len(D),test)
q = binary_search_int(p+1,len(D),test)
print(max(D[p],D[q]) if q != p+1 else D[p])

Submission status: Accepted

Solution code:
def get_divisors(n):
    divisors = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
        i += 1
    return divisors

n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
divisor = list(get_divisors(s))
divisor.sort(reverse=True)
for d in divisor:
    r = list(map(lambda x : x % d, a))
    r.sort()
    left = r[:]
    right = [0] * n
    right[-1] = r[-1] - d
    for i in range(1, n):
        left[i] += left[i - 1]
        right[n-i-1] = right[n-i] + r[n-i-1] - d
    for i in range(n-1):
        if left[i] == -right[i+1] and left[i] <= k:
            print(d)
            quit()
print(1)

Submission status: Accepted

Solution code:
from math import sqrt

def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a_sum = sum(a)
    st = Divisor_Set(a_sum)
    ans = 1
    st.remove(1)
    for v in st:
        b = [x%v for x in a]
        b.sort()
        for i in range(n-1):
            b[i+1] += b[i]
        for i in range(n-1):
            if b[i] == v*(n-i-1) - (b[-1] - b[i]):
                if b[i] <= k and ans < v:
                    ans = v
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=tuple(map(int,input().split()))
a=sum(l)
ans=1
def f(i):
    p=[]
    for j in l:
        r=j%i
        if r:p.append(r)
    p.sort()
    a=i*len(p)-sum(p)
    now=0
    for j in p:
        now+=j
        a-=i-j
        if now<=k and a<=k and abs(now-a)%i==0:
            return i
    return 0

from math import floor,sqrt
for i in range(1,floor(sqrt(a))+1):
    if a%i==0:
        ans=max(f(i),ans,f(a//i))

print(ans)

Submission status: Accepted

Solution code:

"""
https://atcoder.jp/contests/abc136/tasks/abc136_e
"""

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


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


divisor = calc_divisor(sum(X))
ans = 0
for v in divisor:
    cand = sorted(x % v for x in X)
    cs1 = [0] * (N + 1)
    for i in range(N):
        cs1[i + 1] = cs1[i] + cand[i]

    cs2 = [0] * (N + 1)
    for i in reversed(range(N)):
        cs2[i] = cs2[i + 1] + v - cand[i]

    for a, b in zip(cs1, cs2):
        if a <= K and a == b:
            ans = max(ans, v)
            break

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, K = getNM()
A = getList()

# 操作後のAの要素全てが因数にkを持つ

# 好きな回数操作を行えるとすると、Aの要素全てに因数kを持たせることができるか？
# 操作前と操作後とではAの総和は変わらない → A = akとするとa個のkをN個の要素に配分する
# ことでAの要素全てに因数kを持たせることができる。
# 好きな回数操作を行える、操作後のAの全ての要素を割り切る正の整数は、sum(A)の約数になる

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

# K回以下の操作の条件付きでも題意を満たすか
# alta % kをし、あまりが小さい順にソートする
# 前からi番目までをプラス、i + 1番目以降をマイナスにする
# どちらか大きい方がK以下なら条件を満たす

def judger(x):
    alta = [i % x for i in A]
    alta.sort()
    alta_b = [x - i for i in alta]
    # 前からi番目までプラスにする
    imos_f = copy.deepcopy(alta)
    # 前からi + 1番目以降をマイナスにする
    imos_b = copy.deepcopy(alta_b)

    for i in range(N - 1):
        imos_f[i + 1] += imos_f[i]
        imos_b[-i - 2] += imos_b[-i - 1]

    # 全部マイナス、全部プラスの場合
    imos_f.insert(0, 0)
    imos_b.append(0)

    ans = float('inf')
    for i in range(N + 1):
        ans = min(ans, max(imos_f[i], imos_b[i]))

    return ans

for i in make_divisors(sum(A))[::-1]:
    if judger(i) <= K:
        print(i)
        break

Submission status: Accepted

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

for s in S:
    A.sort(key = lambda x:x%s)
    tmp = 0
    judge = True
    for a in A:
        if tmp + (a%s)<=k and judge:
            tmp += a%s
        else:
            judge = False
            tmp -= s-(a%s)
        if tmp<0:
            break
    if tmp>=0:
        print(s);exit()

Submission status: Accepted

Solution code:
from itertools import accumulate

n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
goukei = sum(A)


# 約数列挙
def divide(n):  # unsort
    ans = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i == i:
                continue
            ans.append(n // i)
    return ans


kouho = divide(goukei)
kouho.sort(reverse=True)
ans = 0
for num in kouho:
    delta = 0
    outflag = 0
    d = [0] * n
    for i in range(n):
        d[i] = A[i] % num
    d.sort()
    SD = list(accumulate([0] + d))
    for i in range(n + 1):
        sageru = SD[i]
        ageru = num * (n - i) - (SD[n] - SD[i])
        delta = ageru - sageru
        if delta % num == 0 and max(sageru, ageru) <= k:
            print(num)
            exit()
print(1)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,K = MI()
A = LI()

s = sum(A)

divisor = []  # s の約数

for i in range(1,int(s**.5)+1):
    if s % i == 0:
        divisor.append(i)
        if i != s//i:
            divisor.append((s//i))

divisor.sort(reverse=True)

from itertools import accumulate

for d in divisor:
    B = [a % d for a in A if a % d != 0]
    B.sort()
    C = [0] + list(accumulate(B))
    D = [0] + list(accumulate([d-b for b in B]))
    r = 10**10  # 操作の回数
    for i in range(len(C)):
        r = min(r,max(C[i],D[-1]-D[i]))
    if r <= K:
        print(d)
        break

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,K = MI()
A = LI()

s = sum(A)

divisor = []  # s の約数

for i in range(1,int(s**.5)+1):
    if s % i == 0:
        divisor.append(i)
        if i != s//i:
            divisor.append((s//i))

divisor.sort(reverse=True)

from itertools import accumulate

for d in divisor:
    B = []
    for a in A:
        if a % d == 0:
            continue
        else:
            B.append(a % d)
    B.sort()
    C = [0] + list(accumulate(B))
    D = [0] + list(accumulate([d-b for b in B]))
    r = 10**10  # 操作の回数
    for i in range(len(C)):
        r = min(r,max(C[i],D[-1]-D[i]))
    if r <= K:
        print(d)
        break

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=sum(a)
cd=set(())
for i in range(1,int(m**0.5)+2):
  if m%i==0:
    cd.add(i)
    cd.add(m//i)
cd=list(cd)
cd.sort(reverse=True)
def func(x):
  r=[ai%x for ai in a]
  r.sort()
  tmp=0
  sr=[0]
  for ri in r:
    tmp+=ri
    sr.append(tmp)
  for i in range(n+1):
    tmp0=sr[i]
    tmp1=(n-i)*x-(sr[-1]-sr[i])
    if tmp0==tmp1 and tmp0<=k:
      return True
  return False


for x in cd:
  if x==1:
    print(1)
    exit()
  if func(x):
    print(x)
    exit()

Submission status: Accepted

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

sumA = sum(A)
candiate = []
# sumAの約数を列挙する
tmp = 1
while tmp * tmp <= sumA:
    if sumA % tmp == 0:
        candiate.append(tmp)
        candiate.append(sumA // tmp)
    tmp += 1

def f(x):
    A.sort(key=lambda z:z%x)
    tmp = 0
    judge = True
    for a in A:
        if tmp + (a % x) <= K and judge:
            tmp += a % x
        else:
            judge = False
            tmp -= x - (a % x)
        if tmp < 0: return False
    return True
ans = -1
for cand in candiate:
    if f(cand):
        ans = max(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

def main():
    n, k = map(int, input().split())
    a = np.array([int(x) for x in input().split()])
    key = make_divisors(np.sum(a))
    
    for v in key:
        mod = np.sort(a%v)
        c1, c2 = 0, np.sum(mod)
        judge = c2
        for i in range(n-1, -1, -1):
            c1 += v-mod[i]
            c2 -= mod[i]
            judge = min(judge, max(c1, c2))
        if judge <= k:
            print(v)
            sys.exit()
    
    
if __name__ == "__main__":
    main()

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()
    #約数の大きい順にソートしたい場合
    divisors.sort(reverse=True)
    return divisors
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in make_divisors(sum(a)):
    x=[a[j]-(a[j]//i)*i for j in range(n)]
    x.sort(reverse=True)
    s=sum(x)
    compk=0
    for j in range(n):
        if s==0:
            break
        else:
            s-=i
            x[j]-=i
            compk+=abs(x[j])
    if compk<=k:
        print(i)
        break

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
l = make_divisors(s)
l.sort(reverse=True)
for i in l:
    l2 = [j % i for j in a]
    l2.sort(reverse=True)
    m = sum(l2) - sum(l2[:sum(l2)//i])
    if i == 1:
        m = 0
    if m <= k:
        s = i
        break
print(s)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

s = sum(A)
m = math.ceil(math.sqrt(s))

divs = []
divs2 = []
i = 1
while i <= m:
	if s % i == 0:
		divs.append(i)
		divs2.append(s//i)
	i += 1
divs.reverse()
divs2 += divs

ans = 1
for n in divs2:
	B = [a % n for a in A]
	s = sum(B)
	if s % n != 0: continue
	B.sort()
	B = [b for b in B if b != 0]
	if len(B) == 0:
		ans = max(ans, n)
		break
	bsum = [0]*len(B)
	rbsum = [0]*len(B)
	bs = 0
	for i, b in enumerate(B):
		bs += b
		bsum[i] = bs
	bs = 0
	for i in range(len(B)-1, -1, -1):
		bs += n - B[i]
		rbsum[i] = bs
	need = float('inf')
	for i in range(len(B)-1):
		if bsum[i] == rbsum[i+1]:
			need = bsum[i]
			break
	if need <= K:
		ans = max(ans, n)
		break
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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

asum = sum(a)
adiv = make_divisors(asum)
adiv.reverse()

a = np.array(a)
ans = 1
flg = False
for i in adiv:
    a_ = np.sort(a % i)
    # print(i, a_)
    msum = a_.sum()
    msum_ = 0
    for j in range(-1, -n-1, -1):
        msum -= a_[j]
        msum_ += i - a_[j]
        if msum_ > k:
            break
        if msum < msum_:
            break
        if msum == msum_ :
            ans = i
            flg = True
            break
    if flg:
        break

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def divisors(n):
    # 約数列挙

    divisors = []

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

    return divisors


def main():
    from itertools import accumulate
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    s = sum(a)
    divs = divisors(s)
    divs.sort()

    ans = 1
    for div in divs:
        rem = [0] * n
        rem2 = [0] * n
        for i, x in enumerate(a):
            rem[i] = x % div
        rem.sort()
        for i in range(n):
            rem2[i] = div - rem[i]
        acc = list(accumulate(rem))
        acc2 = list(accumulate(rem2))
        for i in range(n):
            cnt = max(acc[i], acc2[-1] - acc2[i])
            if cnt <= k:
                ans = div
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://betrue12.hateblo.jp/entry/2020/03/28/142051

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

    def divisor_generator(n):
        div = 1

        stock = []
        while div * div <= n:
            if n % div == 0:
                yield n // div
                stock.append(div)
            div += 1

        for div in reversed(stock):
            yield div

    tot = sum(A)
    for div in divisor_generator(tot):
        k = tot // div - sum(a // div for a in A)
        R = sorted(a % div for a in A)
        Rc = [div - r for r in R]

        cond = (sr := sum(r for r in R[:N - k])) == sum(r for r in Rc[N - k:]) and sr <= K
        if cond:
            print(div)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

al_divs.sort(reverse=True)
for div in al_divs:
    # al_rems = [0]*div
    al_rems = []
    for a in al:
        # al_rems[a%div] += 1
        al_rems.append(a%div)
    al_rems.sort()
    cnt = 0
    curr_num = 0
    q = deque(al_rems)
    while q:
        if curr_num >= 0:
            l = q.popleft()
            cnt += l
            curr_num -= l
        else:
            r = q.pop()
            cnt += (div-r)
            curr_num += (div-r)
    # print('---',div)
    # print(cnt)
    if cnt//2 <= k:
        print(div)
        break