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:
n, k = map(int, input().split())
A = list(map(int, input().split()))
s = sum(A)
def md(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
P = md(s)
def test(x):
  L = sorted([a%x for a in A])
  M = sum(L)
  c = M//x
  for _ in range(c):
    M -= L.pop()
  return M <= k

for p in P:
  if test(p):
    print(p)
    break

Submission status: Accepted

Solution code:
# まず, 答えは総和の約数となる
# 恐らく約数ごとに条件が成り立つか調べることになる

# 答えをdと仮定したとき, 各値はdの倍数となる
# 総和をどのように振り分けたらK以下で全てdの倍数になるか調べるのは無理
# そこでmod(d)で考えることにする
# 各値についてdで割った余りを記録していく
# それをソートして両端から-1/+1していけば
# 必ず全て0にでき, その操作回数もO(N)で分かる

# コードは累積和で境界を求めてる

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from fractions import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2
        # 約数のリストを返す

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

    for i in kouho[::-1]:
        nega = [0]*n
        posi = [0]*n
        for j in range(n):
            posi[j] = a[j] % i
        posi.sort()
        for j in range(n):
            nega[j] = posi[j] - i
        posi = [0] + posi
        nega = [0] + nega
        posi = list(accumulate(posi))
        nega = list(accumulate(nega))
        for j in range(1, n+1):
            if posi[j] == -(nega[-1]-nega[j]):
                total = posi[j]
                break
        if total <= k:
            print(i)
            break
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from fractions import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2
        # 約数のリストを返す

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

    for i in kouho[::-1]:
        nega = [0]*n
        posi = [0]*n
        for j in range(n):
            posi[j] = a[j] % i
        posi.sort()
        for j in range(n):
            nega[j] = posi[j] - i
        posi = [0] + posi
        nega = [0] + nega
        posi = list(accumulate(posi))
        nega = list(accumulate(nega))
        total = 10**10
        for j in range(1, n+1):
            total = min(total, max(posi[j], -(nega[-1]-nega[j])))
        if total <= k:
            print(i)
            break
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

def getDivisors(x):
    anss = set()
    for d in range(1, int(x**0.5)+1):
        if x%d == 0:
            anss.add(d)
            anss.add(x//d)
    return sorted(anss)

sumA = sum(As)
divs = getDivisors(sumA)

def check(x):
    Bs = [A%x for A in As if A%x]
    if not Bs:
        return True
    Bs.sort()
    accNums = list(accumulate(Bs))
    accNumRevs = list(accumulate([x-B for B in reversed(Bs)]))[::-1]
    for i in range(len(Bs)-1):
        if accNums[i] == accNumRevs[i+1] and accNums[i] <= K:
            return True
    return False

for div in reversed(divs):
    if check(div):
        print(div)
        break

Submission status: Accepted

Solution code:
N,K,*A = map(int, open(0).read().split())
pls = []
S = sum(A)
for i in range(1,int(S**0.5)+1):
  if S%i==0:
    pls.append(i)
    pls.append(S//i)
pls.sort()
ans = 0
for p in pls:
  B = [a%p for a in A]
  B.sort()
  i = 0
  j = N-1
  cnt = K
  while i<N:
    if B[i]!=0:
      break
    i += 1
  else:
    ans = p
    continue
  while True:
    a = B[i]
    b = B[j]
    if a<p-b:
      if cnt<a:
        break
      B[j] += a
      cnt -= a
      i += 1
    elif a>p-b:
      if cnt<p-b:
        break
      B[i] -= p-b
      cnt -= p-b
      j -= 1
    else:
      if cnt<a:
        break
      cnt -= a
      i += 1
      j -= 1
    if i>=j:
      ans = p
      break
print(ans)

Submission status: Accepted

Solution code:
from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
import unittest
from io import StringIO
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    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:  # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)

        divisors.sort(reverse=True)  # ソートしたけりゃして
        return divisors

    M = make_divisors(sum(A))

    def main():
        for i in M:
            AA = [0]*N
            age = 0
            # delete = 0
            for j in range(N):
                AA[j] = A[j] % i
                #if AA[j] == 0:
                    # delete += 1
                    # age -= i
                age += i-AA[j]
            AA.sort()

            times = 10**9
            sage = 0
            for j in range(0,N-1):
                sage += AA[j]
                age -= i-AA[j]
                if sage % i == age % i:
                    times = min(max(sage, age), times)
            if times <= K:
                return i
    print(main())

resolve()

Submission status: Accepted

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

cands = []
for x in range(1, int(s ** 0.5) + 1):
    if s % x == 0:
        cands.append(x)
        if x != s // x:
            cands.append(s // x)

cands.sort(reverse=True)
#print(cands)

ans = 0
for cand in cands:
    b = [a[i] % cand for i in range(n)]
    b.sort()
    sb = [0 for _ in range(n+1)]
    for i in range(n):
        sb[i+1] = sb[i] + b[i]
    #print(cand, sb)

    flg = False
    for i in range(n+1):
        x = max(sb[i], cand * (n - i) - (sb[n] - sb[i]))
        #print(i, sb[i], cand * (n - i) - (sb[n] - sb[i]))
        if x <= k:
            flg = True
            break

    if flg:
        print(cand)
        break

Submission status: Accepted

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

m = sum(a)
s = set()
i = 1
while i * i <= m:
    if m % i == 0:
        s |= set([i, m // i])
    i += 1

ans = 0
for i in s:
    b = [j % i for j in a]
    b.sort()
    c = [0]
    for j in b:
        c.append(c[-1] + j)
    d = [0]
    for j in reversed(b):
        d.append(d[-1] + (i-j))
    d = list(reversed(d))

    for j in range(n+1):
        if (c[j] - d[j]) % i == 0:
            if max(c[j], d[j]) <= k:
                ans = max(ans, i)
print(ans)

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    s = sum(a)
            
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)

        return divisors
            
    div = make_divisors(s)
    
    div.sort()
    ans = 1
    for use in div:
        rest = -(a%use)
        rest = np.sort(rest)
        ch = -sum(rest)//use
        do = use*ch+sum(rest[:ch])
        if do <= K:
            ans = use
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    SUM=sum(A)
    l=[]
    for i in range(1,int(SUM**0.5)+1):
        if SUM%i==0:
            l.append(i)
            l.append(SUM//i)
    ans=0
    for x in l:
        B=[A[i]%x for i in range(N)]
        B.sort()
        S_m=[0]*(N+1)
        S_p=[0]*(N+1)
        for i in range(N):
            S_m[i+1]=S_m[i]+B[i]
            S_p[i+1]=S_p[i]+x-B[i]
        for i in range(N+1):
            if max(S_m[i],S_p[N]-S_p[i])<=K:
                ans=max(ans,x)
                break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    SUM=sum(A)
    l=[]
    for i in range(1,int(SUM**0.5)+1):
        if SUM%i==0:
            l.append(i)
            l.append(SUM//i)
    ans=0
    for x in l:
        B=[A[i]%x for i in range(N)]
        B.sort()
        S_m=[0]*(N+1)
        S_p=[0]*(N+1)
        for i in range(N):
            S_m[i+1]=S_m[i]+B[i]
            S_p[i+1]=S_p[i]+x-B[i]
        for i in range(N+1):
            if max(S_m[i],S_p[N]-S_p[i])<=K:
                ans=max(ans,x)
                break
    if SUM==0:
        print(K)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
x=sum(l)
def f(m,k,l):
    l=[i%m for i in l]
    l.sort()
    if sum(l[:n-sum(l)//m])<=k:
        return True
ans=1
for i in range(1,int(x**0.5)+1):
    if x%i:
        continue
    if f(x//i,k,l):
        print(x//i)
        break
    elif f(i,k,l):
        ans=i
else:
    print(ans)

Submission status: Accepted

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

def get_divisors(num):
    f_divs, l_divs = [], []
    for i in range(1, int(num**0.5)+1):
        if not num % i:
            f_divs.append(i)
            if i != num // i:
                l_divs.append(num // i)
    return f_divs + l_divs[::-1]

divs = get_divisors(sum(a))
ans = 1

def evl(d):
    rem = [x % d for x in a]
    rem.sort()
    s = sum(rem)
    c = 0
    for i, x in enumerate(rem):
        c += x
        if c == d*(n-i-1) - (s-c):
            return c <= k
    return False

for d in divs[::-1]:
    if evl(d):
        print(d)
        break

Submission status: Accepted

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
divs = make_divs(S)
ans = 0

for d in divs:
    B = [Ai%d for Ai in A]
    B.sort()
    l, r = 0, N-1
    cnt = 0
    
    while l!=r:
        t = min(B[l], d-B[r])
        B[l] -= t
        B[r] += t
        cnt += t
        
        if B[l]==0:
            l += 1
        else:
            r -= 1
    
    if cnt<=K:
        ans = max(ans, d)

print(ans)

Submission status: Accepted

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

sum_a=sum(alist)
alist.sort()
#print(sum_a,alist)

#M=1の場合にも対応
divisor_set=set()
for i in range(1,int(sum_a**0.5)+1):
  if sum_a%i==0:
    divisor_set.add(i)
    divisor_set.add(sum_a//i)
divisor_list=list(divisor_set)
divisor_list.sort()
#print(divisor_list)

answer=0
for d in divisor_list:
  rlist=[]
  for a in alist:
    rlist.append((a%d,(d-a%d)%d))
  rlist.sort()
  
  s1list,s2list=[0],[0]
  for r1,r2 in rlist:
    s1list.append(s1list[-1]+r1)
    s2list.append(s2list[-1]+r2)
  #print(d,s1list,s2list)
  
  for i in range(len(rlist)):
    r1sum=s1list[i]
    r2sum=s2list[-1]-s2list[i]
    if r1sum==r2sum and r1sum<=K:
      answer=d
      break
      
print(answer)

Submission status: Accepted

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

S = sum(A)
#print(S)

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

S_div = make_divisors(S)

mod = []
for _ in range(N):
  mod.append(0)

ans = 1
for i in range(1,len(S_div)):
  for j in range(N):
    mod[j] = A[j] % S_div[i]
  group = sum(mod)//S_div[i]
  mod.sort(reverse=True)
  Ktmp = S_div[i]*group - sum(mod[:group])
  if Ktmp <= K:
    ans = max(ans,S_div[i])

print(ans)

Submission status: Accepted

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

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

for i in range(len(D)):
    B = {}
    for j in range(n):
        try:
            B[A[j] % D[i]] += 1
        except:
            B[A[j] % D[i]] = 1
    C = list(B.items())
    C.sort()
    # print(D[i], C)
    E = []
    for j in range(len(C)):
        E.append([C[j][0], C[j][1]])
    nn = n
    c = 0
    
    l = 0
    r = len(E)-1
    ls = 0
    rs = 0
    while nn > 0:
        if ls <= rs:
            ls += E[l][0]
            E[l][1] -= 1
            nn -= 1
            if E[l][1] == 0:
                l += 1
        else:
            rs += D[i] - E[r][0]
            E[r][1] -= 1
            nn -= 1
            if E[r][1] == 0:
                r -= 1
    # print(ls,rs)
    if ls <= k:
        print(D[i])
        break

Submission status: Accepted

Solution code:


import itertools

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 resolve():
    N,K = map(int,input().split())
    A= list(map(int,input().split()))

    S = sum(A)
    
    divs = make_divisors(S)

    for d in divs[::-1]:
        r=[i%d for i in A]
        r.sort() 
        ruiseki = list(itertools.accumulate(r))
        for i,v in enumerate(ruiseki):
            b = ruiseki[-1]-v
            bb = (N-1-i)*d-b
            if v <= K and v == bb:
                print(d)
                return




resolve()

Submission status: Accepted

Solution code:
import numpy as np

def getDivisor(n):
    divisor = []
    tmp = n
    for i in range(2, int(n**0.5)+1):
        cnt = 1
        d = [1,]
        while tmp%i == 0:
            d.append(i**cnt)
            tmp //= i
            cnt += 1
        if cnt > 1:
            divisor.append(d)
    if tmp != 1:
        divisor.append([1,tmp])
    if divisor == []:
        divisor.append([1,n])
        
    divisor_mat = np.matrix(1) 
    for d in divisor:
        d = np.matrix(d)
        mat = []
        for dcol in divisor_mat:
            mat.append(dcol.T * d)
        divisor_mat = np.concatenate(mat)
    divisor_mat = np.array(divisor_mat.flatten())
    divisor_mat = np.array(divisor_mat[0].tolist())
    divisor_mat.sort()
    return divisor_mat

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

a = np.array(a)
sum_a = a.sum()
divisor = getDivisor(sum_a)
for d in divisor[::-1]:
  tmp = a % d
  idx = tmp.sum() // d
  tmp.sort()
  num_op = tmp[:-idx].sum()
  if num_op <= k:
    break
print(d)

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)
    s = Divisor_Set(a_sum)
    ans = 1
    for v in s:
        a_mod = [x%v for x in a]
        a_mod.sort()
        for i in range(1, n):
            a_mod[i] += a_mod[i-1]
        for i in range(n):
            l, r = a_mod[i], v*(n-i-1) - (a_mod[-1] - a_mod[i])
            if l == r and r <= k:
                if ans < v:
                    ans = v
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = 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)
    return divisors


def solve():
    N, K = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    divs = make_divisors(sum(A))
    divs.sort(reverse=True)
    
    ans = 1
    for div in divs:
        if div == 1:
            break
        a_mods = [ai % div for ai in A]
        a_mods.sort(reverse=True)
        sum_mods = sum(a_mods)
        c = sum_mods // div
        d = sum_mods - sum(a_mods[:c])
        if d <= K:
            ans = div
            break
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
def divisor_all(n): # 約数全列挙
    l = [1,n]
    for i in range(2,int(pow(n,1/2))+1):
        if n % i == 0:
            if i == n//i:
                l.append(i)
            else:
                l.append(i)
                l.append(n//i)
    l.sort(reverse=True)
    return l # list
D = divisor_all(sum(A))
def accumulater1D(A): # B:list[int]
    B = [0]*len(A)
    B[0] = A[0]
    for i in range(1,len(B)):
        B[i] = B[i-1]+A[i]
    return B # Aの1次元累積和
import bisect
ans = 0

for d in D:
    R = [A[i]%d for i in range(N) if A[i]%d!=0]
    nr = len(R)
    
    R.sort()
    if len(R)==0:
        ans = d
        break
    LR = accumulater1D(R)
    RR = list(reversed(accumulater1D([d-R[nr-1-i] for i in range(nr)])))
    
    for i in range(nr-1):
        if LR[i]==RR[i+1]:
            if LR[i]<=K:
                ans = d
                break
    if ans != 0:
        break
print(ans)

Submission status: Accepted

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

def search(x):
    ml = []
    for i in a:
        ml.append(i%x)
    ml.sort(reverse = True)
    ms = sum(ml)
    count = 0
    i = 0
    while k > count and ms > count:
        mi = x-ml[i]
        if k >= mi:
            count += mi
            ms -= ml[i]
            
        else:
            break
        i += 1

    if k >= count and count == ms:
        return True
    else:
        return False

for i in dl:
    
    if search(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


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

    M = sum(A)
    table = set()
    i = 1
    while i * i <= M:
        if M % i == 0:
            table.add(i)
            table.add(M // i)
        i += 1

    res = 1
    for p in table:
        B = list(map(lambda x: x%p, A))
        B.sort()
        
        forward = [0]*N
        forward[0] = B[0]
        for j in range(1,N):
            forward[j] = forward[j-1] + B[j]
        
        back = [0]*N
        if B[j] != 0:
            back[N-1] = p - B[j]
        for j in reversed(range(N-1)):
            if B[j] == 0:
                back[j] = back[j+1]
            else:
                back[j] = back[j+1] + p - B[j]
        
        for j in range(N-1):
            if forward[j] == back[j+1] and forward[j] <= K:
                res = max(res, p)
    
    print(res)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 解説AC
from collections import deque

def check(d:int):
    """ K回以下の操作でAがdの倍数となるか判定する """
    mod = deque(sorted([a % d for a in A if (a % d != 0)]))

    ans = 0
    while mod:
        modmin = mod.popleft() # modの最小値

        # modmin -> 0 を考える
        ans += modmin
        while modmin:
            if not mod: return False # modmin -> 0 にできない
            modmax = mod.pop()
            sub = d - modmax # modmax -> d にする操作回数
            if sub <= modmin:
                # modmin -> 0 の方が操作回数が必要な場合
                modmin -= sub
            else:
                # modmax -> d の方が操作回数が必要な場合
                # (※ modmax > d となることはない)
                modmax += modmin
                if modmax % d != 0:
                    mod.append(modmax)
                modmin = 0
    
    return True if (ans <= K) else False
    

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

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

sumA_divisors = make_divisors(sum(A))

ans = 0
for d in sumA_divisors:
    if check(d):
        ans = d

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().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(reverse = True)
    return divisors
pr = make_divisors(sum(a))
def sol(p):
    mo = []
    pl = []
    for i in a:
        if i%p != 0:
            mo += [i%p]
            pl += [p-i%p]
    mo.sort(); pl.sort()
    m = 0; c = sum(pl)
    ln = len(mo)
    for i in range(ln):
        m += mo[i]
        c -= pl[ln-i-1]
        if max(m,c) <= k and m%p == c%p:
            return True
    return False
for p in pr:
    if sol(p):
        res = p
        break
else:
    res = 1
print(res)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().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(reverse = True)
    return divisors
pr = make_divisors(sum(a))
def sol(p):
    mo = []
    pl = []
    for i in a:
        if i%p != 0:
            mo += [i%p]
            pl += [p-i%p]
    mo.sort(); pl.sort()
    m = 0; c = sum(pl)
    ln = len(mo)
    for i in range(ln):
        m += mo[i]
        c -= pl[ln-i-1]
        if max(m,c) <= k and m == c:
            return True
    return False
for p in pr:
    if sol(p):
        res = p
        break
else:
    res = 1
print(res)

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

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

    from itertools import accumulate
    divs = trial_division(sumA)
    ans = 0
    for d in divs:
        R = [a % d for a in A if a % d != 0]
        R.sort()
        S = [acc for acc in accumulate(R)]
        M = len(S)
        # print(d, R, S)
        if M == 0:
            ans = max(ans, d)
            continue
        for i in range(M-1):
            ne = S[i]
            po = d*(M-1-i) - (S[M-1] - S[i])
            if po == ne and po <= K:
                ans = max(ans, d)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

div_small = []
div_large = []
for p in range(1, int(S**0.5)+1):
    if S % p == 0:
        div_small.append(p)
        if S // p != p:
            div_large.append(S//p)
div_large += div_small[::-1]

for d in div_large:
    R = sorted([a % d for a in A])
    SR = sum(R)
    acc = tuple(accumulate(R))

    for i, l in enumerate(acc):
        r = d*(N-i-1)-(SR-l)
        if l == r:
            if l <= K:
                print(d)
                sys.exit()
            else:
                break

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def ok(f):
        bb=[a%f for a in aa]
        bb.sort()
        i,j=0,n-1
        s=t=0
        while i<=j:
            if s>t:
                t+=f-bb[j]
                j-=1
            else:
                s+=bb[i]
                i += 1
        return s<=k

    n,k=MI()
    aa=LI()
    s=sum(aa)
    ff=[]
    for d in range(1,s+1):
        if d**2>s:break
        if s%d==0:
            ff.append(d)
            ff.append(s//d)
    if ff[-1]==ff[-2]:ff.pop()
    ff.sort(reverse=True)
    for f in ff:
        if ok(f):
            print(f)
            break

main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def fact(n):
        if n < 4:
            return [n,1]
        i = 2
        res = [1,n]
        while i*i <= n:
            if n%i == 0:
                res.append(i)
                m = n//i
                if m != i:
                    res.append(m)
            i += 1
        res.sort(reverse = True)
        return res
    n,k = LI()
    a = LI()
    s = sum(a)
    f = fact(s)
    for i in f:
        s = [j%i for j in a]
        s.sort()
        s = list(accumulate(s))
        l = 0
        r = n
        while r > l+1:
            j = (l+r) >> 1
            sl = s[j]
            sr = i*(n-j-1)-s[-1]+s[j]
            if sl <= sr:
                l = j
            else:
                r = j
        sl = s[l]
        sr = i*(n-l-1)-s[-1]+s[l]
        if sl == sr:
            if sl <= k:
                print(i)
                return
    return

#Solve
if __name__ == "__main__":
    solve()