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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
x = [1]
for i in range(2, int(S**0.5)+1):
    if S % i == 0:
        x.append(i)
        x.append(S//i)
x.append(S)
for g in x[::-1]:
    B = [a%g for a in A]
    B.sort()
    S1 = sum(B)
    S2 = 0
    for i in range(N)[::-1]:
        S1 -= B[i]
        S2 += g-B[i]
        if S1 == S2:
            if S % g == 0 and S1 <= K:
                print(g)
                exit()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
x = [1]
for i in range(2, int(S**0.5)+1):
    if S % i == 0:
        x.append(i)
        x.append(S//i)
x.append(S)
for g in x[::-1]:
    B = [a%g for a in A]
    B.sort()
    S1 = sum(B)
    S2 = 0
    for i in range(N)[::-1]:
        S1 -= B[i]
        S2 += g-B[i]
        if S1 == S2:
            if S % g == 0 and S1 <= K:
                print(g)
                exit()
            else:
                break

Submission status: Wrong Answer

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()))

  ## Prepare
  fset = get_fact(sum(An))
  ans = 1
  for f in sorted(fset):
    Amod = []
    for a in An:
      if a%f > 0:
        Amod.append(a%f)
    if len(Amod)==0:
      ans = f
    else:
      for i in range(1,len(Amod)):
        Amod[i] += Amod[i-1]
      for i in range(len(Amod)):
        if max(Amod[i],abs(f*(N-i-1)-Amod[-1]-Amod[i])) <= K:
          ans = f
  return ans


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

Submission status: Wrong Answer

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

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

sumA = sum(A)
divs = make_divisors(sumA)[::-1]
# 何回操作しても総和が変わらないので，すべての要素を割り切る正の整数は，総和の約数
# よってこれだけ試す

for d in divs:
  B = [a%d for a in A]
  B.sort()
  Bcumsum = list(accumulate(B))
  nBcumsum = list(accumulate([b-d for b in B][::-1]))[::-1]
  for i in range(len(B)-1):
    if Bcumsum[i]==-nBcumsum[i+1]:
      if Bcumsum[i]<=K:
        print(d)
        exit()

Submission status: Wrong Answer

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

s = 2
l = [0]*n
maxs = 0
suma = sum(a)
while s < max(a)+k+1:
    if sum(a)%s == 0:
        for i in range(n):
            l[i] = a[i]%s
        l.sort()
        sml = sum(l)
        ns = sml//s
        if sml%s == 0 and -sum(l[len(l)-ns:len(l)])+ns*s<=k:
            maxs = s
        s = s + 1
    else:
        s = s + 1
print(maxs)

Submission status: Wrong Answer

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

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

#print(make_divisors(sum(A)))
for d in make_divisors(sum(A)):
  if d==1:
    print(d)
    exit()
  A_ = [a%d for a in A if a%d]
  A_.sort()
  left, right = 0, len(A_)-1
  for k in range(K):
    if sum([a%d for a in A_]) == 0:
      print(d)
      exit()
    
    A_[left] -= 1
    if A_[left]==0:
      left += 1
    A_[right]+= 1
    if A_[right]==d:
      right-= 1

Submission status: Wrong Answer

Solution code:
import math
a,b=map(int,input().split())
c=list(map(int,input().split()))

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

    divisors.sort(reverse = True)
    return divisors
d=make_divisors(sum(c))


m=1
for i in d:
  d=[0 for j in range(a)]
  for j in range(a):
    d[j]=c[j]%i
  d.sort()
  for j in range(a):
    k=sum(d[:j]) 
    l=(a-j)*i-sum(d[j:])
    if k==l and k+l<=b*2:
      print(i)
      exit()

Submission status: Wrong Answer

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

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

    # divisors.sort()
    return divisors

s=sum(A)

D=make_divisors(s)
D.sort()
D.reverse()
#print(D)

for m in D:
    now=k
    P=[i%m for i in A]
    P.sort()
    for i in range(n):
        now-=P[i]
        if now<=0:
            now+=P[i]
            ck=i
            break
    else:
        print(m)
        break
    NP=[m-i for i in P]
    now=k
    for i in range(ck,n):
        now-=NP[i]
        if now<0:
            break
    else:
        print(m)
        break

Submission status: Wrong Answer

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()
            #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: Wrong Answer

Solution code:
import math
a,b=map(int,input().split())
c=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
d=make_divisors(sum(c))


m=1
for i in d:
  d=[0 for j in range(a)]
  for j in range(a):
    d[j]=c[j]%i
  d.sort()
  for j in range(a):
    k=sum(d[:j]) 
    l=(a-j)*i-sum(d[j:])
    if k==l and k+l<=b*2:
      m=i
      break
print(m)

Submission status: Wrong Answer

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
            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: Wrong Answer

Solution code:
import math
a,b=map(int,input().split())
c=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
d=make_divisors(sum(c))


m=1
for i in d:
  d=[0 for i in range(a)]
  for j in range(a):
    d[j]=c[j]%i
  d.sort()
  for j in range(a):
    k=sum(d[:j]) 
    l=(a-j)*i-sum(d[j:])
    if k==l and k+l<=b*2:
      m=i
      break
print(m)

Submission status: Wrong Answer

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

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

sumA = sum(A)
divs = make_divisors(sumA)[::-1]
# 何回操作しても総和が変わらないので，すべての要素を割り切る正の整数は，総和の約数
# よってこれだけ試す

for d in divs:
  B = [a%d for a in A]
  B.sort()
  Bcumsum = list(accumulate(B))
  nBcumsum = list(accumulate([b-d for b in B][::-1]))[::-1]
  for i in range(len(B)-1):
    if Bcumsum[i]==-nBcumsum[i+1]:
      if Bcumsum[i]<=K:
        print(d)
        exit()
      else:
        break

