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:
from itertools import accumulate

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

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

ans = 0
for d in divisor:
    x = sorted(v % d for v in A)
    y = [d - r for r in x]
    x_s = [0] + list(accumulate(x))
    y_s = list(accumulate(y[::-1]))[::-1] + [0]

    for i in range(N + 1):
        if x_s[i] <= K and x_s[i] == y_s[i]:
            ans = max(ans, d)
            break

print(ans)

Submission status: Accepted

Solution code:
import sys

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    table.sort(reverse=True)
    return table

def resolve():
    lines = sys.stdin.readlines()
    n, k = tuple(map(int, lines[0].split(' ')))
    a = list(map(int, lines[1].split(' ')))
    divs = divisor(sum(a))

    for div in divs:
        a_mod = list(map(lambda x: x % div, a))
        sum_mod = sum(a_mod)
        a_mod.sort(reverse=True)
        loop = sum_mod//div
        for i in range(loop):
            a_mod[i] = 0
        sum_e_mod = sum(a_mod)
        if k >= sum_e_mod:
            print(div)
            return
    print(1)

resolve()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
m=sum(A)
ans=0
for i in range(1,int(m**0.5)+1):
  if m % i != 0:
    continue 
  for j in [i,m//i]:
    stg = []
    for a in A:
      stg.append(a%j)
    stg.sort()
    sm,idx=0,0
    flag=False
    while sm+stg[idx]<=K:
      sm+=stg[idx]
      idx+=1
      if idx>=N:
        flag=True
        break
    if flag or sum([j-x for x in stg[idx:]]) <= K:
      ans=max(ans,j)
  
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    # Calculate divisors of sum(A)
    S = sum(A)
    divs = list()
    n = 1
    while n ** 2 <= S:
        if S % n == 0:
            m = S // n
            if n != m:
                divs.extend([n, m])
            else:
                divs.append(n)
        n += 1
    divs.sort(reverse=True)
    # calc answer
    ans = S
    for d in divs:
        B = [a % d for a in A]
        B.sort(reverse=True)
        t = sum(B) // d
        k = sum(B) - sum(B[:t])
        if d == 1:
            k = 0
        if k <= K:
            ans = d
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def enum_divisor(num):
        i = 1
        left = []
        right = []
        while i ** 2 < num:
            if num % i == 0:
                left.append(i)
                right.append(num // i)
            i += 1
        if i ** 2 == num:
            return left + [i] + list(reversed(right))
        else:
            return left + list(reversed(right))
    

    def is_ok(m, k, L):
        mod_list = [elm % m for elm in L]
        plus_group, minus_group = [], []
        plus_cnt, minus_cnt = 0, 0
        for mod_num in mod_list:
            if mod_num <= m - mod_num:
                minus_group.append(mod_num)
                minus_cnt += mod_num
            else:
                plus_group.append(mod_num)
                plus_cnt += m - mod_num
        
        # print(f"m {m} plus {plus_group} minus {minus_group}")
        # print(f"pluscnt {plus_cnt} minuscnt {minus_cnt}")
        assert abs(plus_cnt - minus_cnt) % m == 0
        cnt = plus_cnt + minus_cnt
        if plus_cnt > minus_cnt:
            # plus のグループを minus のグループに転じる必要がある
            plus_group.sort()
            for i in range((plus_cnt - minus_cnt) // m):
                mod_num = plus_group[i]
                cnt += (mod_num - (m - mod_num))
        else:
            # minus のグループを plus のグループに
            minus_group.sort(reverse=True)
            for i in range((minus_cnt - plus_cnt) // m):
                mod_num = minus_group[i]
                cnt += ((m - mod_num) - mod_num)
        # print(f"cnt {cnt}")
        assert cnt % 2 == 0
        return cnt // 2 <= k
    

    n, k = mi()
    L = lmi()
    s = sum(L)
    div = enum_divisor(s)
    div.reverse()


    for m in div:
        if is_ok(m, k, L):
            print(m)
            break







if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
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=1)
    return divisors

n,k = map(int,input().split())
a = list(map(int,input().split()))
S = sum(a)
for gcd in make_divisors(S):
    li = deque(sorted([x % gcd for x in a]))
    count = 0
    L = li.popleft()
    R = li.pop()
    while li:
        if L >= gcd-R:
            L -= gcd-R
            count += gcd-R
            R = li.pop()
        else:
            R += L
            count += L
            L = li.popleft()
    count += L
    if count <= k:
        print(gcd)
        exit()

Submission status: Accepted

Solution code:
import numpy as np

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

As_arr = np.array(As_lis)
S = np.sum(As_arr)

smaller_factors = []
larger_factors = []
for i in range(1, int(S ** 0.5) + 1):
    if S % i == 0:
        smaller_factors.append(i)
        larger_factors.append(S // i)

for fac in larger_factors:
    mods = As_arr % fac
    k = np.sum(np.sort(mods)[:N - np.sum(mods) // fac])
    if k <= K:
        print(fac)
        exit()

for fac in reversed(smaller_factors):
    mods = As_arr % fac
    k = np.sum(np.sort(mods)[:N - np.sum(mods) // fac])
    if k <= K:
        print(fac)
        exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

def is_divide(d):
    Rs = [a%d for a in A]
    Rs.sort()
    cumsum = [0] * (N + 1)
    for i in range(N - 1,-1,-1):
        cumsum[i] = cumsum[i + 1] + d - Rs[i]
    cum = 0
    for i in range(N):
        if max(cum,cumsum[i]) <= K:
            return True
        cum += Rs[i]
    return False

S = sum(A)
ans = 0
for i in range(1,S + 1):
    if i*i > S:
        break
    if S%i == 0:
        if is_divide(i):
            ans = max(ans,i)
        if is_divide(S//i):
            ans = max(ans,S//i)
print(ans)

Submission status: Accepted

Solution code:
# 割り切る数は、Aの総和の約数である
# 約数について大きい順にすべて試して、当てはまるものがあれば答え

# 8,20を7の倍数に近づけるとき、
# 8 -> mod 7が1であり、-1か+6で7の倍数になる
# 20 -> mod 7が6であり、-6か+1で7の倍数になる
# 負の和と正の和が一致したとき、そのときの絶対値が答え
# 1,1,2,3,4,5と並べて、前から足していくのが最善。入れ替えると絶対値が増加するので損しかしない

import sys
readline = sys.stdin.readline

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

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

divisors = sorted(divisors,reverse = True)

for d in divisors:
  mods = [0] * (N)
  for i in range(len(A)):
    mods[i] = A[i] % d
  mods = sorted(mods)
  mods_front = [0] * N
  mods_front[0] = mods[0]
  for i in range(1,N):
    mods_front[i] = mods_front[i - 1] + mods[i]
  mods_back = [0] * N
  mods_back[-1] = d - mods[-1]
  for i in range(N - 2,-1,-1):
    mods_back[i] = mods_back[i + 1] + (d - mods[i])
  for i in range(N - 1):
    if mods_front[i] == mods_back[i + 1]:
      if K >= mods_front[i]:
        print(d)
        exit(0)
else:
  print(1)

Submission status: Accepted

Solution code:
# 割り切る数は、Aの総和の約数である
# 自分自身を除く約数について大きい順にすべて試して、当てはまるものがあれば答え

# 8,20を7の倍数に近づけるとき、
# 8 -> mod 7が1であり、-1か+6で7の倍数になる
# 20 -> mod 7が6であり、-6か+1で7の倍数になる

import sys
readline = sys.stdin.readline

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

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

divisors = sorted(divisors,reverse = True)

for d in divisors:
  mods = [0] * (N)
  for i in range(len(A)):
    mods[i] = A[i] % d
  mods = sorted(mods)
  mods_front = [0] * N
  mods_front[0] = mods[0]
  for i in range(1,N):
    mods_front[i] = mods_front[i - 1] + mods[i]
  mods_back = [0] * N
  mods_back[-1] = d - mods[-1]
  for i in range(N - 2,-1,-1):
    mods_back[i] = mods_back[i + 1] + (d - mods[i])
  for i in range(N - 1):
    if mods_front[i] == mods_back[i + 1]:
      if K >= mods_front[i]:
        print(d)
        exit(0)
else:
  print(1)

Submission status: Accepted

Solution code:
# 割り切る数は、Aの総和の約数である
# 自分自身を除く約数について大きい順にすべて試して、当てはまるものがあれば答え

# 8,20を7の倍数に近づけるとき、
# 8 -> mod 7が1であり、-1か+6で7の倍数になる
# 20 -> mod 7が6であり、-6か+1で7の倍数になる
# -1と+1をペアにすることが出来て、この操作回数1をK = 3から引くと2となり、これが偶数ならOK

import sys
readline = sys.stdin.readline

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

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

divisors = sorted(divisors,reverse = True)

#print(divisors)

for d in divisors:
  mods = [0] * (N)
  for i in range(len(A)):
    mods[i] = A[i] % d
  mods = sorted(mods)
  #print("d",d,"mods",mods)
  mods_front = [0] * N
  mods_front[0] = mods[0]
  for i in range(1,N):
    mods_front[i] = mods_front[i - 1] + mods[i]
  mods_back = [0] * N
  mods_back[-1] = d - mods[-1]
  #print("mods_front",mods_front)
  for i in range(N - 2,-1,-1):
    mods_back[i] = mods_back[i + 1] + (d - mods[i])
  #print("mods_back",mods_back)
  for i in range(N - 1):
    if mods_front[i] == mods_back[i + 1]:
      if K >= min(mods_front[i],mods_back[i + 1]):
        print(d)
        exit(0)
else:
  print(1)

Submission status: Accepted

Solution code:
def factors(n):
  a = [1,n]
  x = 2
  while x * x <= n :
    if n % x == 0:          
      a.append(x)
      c=n//x
      while(c+1)*x<=n:
        c+=1
      a.append(c)
    x+=1
  return a
n,k=map(int,input().split())
a=list(map(int,input().split()))
candidates=factors(sum(a))
candidates.sort()
candidates.reverse()
for i in candidates:
  b=[]
  for j in range(n):
    b.append(a[j]%i)
  b.sort()
  upsum=0
  downsum=0
  for j in range(n):
    upsum+=i-b[j]
  for j in range(n):
    upsum-=i-b[j]
    downsum+=b[j]
    if upsum<=downsum:
      break
  if upsum<=k:
    print(i)
    break

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)

    return divisors

N, K = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
L = make_divisors(S)
ans = 0
for i in L:
    D = []
    for a in A:
        if a % i != 0:
            D.append(a % i)
    D.sort()
    L1 = [0]
    L2 = [0]
    for j in range(len(D)):
        L1.append(L1[-1] + D[j])
        L2.append(L2[-1] + i - D[len(D)-1-j])
    L2.reverse()
    
    for j in range(len(D)+1):
        if K >= max(L1[j], L2[j]):
            ans = max(ans, i)

print(ans)

Submission status: Accepted

Solution code:

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

s = sum(A)



def solve():
    ans = 1
    idx = 1

    while idx * idx <= s:
        if s % idx == 0:
            if ok(s // idx):
                return s // idx
            if ok(idx):
                ans = idx
        idx += 1

    return ans


def ok(i):
    D = list(filter(lambda x: x != 0, [a % i for a in A]))
    D.sort()

    l = len(D)

    S = [0] * (l + 1)
    for j in range(l):
        S[j + 1] = S[j] + D[j]

    for j in range(l):
        if S[j] == i * (l - j) - (S[l] - S[j]) and S[j] <= K:
            return True

    return False


print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, K = MI()
    A = LI()

    M = sum(A)
    divs = []
    for i in range(1, int(pow(M, 0.5))+1):
        if M % i: continue
        divs.append(i)
        if i != M//i: divs.append(M//i)
    divs.sort(reverse=True)

    for d in divs:
        B = list(map(lambda x: x%d, A))
        B.sort()
        C = list(map(lambda x: d-x, B))
        # print(d, B, C)
        # print(list(accumulate(B)), list(accumulate(C)))
        Ba = list(accumulate(B))
        Ca = list(accumulate(C))
        for i in range(0, N-1):
            b = Ba[i]
            c = Ca[-1] - Ca[i]
            # print(b, c)
            if b == c and b <= K:
                print(d)
                return
    print(1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def divisors(N):
    return sorted(sum((list({n, N // n}) for n in range(1, int(N ** 0.5) + 1) if not N % n), []), reverse=True)
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
D = divisors(sum(A))
for d in D:
    L = sorted(a % d for a in A)
    if not sum(L):
        print(d)
        break
    left, right = 0, N - 1
    count = 0
    while left < right:
        if L[left] + L[right] <= d:
            next_right = right - (L[right] + L[left] == d)
            next_left = left + 1
            L[right] += L[left]
            count += L[left]
            L[left] = 0
        else:
            next_left = left
            next_right = right - 1
            m = d - L[right]
            count += m
            L[right] += m
            L[left] -= m
        left, right = next_left, next_right
    if count <= K:
        print(d)
        break

Submission status: Accepted

Solution code:
def get_divisors(x):
    i = 1
    ret = set()
    while i * i <= x:
        if x % i == 0:
            ret.add(i)
            ret.add(x // i)

        i += 1

    return ret


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

sm = sum(a)
divs = get_divisors(sm)

ans = 0
for div in divs:
    mods = [e % div for e in a]
    mods.sort()
    p = 0
    m = n * div - sum(mods)
    for mod in mods:
        p += mod
        m -= div - mod
        if p == m:
            if p <= k:
                ans = max(ans, div)
            break

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush


def solve():
    n, k = MI()
    A = LI()
    sm = sum(A)

    div = []
    for i in range(1, int(pow(sm, 0.5))+1):
        if sm % i: continue
        div.append(i)
        if i != sm //i:
            div.append(sm // i)
    ans = 1
    for d in div:
        R = [a % d for a in A]
        R.sort()
        plus = 0
        minus = 0
        for r in R:
            plus += d - r
        for r in R:
            minus += r
            plus -= d - r
            if minus == plus and plus <= k:
                ans = max(ans, d)
    print(ans)



if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    s = sum(a)
    cand = [s]
    for i in range(2, int(s ** 0.5) + 1):
        if s % i == 0:
            cand.append(i)
            cand.append(s // i)
    cand.sort(reverse=True)

    for c in cand:
        arr = [a[i] % c for i in range(n)]
        arr.sort()
        sum_r = [0] * n
        sum_r[0] = arr[0]
        for i in range(1, n):
            sum_r[i] = sum_r[i - 1] + arr[i]
        for i in range(n - 1):
            if sum_r[i] <= k:
                sum_l = c * (n - i - 1) - sum_r[-1] + sum_r[i]
                if sum_r[i] == sum_l:
                    print(c)
                    exit()

    print(1)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
def divisor(n):
    res = []
    i = 1
    while i*i <= n:
        if n%i == 0:
            res.append(i)
            if i*i != n:
                res.append(n//i)
        i += 1
    res.sort()
    return res

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
ans = 1
for d in divisor(S):
    rs = [a%d for a in A]
    rs.sort()
    Sum = [0]*(N+1)
    Sum2 = [0]*(N+1)
    for i in range(1,N+1):
        Sum[i] = Sum[i-1]+rs[i-1]
        Sum2[i] = Sum2[i-1]+(d-rs[i-1])
    for i in range(N+1):
        if Sum[i] == Sum2[N]-Sum2[i]:
            if Sum[i] <= K:
                ans = d
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


@mt
def slv(N, K, A):
    S = sum(A)
    ans = 0
    for d in divisor(S):
        r = [a%d for a in A]
        r.sort()
        lr = [0]
        rr = [0]
        for v in r:
            lr.append(lr[-1] + v)
            rr.append(rr[-1] + (d-v))
        for i in range(N):
            l = lr[i+1] - lr[0]
            r = rr[-1] - rr[i+1]
            if l == r and l <= K:
                ans = max(ans, d)
    return ans






def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

fac=sorted(factor(sum_),reverse=True)
ans=1
for x in fac:
    li=sorted(z%x for z in a)
    res=0
    cum=[0]*(n+1)
    for i in range(n):
        cum[i+1]=cum[i]+li[i]
    for i in range(1,n):
        l,r=cum[i],x*(n-i)-(cum[n]-cum[i])
        if l==r and r<=k:
            ans=max(ans,x)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def isok(x):
    que=deque(sorted(z%x for z in a))
    res=0
    while que:
        l=que[0]
        if l==0:
            que.popleft()
            continue
        r=que[-1]
        if r==0:
            que.pop()
            continue
        d=min(l,x-r)
        que[0]-=d
        que[-1]=(que[-1]+d)%x
        res+=d
    return res
        
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

fac=sorted(factor(sum_),reverse=True)
ans=1
for x in fac:
    c=isok(x)
    if c<=k:
        ans=x
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def isok(x):
    que=deque(sorted(z%x for z in a))
    res=0
    while que:
        l=que[0]
        if l==0:
            que.popleft()
            continue
        r=que[-1]
        if r==0:
            que.pop()
            continue
        d=min(l,x-r)
        que[0]-=d
        que[-1]=(que[-1]+d)%x
        res+=d
    return res
        

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

fac=set()
for i in range(1,sum_+1):
    if i*i>sum_:
        break
    if sum_%i==0:
        fac.add(i)
        fac.add(sum_//i)

fac=sorted(fac,reverse=True)
ans=1
for x in fac:
    c=isok(x)
    if c<=k:
        ans=x
        break
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
sum_a = sum(a)
ans = 0
def try_ans(target):
    remain = [i % target for i in a]
    remain.sort()
    count = 10**10
    #sum_remainは全てをマイナス側に落とし込むときの操作回数
    sum_remain = sum(remain)
    #plus_remainはプラス側に落とし込むときの操作回数
    plus_remain = 0
    for i in range(n-1,-1,-1):
        plus_remain += target - remain[i]
        sum_remain -= remain[i]
        count = min(count, max(sum_remain,plus_remain))
    return count <= k

for i in range(1,int(sum_a**0.5)+1):
    if sum_a % i == 0:
        if try_ans(i):
            ans = max(ans, i)
        if try_ans(sum_a // i):
            ans = max(ans, sum_a//i)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
cnt=1
A=sum(a)
l=[]
for i in range(1,int(A**(1/2))+1):
    if A%i!=0:continue
    l.append(i)
    if  A// i != i:
        l.append(A // i)
for i in l:
    x=[0]*n
    for j in range(n):
        x[j]=a[j]%i
    s=sum(x)
    l=0
    x.sort(reverse=True)
    for j in range(n):
        if s<=k and l<=k:
            if (s-l)%i==0:
                if i>cnt:
                    cnt=i
                break
        l+=i-x[j]
        s-=x[j]

print(cnt)

Submission status: Accepted

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

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

    # divisors.sort()
    return divisors

ans = 1

for div in make_divisors(sum(a)):
    mod_div = []
    for ai in a:
        mod_div.append(ai % div)
    mod_div.sort()

    tmp_p = n * div - sum(mod_div)
    tmp_m = 0

    for i, x in enumerate(mod_div):
        tmp_m += x
        tmp_p -= div - x
        if tmp_m == tmp_p and tmp_m <= k:
            ans = max(div, ans)

print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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


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

    divisors.sort()
    return divisors

divs=make_divisors(sum(a))
# print(divs)
ans=1
for i in range(len(divs)):
    r=[]
    d=divs[i]
    for j in range(n):
        if a[j]%d!=0:
            r.append(a[j]%d)
    r.sort()

    ruir=ruiseki(r)
    # print(d,ruir)
    # print(r)
    if ruir==[0]:
        ans=d
    for i in range(len(r)):
        hiku=ruir[i]
        tasu=-(ruir[-1]-ruir[i])+d*(len(r)-i)
        # print(hiku,tasu,ruir[-1]-ruir[i])
        if hiku%d==tasu%d and max(hiku,tasu)<=k:
            ans=d

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,input().split())
a = [int(i) for i in input().split()]

def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]
 
 
def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

c = []
fct = factorize(sum(a))
for div in divisorize(fct):
    c.append(num(div))

c.sort(reverse=True)
ans = 1
from heapq import heapify,heappush,heappop

for num in c:
  chk = 0; cnt = 0
  sp = 0
  pl = []; mi = []
  heapify(pl); heapify(mi)
  for j in a:
    m = min(j%num,num-j%num)
    chk += m
    if m == j%num:
      cnt += m
      heappush(pl,-m)
    else:
      cnt -= m
      heappush(mi,-m)
  
  if cnt != 0:
    for i in range(abs(cnt)//num):
      if cnt > 0 and pl!=[]:
        p = heappop(pl)
        chk += (num+2*p)
      elif cnt < 0 and mi!=[]:
        q = heappop(mi)
        chk += (num+2*q)
        
  if chk <= 2*k:
    ans = num
    break
    
print(ans)