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 bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = 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()
    return divisors


def main():
    n, k = get_li()
    A = get_li()
    ds = make_divisors(sum(A))
    ans = 1
    for d in ds[1:]:
        pdiff = [0] * n
        ndiff = [0] * n
        for i, a in enumerate(A):
            pdiff[i] = a % d
            ndiff[i] = a % d - d
        hoge = list(sorted(zip(pdiff, ndiff)))
        ps = [0] + [h[0] for h in hoge]
        ns = [h[1] for h in hoge] + [0]
        pacc = list(its.accumulate(ps))
        nacc = list(reversed(list(its.accumulate(reversed(ns)))))
        for p_, n_ in zip(pacc, nacc):
            if p_ + n_ == 0 and p_ <= k:
                ans = d
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    totalSum = 0
    for a in A: totalSum += a

    if K >= totalSum - A[N-1]: print(totalSum)
    else:
        divisor = []
        k = 1
        while k ** 2 <= totalSum:
            if totalSum % k == 0:
                divisor.append(k)
                if k ** 2 < totalSum: divisor.append(totalSum//k)
            k += 1

        divisor.sort(reverse = True)
        for d in divisor:
            need = []
            lenneed = 0
            for a in A:
                if a % d > 0: 
                    need.append(a % d)
                    lenneed += 1

            #print(d, need)
            if lenneed == 0:
                print(d)
                break
            else:
                possible = False
                need.sort()
                needSum = [[0, 0] for _ in range(lenneed)]
                needSum[0][0] = need[0]
                needSum[lenneed -1][1] = d - need[lenneed - 1]
                for i in range(1, lenneed):
                    needSum[i][0] = needSum[i-1][0] + need[i]
                    needSum[lenneed - 1 - i][1] = needSum[lenneed - i][1] + d - need[lenneed - i - 1]
                #print(needSum)

                for i in range(lenneed - 1):
                    if needSum[i][0] == needSum[i+1][1] and needSum[i][0] <= K:
                        possible = True
                
                if possible: 
                    print(d)
                    break

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


def get_fact(N):
  ret = set([N])
  for i in range(2,int(N**0.5)+2):
    if N%i == 0:
      ret.add(i)
      ret.add(N//i)
  return ret


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

  ## Solve
  fset = get_fact(sum(An))
  ans = 1
  for f in fset:
    Amod = [a%f for a in An]
    Amod = sorted(Amod)
    if sum(Amod[:-sum(Amod)//f]) <= K:
      ans = max(ans,f)
  return ans


if __name__ == "__main__":
  ans = main()
  print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque


def check(A, d, K):
    diff = []
    for a in A:
        if a % d != 0:
            diff.append(a % d)
    totalinc = 0
    diff.sort()
    q = deque(diff)
    cnt = 0
    while len(q):
        x = q.popleft()
        cnt += x
        totalinc += x
        while len(q) and q[-1] + totalinc >= d:
            y = q.pop()
            totalinc -= d-y
    cnt += totalinc
    return cnt <= K


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)
    divs = [1, total]
    rt = int(math.sqrt(total))
    for i in range(2, rt+1):
        if total % i == 0:
            divs.append(i)
            if i**2 != total:
                divs.append(total//i)
    ans = 0
    for d in divs:
        if check(A, d, K):
            ans = max(ans, d)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
from itertools import accumulate
def check(n):
    L = [None]*N
    for i in range(N):
        L[i] = ((A[i] % n), n - (A[i] % n))
    L.sort(key=lambda x:x[0])
    acc1 = list(accumulate([L[i][0] for i in range(N)]))
    acc2 = list(accumulate([L[i][1] for i in range(N)]))
    for i in range(N):
        if acc1[i] <= K and acc2[N-1]-acc2[i] <= K:
            return True
    return False

mx = -1
import math
for i in range(math.floor(math.sqrt(S)), 0, -1):
    if S % i == 0:
        if check (i):
            mx = max(i, mx)
        if check (S // i):
            mx = max(S // i, mx)
print(mx)

Submission status: Accepted

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

import sys
from math import sqrt
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

sm=sum(A)

def divisor_set(N: int) -> set:
    """ 約数の列挙・個数 """
    # 1とその数はデフォで入れとく
    s = {1, N}
    # 終点はルート切り捨て
    for i in range(2, int(sqrt(N))+1):
        # 割り切れるなら、iとN/iを追加
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

divs=sorted(divisor_set(sm), reverse=True)

for div in divs:
    B=[]
    for i in range(N):
        if A[i]%div!=0:
            B.append(A[i]%div)
    # mod取ったものをソート、これを前後からdivの約数に合わせていく
    B.sort()
    B=deque(B)
    cnt=0
    while len(B):
        # 先頭を引いていってdivの約数になるまでの距離
        dista=B[0]%div
        # 末尾を足していってdivの約数になるまでの距離
        distb=div-B[-1]%div
        # どちらが近いかに応じてリストBを操作する
        if dista>distb:
            B[0]-=distb
            B.pop()
            cnt+=distb
        elif dista<distb:
            B[-1]+=dista
            B.popleft()
            cnt+=dista
        elif dista==distb:
            B.pop()
            B.popleft()
            cnt+=dista
    # 操作回数がK回以内ならOK
    if cnt<=K:
        print(div)
        exit()

Submission status: Accepted

Solution code:
import sys,heapq,math,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  #resource.setrlimit(RLIMIT_STACK, (128*1024*1024,hard))

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def foo(x):
    b = []
    for y in a:
        if y%x != 0:
            b.append(y%x)
    b.sort()
    m = k
    while m>0 and len(b)>0:
        if b[0] < x-b[-1] or (len(b)==1 and b[0]<=x//2):
            if m<b[0]:
                return False
            m -= b[0]
            b[-1] += b[0]
            b = b[1:]
            #p = len(b)-1
            #while p>0 and b[p-1]>b[p]:
            #    b[p-1],b[p] = b[p],b[p-1]
        else:
            d = x-b[-1]
            if m<d:
                return False
            m -= d
            b[0] -= d
            b.pop()
            if b[0]==0:
                b = b[1:]
            #p = 0
            #while p<len(b)-1 and b[p]>b[p+1]:
            #    b[p],b[p+1] = b[p+1],b[p]
    return (len(b)==0)

n,k = inm()
a = inl()
sm = sum(a)
f = prime_division(sm)

facs = [1]
for z in f:
    b = z[0]
    e = z[1]
    newfacs = []
    for x in facs:
        for i in range(e+1):
            newfacs.append(x*(b**i))
    facs = newfacs

facs.sort(reverse=True)
for x in facs:
    if foo(x):
        print(x)
        exit()
print(1)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K, *A = map(int, open(0).read().split())

def check(d):
    r = sorted([v % d for v in A])
    r_inv = [d - v for v in r]    
    r_cs = [0] + list(accumulate(r))
    r_inv_cs = list(accumulate(r_inv[::-1]))[::-1] + [0]

    ret = False
    for i in range(N + 1):
        flg1 = r_cs[i] <= K
        flg2 = r_cs[i] == r_inv_cs[i]
        ret = (flg1 and flg2) or ret
    
    return ret

M = sum(A)
ans = 0
for i in reversed(range(1, int(M ** 0.5) + 1)):
    if M % i == 0 and check(i):
        ans = max(ans, i)
    if M % (M // i) == 0 and check(M // i):
        ans = max(ans, M // i)
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def get_prime_factorized(N):
    result    = []
    base, exp = 2, 0
    while base ** 2 <= N:
        while N % base == 0:
            N    = N // base
            exp += 1
        if exp > 0:
            result.append([base, exp])
        base, exp = base + 1, 0
    if N > 1:
        result.append([N, 1])
    return result

def re_func_divisior(prime_factorized):
    base, exp = prime_factorized.pop()
    P = re_func_divisior(prime_factorized) if prime_factorized else [[]]
    Q = [[base ** k] for k in range(exp + 1)]
    return [p + q for p in P for q in Q]

def get_list_divisor(N, reverse=True):
    try:
        prime_factorized = get_prime_factorized(N)
        res    = re_func_divisior(prime_factorized)
        result = []
        for k in res:
            for i, x in enumerate(k):
                if i == 0:
                    r = x
                else:
                    r *= x
            result.append(r)
        result = sorted(result, reverse=reverse)
    except:
        result = [N]
    return result


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

X = get_list_divisor(sum(A))

is_break = False

for x in X:
    POS = sorted([a % x for a in A if a % x != 0])
    NEG = [x - pos for pos in POS]
    POS_cumsum = np.cumsum(POS)
    NEG_cumsum = np.cumsum(NEG[::-1])[::-1]
    for sep in range(1, len(POS)):
        if POS_cumsum[sep-1] == NEG_cumsum[sep] and POS_cumsum[sep-1] <= K:
            is_break = True
            break
    if is_break:
        break

print(x)

Submission status: Accepted

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

sumA = sum(A)
divisors = []
for i in range(1, sumA + 1):
    if i * i > sumA:
        break
    if sumA % i != 0:
        continue
    divisors.append(i)
    if sumA // i != i:
        divisors.append(sumA // i)

divisors.sort(reverse=True)

ans = 0
for d in divisors:
    costs = [a % d for a in A]
    costs.sort()
    if sum(costs[:N - sum(costs) // d]) <= K:
        print(d)
        break

Submission status: Accepted

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

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

    return divisors
sum_num = sum(a_list)
a_list.sort()
div = divisors(sum_num)
div.sort(reverse=True)
ans = 1
from itertools import accumulate
for d in div:
    mod = []
    if d == 1:
        break
    for a in a_list:
        mod.append(a % d)
    mod.sort()
    acc_m = list(accumulate(mod))
    modd = []
    for i in range(N):
        modd.append(d-mod[i])
    acc_p = list(accumulate(modd))
    flag = False
    for i in range(N-1):
        p_sum = acc_p[-1] - acc_p[i]
        n_sum = acc_m[i]
        if p_sum == n_sum and p_sum <= K:
            flag = True
    if flag:
        ans = d
        break

print(ans)

Submission status: Accepted

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

    divisors.sort()
    return divisors

N,K = map(int,input().split())
A = list(map(int,input().split()))
D = sum(A)
D = make_divisors(D)[::-1]

for d in D:
    a = []
    for i in range(N):
        a.append(A[i]%d)
    k = 0
    M = max(a)
    while k <= K and M != 0:
        i = 0
        j = 0
        m = d
        M = 0
        for l in range(N):
            if 0 < a[l] < m:
                m = a[l]
                i = l
        for l in range(N-1,-1,-1):
            if a[l] > M:
                M = a[l]
                j = l
        if m == d:
            break
        if m <= d-M:
            a[i] = 0
            a[j] += m
            a[j] %= d
            k += m
        else:
            a[i] -= d-M
            a[i] %= d
            a[j] = 0
            k += d-M
    if k <= K:
        break

print(d)

Submission status: Accepted

Solution code:
#coding:utf-8
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)
    return divisors
ls = sorted(make_divisors(sum(A)))[::-1]


def cost(ls,n):
    ls = sorted(ls)
    #print (ls)
    left = 0
    right = len(ls)-1
    sm = 0
    while left < right:
        if (ls[left] + ls[right])<=n:
            op = ls[left]
            ls[left] = 0
            ls[right] += op
            left += 1
        else:
            op = n-ls[right]
            ls[right] = 0
            right -= 1
            ls[left] -= op
            if ls[left] == 0:
                left += 1


        sm += op
        #print (left,right)
        #print (ls)
        #print (sm)
    return sm

    

for n in ls:
    if cost([a%n for a in A],n) <= K:
        print (n)
        exit()

Submission status: Accepted

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

def yakusuu(a):
    yakusuu=set()
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            yakusuu.add(i)
            yakusuu.add(a//i)
    yakusuu=sorted(list(yakusuu),reverse=True)
    return yakusuu

y=yakusuu(sum(a))

from itertools import accumulate
flag=0
for i in y:
    B=[A%i for A in a]
    C=sorted(B,reverse=True)
    B=list(accumulate(sorted(B)))
    C=list(reversed(list(accumulate([(i-c)%i for c in C]))))[1:]+[0]
    for j in range(n):
        if B[j]==C[j]:
            if B[j]<=k:
                print(i)
                flag=1
                break
            break
    if flag==1:
        break

Submission status: Accepted

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

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=sum(arr)
ans=1
d=div(s)
for val in d:
  arr=sorted(arr,key=lambda x:x%val)
  parr=[]
  narr=[]
  for num in arr:
    narr.append(num%val)
    parr.append(val-num%val)
  for i in range(n-1):
    parr[i+1]+=parr[i]
    narr[i+1]+=narr[i]
  for i in range(n-1):
    ncnt=narr[i]
    pcnt=parr[-1]-parr[i]
    if ncnt!=pcnt:
      continue
    else:
      if pcnt<=k:
        ans=max(ans,val)
print(ans)

Submission status: Accepted

Solution code:
def main():
     n,k=map(int,input().split())
     a=list(map(int,input().split()))
     sum_a=sum(a)
     anskoho=[]
     for i in range(1,int(sum_a**0.5)+1):
          if sum_a%i==0:
               anskoho+=[i,sum_a//i]
     anskoho.sort(reverse=True)
     
     for i in anskoho:
          a_sub=[j%i for j in a]
          a_sub.sort()
          
          sum_L,sum_R=sum(a_sub),0
          sakai=n-1
          while sum_L!=sum_R:
               sum_L-=a_sub[sakai]
               sum_R+=i-a_sub[sakai]
               sakai-=1
          if sum_L<=k:
               print(i)
               break
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()
    return divisors

N,K = map(int,input().split())
A = list(map(int,input().split()))
D = sum(A)
D = make_divisors(D)[::-1]

for d in D:
    a = []
    for i in range(N):
        if A[i]%d != 0:
            a.append(A[i]%d)
    a.sort()
    b = [d-x for x in a]
    b.sort()

    c1 = [0]*(len(a)+1)
    for i in range(len(a)):
        c1[i] = a[i]+c1[i-1]
    c2 = [0]*(len(b)+1)
    for i in range(len(b)):
        c2[i] = b[i]+c2[i-1]

    k = float('inf')
    for i in range(len(a)):
        if c1[i] == c2[len(a)-2-i]:
            k = c1[i]
            break
    if k <= K:
        break
print(d)

Submission status: Accepted

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

# 約数の全列挙
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)
    divisors.sort(reverse = True)  # ソート
    return divisors

ansList = divisors(sumA)
ans = 1

for div in ansList :
    res = [a % div for a in A]
    res.sort(reverse=True)

    sumCount = sum(res)
    b = 0
    for r in res :
        sumCount -= r
        b += div - r
        if sumCount == b :
            if sumCount <= K :
                ans = div
                break
    else :
        continue
    break

print(ans)

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

goukei = sum(A)
candidate = make_divisors(goukei)
tmp_goukei = 0
operation = 0
answer = 1
for c in candidate:
    mod_c = sorted([a % c for a in A], reverse=True)
    sum_c = sum(mod_c)
    #print(c, mod_c, sum_c)
    if sum_c % c != 0:
        continue
    counter = 0
    for a in mod_c:
        sum_c -= c
        counter += c - a
        if sum_c <= 0:
            break
    #print(c, a, counter)
    if counter <= K:
        answer = c
        break
    else:
        tmp_goukei = 0
        operation = 0
print(answer)

Submission status: Accepted

Solution code:
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def can_make(div):
    mods = []
    for a in A:
        mods.append(a % div)

    mods.sort()
    left = 0
    right = len(mods) - 1
    k = K
    while left <= right and k >= 0:
        while left < len(mods) and mods[left] % div == 0:
            left += 1
        while right >= 0 and mods[right] % div == 0:
            right -= 1
        if right < left:
            return True

        m = div - mods[right]
        if mods[left] >= m:
            mods[left] -= m
            mods[right] = 0
            right -= 1
            k -= m
        else:
            mods[right] += mods[left]
            k -= mods[left]
            mods[left] = 0
            left += 1
    return k >= 0


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

# 答えは絶対 A の合計の約数になる
divs = get_divisors(sum(A))
for div in sorted(divs, reverse=True):
    if can_make(div):
        print(div)
        exit()
assert False

Submission status: Accepted

Solution code:
def all_divisor(n):
    small = [1]
    large = [n]
    for i in range(2, int(n ** 0.5) + 1):
        if not (n % i):
            small.append(i)
            large.append(n//i)
    large.reverse()
    divisor = small + large
    return divisor

n, k = map(int, input().split())
a = list(map(int, input().split()))
sum_a = sum(a)
divisor = all_divisor(sum_a)
ans = 1
for i in reversed(divisor):
  t = 0
  b = []
  d = 0
  for j in a:
    b.append(j % i)
  c = sum(b)
  b.sort()
  for x in reversed(b):
    c -= x
    d += i - x
    if c == d:
      if c <= k:
        print(i)
        exit()
print(ans)

Submission status: Accepted

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

nums = A[:]

sum_n = sum(nums)

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

divisors = sorted(list(make_divisors(sum_n)), reverse=True)
#print('DIV', divisors)


for d in divisors:
    mod_nums = list(map(lambda x: x%d, nums[:]))
    mod_nums = sorted(mod_nums)
    #print(mod_nums)
    x = 10**10
    for i in range(0, len(mod_nums)+1):
        if sum(mod_nums[:i]) == sum(list(map(lambda x: d-x, mod_nums[i:]))):
            x = sum(mod_nums[:i])
            break
    #print(d, x)
    if x <= K:
        ans = d
        break
            
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

sumA = sum(A)
yakusu = []
yakusu2 = []
t = 1
while t <= sumA ** 0.5:
	if sumA % t == 0:
		yakusu.append(t)
		yakusu2.append(sumA // t)
	t+=1
while len(yakusu) > 0:
	yakusu2.append(yakusu.pop())

#print(yakusu2)
for num in yakusu2:
	sa = []
	for i in range(N):
		syo = A[i]//num
		sa.append(A[i]-num*syo)
	sa.sort()
	judge = 0
	wa = 0
	loc = 0
	for i in range(len(sa)):
		#print(wa + sa[i])
		if (wa + sa[i]) <= K:
			wa += sa[i]
			loc = i
		else:
			break
	if loc == len(sa) - 1:
		print(num)
		exit()
	else:
		for i in range(loc+1, len(sa)):
			sa[i] = num - sa[i]
	#print(num, sa, loc)
	if sum(sa[loc+1:]) <= K:
		print(num)
		exit()

Submission status: Accepted

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

for d in div:
	b = [x%d for x in a if x%d != 0]
	if not b:
		print(d)
		break
	b.sort(key=lambda x: x%d)
	y, z = 0, d*len(b)-sum(b)
	res = 10**30
	for x in b:
		y += x
		z -= d-x
		res = min(res, max(y, z))
	if res <= k:
		print(d)
		break

Submission status: Accepted

Solution code:
from math import sqrt
class Factorizer:
    def __init__(self):
        self.primes_ceil = 5
        self.primes = [2,3]

    def find_primes(self, primes_ceil):
        if primes_ceil <= self.primes_ceil:
            return self.primes

        prev_primes_ceil, self.primes_ceil = self.primes_ceil, primes_ceil
        r, m = prev_primes_ceil//6, prev_primes_ceil%6
        if m <= 1:
            i = r*6 + 1
            mod_flag = True
        else:
            i = r*6 + 5
            mod_flag = False

        while i < self.primes_ceil:
            sieve = True
            for p in self.primes:
                if p*p > i:
                    break
                elif i % p == 0:
                    sieve = False
                    break
            if sieve:
                self.primes.append(i)
            if mod_flag:
                i += 4
                mod_flag = False
            else:
                i += 2
                mod_flag = True

        return self.primes

    def __call__(self, n):
        if (self.primes_ceil-1)**2 < n:
            self.find_primes(int(sqrt(n))+1)
        factors = []
        powers = []
        for p in self.primes:
            if p * p > n:
                break
            elif n % p == 0:
                n //= p
                k = 1
                while n % p == 0:
                    n //= p
                    k += 1
                factors.append(p)
                powers.append(k)
        if n > 1:
            factors.append(n)
            powers.append(1)
        return factors, powers

inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
S = sum(A)
factorize = Factorizer()

ft, pw = factorize(S)
n = len(ft)
denominators = [1]
for i in range(n):
    new_denominators = []
    for d in denominators:
        for p in range(pw[i]+1):
            new_denominators.append(d*(ft[i]**p))
    denominators = new_denominators
denominators.sort(reverse=True)

for d in denominators:
    mods = [a%d for a in A]
    mods.sort()
    Sm = sum(mods)
    h = Sm // d
    minK = min(d*(h+1)-sum(mods[N-h-1:]), sum(mods[:N-h]))
    if minK <= K:
        print(d)
        exit()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, K = [int(a) for a in input().split()]
    # H = [
    #     int(input())
    #     for _ in range(N)
    # ]
    A = sorted([int(a) for a in input().split()])
    SUM = sum(A)

    # bubu = [0] * N
    # max_K = 0
    # s = 0
    # for i, a in enumerate(A):
    #     s += a
    #     bubu[i] = s
    # for i in range(N):
    #     if bubu[i] >= K:
    #         max_K = N - i
    #         break
    # print("A", A)
    # print("bubu", bubu)
    # print(max_K)
    # print("SUM:", SUM)

    def check(nn):
        r = []
        for a in A:
            amari = a % nn
            if amari == 0:
                r.append((0, 0))
            else:
                r.append((amari, amari - nn))
            # if amari<nn-amari:
            #     r.append(amari)
            # else:
            #     r.append(amari-nn)
        # print(r)
        r = sorted(r, key=lambda a: a[0])
        ss = sum(a for a, _ in r)
        sss = ss // nn
        rsum = sum(a for a, b in r[:-sss])
        lsum = -sum(b for _, b in r[-sss:])
        vvv = max(rsum, lsum)
        # print(ss, sss, rsum, lsum)
        if vvv <= K:
            return True
        else:
            return False

    sq = int(math.sqrt(SUM))
    aaa = []
    for n in range(1, sq + 1):
        # print("@@", n)
        if SUM % n != 0:
            continue
        aaa.append(n)
        ddd = SUM // n
        # print("maybe:", ddd)
        if check(ddd):
            print(ddd)
            return
        # print(n, ddd)

    for n in reversed(aaa):
        # print("maybe:", n)
        if check(n):
            print(n)
            return
        # print(n)


if __name__ == '__main__':
    main()