Submission status: Wrong Answer

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 rest(i,k):
    r = i%k
    if r <= k//2:
        return r
    else:
        return k-r

def foo(x):
    b = []
    for y in a:
        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()
            #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: Wrong Answer

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 -= 7
        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: Wrong Answer

Solution code:
# 保存用に提出 ABC136 E

def create_conbinations(conbination, N, n):
    if n == 0:
        yield conbination
    
    else:
        n -= 1
        for i in range(N):
            conbination[i] += 1
            create_conbinations(conbination, N, n)
            conbination[i] -= 1


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

A_lst.sort()
A_SUM = sum(A_lst)
commons_lst = []

for i in range(int(A_SUM/N), 0, -1):
    if A_SUM % i == 0:
        bn = A_SUM // i
        common = i
        commons_lst.append((common, bn))

ans = 0
candidates = []
for common, bn in commons_lst:
    tmp = [common] * N
    remining = bn - N
    conbination = [0]*N
    for conbination in create_conbinations(conbination, N, remining):
        for i in range(N):
            tmp[i] += conbination[i] * common
        t = 0
        for i in range(N):
            t += abs(tmp[i] - A_lst[i])
        if t <= K:
            ans = common
            break
    if ans:
        break

print(ans)

Submission status: Wrong Answer

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

suma = sum(a)

def divisor(n) :
    ans = []
    for i in range(2, n//2+1) :
        if not n%i :
            ans.append(i)
    ans.append(n)
    return ans

testicle = divisor(suma)

answer = 1
for t in testicle :
    s = [0 for i in range(n)]
    for i, aa in enumerate(a) :
        if i == n-1 :
            s[i] = -sum(s)
        else :
            if aa%t <= t-aa%t :
                s[i] = aa%t
            else :
                s[i] = aa%t - t
    if sum(map(abs, s)) <= 2*k :
        answer = t
print(answer)

Submission status: Wrong Answer

Solution code:
n, K = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = sum(a)
f = []
for i in range(b, 0, -1):
    if b % i == 0:
        f.append(i)

for fi in f:
    a_dif = [0 for i in range(n)]
    for i, ai in enumerate(a):
        a_dif[i] = (ai % fi)
    cnt = 0
    while True:
        k = 10**6
        for i in range(n):
            if a_dif[i] > 0 and a_dif[i] < k:
                k = a_dif[i]
                idx = i
        if k == 10**6:
            break
        for i in range(k):
            x = max(a_dif)
            idx2 = a_dif.index(x)
            a_dif[idx] -= 1
            a_dif[idx2] = (a_dif[idx2]+1)%fi
            cnt += 1
        if cnt > K:
            break
    if k == 10**6:
        print(fi)
        break

Submission status: Wrong Answer

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: Wrong Answer

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 rest(i,k):
    r = i%k
    if r <= k//2:
        return r
    else:
        return k-r

def foo(x):
    b = []
    for y in a:
        b.append(y%x)
    b.sort()
    m = k
    while m>0 and len(b)>0:
        if b[0] < x-b[-1]:
            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()
            #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: Wrong Answer

Solution code:
s = list(map(int,input().split()))
a = list(map(int,input().split()))
b = 0
e = 0
ans = 0
N = s[0]
K = s[1]
for i in range(N):
    b += a[i]
for i in range(1,b+1):
    d = [0] * N
    if(b % i == 0):
        #print(i)
        c = 0
        for k in range(N):
            d[k] = a[k] % i
            c += d[k]
        #print(d)
        if(c % i == 0):
            #print(i)
            e = 0
            for l in range(N):
                d[l] = min(i - d[l],d[l])
                e += d[l] 
            #print(e)
            if((e / 2) < K):
                ans = i
                
            
print(ans)

Submission status: Wrong Answer

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

sum = 0
for i in range(N):
    sum += A[i]

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

divisors.sort(reverse=True)

for d in divisors:
    v = []
    for i in range(N):
        v.append(A[i]%d)
    v.sort(reverse=True)
    vSum = 0
    for i in range(N):
        vSum += v[i]
    abc = 0
    vMin = vSum
    for i in range(N):
        abc += d-v[i]
        vMin = min(vMin,max(vSum-v[i], abc))
    if vMin <= K:
        print(d)
        exit()

Submission status: Wrong Answer

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

s = 2
l = [0]*n
maxs = 0
while s < max(a)+k+1:
    for i in range(n):
        l[i] = a[i]%s
    l.sort()
    sml = sum(l)
    ns = sml//s
    if sml%s == 0 and -sum(l[len(l)-ns:len(l)])+ns*s<=k:
        maxs = s
    s = s + 1
print(maxs)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=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)

    divisors.sort()
    return divisors

l=make_divisors(s)
i=len(l)-1
while i>=0:
    u=[0]*n
    d=[0]*n
    for k in range(n):
        for j in range(s//l[i]):
                if l[i]*j<a[k]:
                    u[k]=l[i]*(j+1)
                    d[k]=l[i]*j
    for k in range(n):
        u[k]=u[k]-a[k]
        d[k]=d[k]-a[k]
    for k in range(n):
        c=sum(d)-d[k]
        if u[k]+c==0 and abs(c)<=m:
            print(l[i])
            exit()

    i-=1

Submission status: Wrong Answer

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

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

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

    def __iter__(self):
        return self

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

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

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

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

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

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

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

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

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

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

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

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

        return F



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

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

    return str(res)

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

Submission status: Wrong Answer

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

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

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

    def __iter__(self):
        return self

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

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

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

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

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

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

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

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

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

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

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

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

        return F



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

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

    return str(res)

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