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,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

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

    s = sum(A)
    d = [s]
    for i in range(2,int(math.sqrt(s))+1):
        if s % i == 0:
            d.append(i)
            if s // i != i:
                d.append(s//i)

    ans = 1




    for x in d:
        c = 0
        cnt = 0

        B = sorted(A,key=lambda z:x-z%x,reverse=True)

        for y in B:
            c1 = x - y % x
            c2 = -(y % x)
            if abs(c + c1) < abs(c + c2):
                c += c1
                cnt += c1
            else:
                c += c2

        if c == 0 and cnt <= K:
            ans = max(ans,x)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
"""
どんなに操作をおこなっても、全てのi,j(i<j)に関して、Ai,Ajの絶対値の差がsum(A)より大きくなることはない。
したがって、答えがsum(A)より大きくなることはない。
さらに言うなら、数値の状態がワイルドカードである0がベストなので負の値にする必要もない。

また、答えはsum(A)の約数になる。
答えをXとおくと、全ての数はXで割り切れる＝Xの倍数である。
Ai/X = Biとおくと、XBi = Ai　と表すことができる。。
X*sum(B) = sum(A)なので、答えXはsum(A)の約数であることがわかる。

解法：
基本方針としては、sum(A)の約数を列挙して、K回以内の操作で大きい順に実現可能かどうかを調べる。
実現可能かどうかは、各Aiを数が引かれる方と足される方に分けることで考えることができる。
"""
from itertools import accumulate
N,K = map(int,input().split())
A = list(map(int,input().split()))

sumA = sum(A)

#sumAの約数を列挙する。
yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)

for d in yakusu:
    X = [A[i]%d for i in range(N)]
    X.sort()
    Y = [d-A[i]%d for i in range(N)]
    Y.sort()
    X = list(accumulate(X))
    Y = list(accumulate(Y))
    Y = Y[::-1]
    for i in range(N-1):
        if X[i] == Y[i+1] and X[i]<=K:
            print(d)
            exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K=map(int,input().split())
L=list(map(int,input().split()))

def factorization(N):
    res=[]
    for i in range(2,int(N**(1/2))+2):
        if not N%i:
            r=0
            while not N%i:
                N//=i
                r+=1
            res.append((i,r))
    if N>1:
        res.append((N,1))
    return res

def factors(n):
    res=[1]
    for i,j in factorization(n):
        res+=[r*i**(b+1) for r in res for b in range(j)]
    return res

A=factors(sum(L))
A.sort()

def check(n):
    B=deque(sorted([a%n for a in L if a%n>0]))
    rp,rm=0,0
    while B:
        if rp<rm:
            rp+=B.popleft()
        else:
            rm+=n-B.pop()
    if rp!=rm:
        return False
    return rp<=K

ok=-1
ng=len(A)
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if check(A[mid]):
        ok=mid
    else:
        ng=mid
print(A[ok])

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

x=sum(a)

lst=make_divisors(x)

lst.reverse()

for can in lst:
    aa=list(map(lambda x:x%can,a))
    aa.sort()

    cnt=0
    l=0
    r=0
    lll=0
    rrr=len(aa)-1
    while lll<=rrr:
        if l<r:
            l+=aa[lll]
            lll+=1
        
        else:
            r+=can-aa[rrr]
            rrr-=1
    
    if l==r and l<=k:
        print(can)
        exit()

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

x=sum(a)

lst=make_divisors(x)

lst.reverse()

for can in lst:
    aa=list(map(lambda x:x%can,a))
    aa.sort()

    cnt=0
    l=0
    r=0
    lll=0
    rrr=len(aa)-1
    while lll<=rrr:
        if l==r:
            if lll==rrr:
                break
            l+=aa[lll]
            r+=can-aa[rrr]
            lll+=1
            rrr-=1

        elif l<r:
            l+=aa[lll]
            lll+=1
        
        else:
            r+=can-aa[rrr]
            rrr-=1
    
    if l==r and l<=k:
        print(can)
        exit()

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

x=sum(a)

lst=make_divisors(x)

lst.reverse()

for can in lst:
    aa=list(map(lambda x:x%can,a))
    aa.sort()

    cnt=0
    l=0
    r=0
    lll=0
    rrr=len(aa)-1
    while lll<=rrr:
        if l==r:
            l+=aa[lll]
            r+=can-aa[rrr]
            lll+=1
            rrr-=1

        elif l<r:
            l+=aa[lll]
            lll+=1
        
        else:
            r+=can-aa[rrr]
            rrr-=1
    
    if l==r and l<=k:
        print(can)
        exit()

Submission status: Wrong Answer

Solution code:
"""
まず、答えは必ずAの総和以下になる。なぜなら、A同士の差の最大値がAの総和だからである。
移動回数が足りるのであれば、一つだけAの総和になるような項を作って、他を全部0にするのがよい。
ここからわかるのは、数を移動させ終わった後の各Aは全て0以上になるということである。

また答えはからなずAの総和の約数になる。
理由：
答えをXとすると、各AはbXと表すことができる。
したがって、Aの総和＝(bの総和*X)となる。
ゆえに、答えXはAの総和の約数である。

解法としては、Aの総和の約数を列挙して、大きい順に実現可能かどうかを試していく。
実現可能かどうかを試すには、各Aを総和の約数dで割ったときの余りをもとめて、小さい順にソートする。
そのうえで、左からL番目までを「数を与える側」、L+1番目以降を「数をもらう側」として余りが0になるように調整できないかを確かめる。
これは累積和を活用することですくない計算量で実行可能である。
最後に、移動した数がK以下かどうかを確認する。
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
sumA = sum(A)
 
yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)
for d in yakusu:
    #約数の大きい順に、実現可能かどうかを試していく。
    rest = [a%d for a in A]
    rest.sort()
    
    cnt = 0
    l = 0
    r = N-1
    Lstock = 0
    Rstock = 0
    while l < r:
        if Lstock == 0:
            Lstock = rest[l]
        if Rstock == 0:
            Rstock = d-rest[r]
        if Lstock > Rstock:
            cnt += Rstock
            Lstock -= Rstock
            Rstock = 0
            r -= 1
        elif Rstock > Lstock:
            cnt += Lstock
            Rstock -= Lstock
            Lstock = 0
            l += 1
        else:
            cnt += Rstock
            Lstock = 0
            Rstock = 0
            l += 1
            r -= 1
    if cnt <= K and Lstock==0 and Rstock==0:
        print(d)
        exit()

Submission status: Wrong Answer

Solution code:
"""
最大公約数を追い求める。

少なくとも、Aの合計値より答えが大きくなることはない。
なぜなら、どんなに頑張ってもA同士の差分はAの合計値以下になるからである。

答えの最大値はAの合計値。
マイナスを作る必要はない。
0を作る必要はある。

やっぱり、Aの合計値の約数のどれかが答えになりそうだな。証明はできないけど。
Aの合計値の約数を大きいものから順に、実現可能かどうかを検証していけばよい。

"""

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

yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)
for d in yakusu:
    #約数の大きい順に、実現可能かどうかを試していく。
    rest = [a%d for a in A]
    rest.sort()
    
    cnt = 0
    l = 0
    r = N-1
    Lstock = rest[l]
    Rstock = rest[r]
    while l < r:
        if Lstock > Rstock:
            cnt += Rstock
            Lstock -= Rstock
            r -= 1
            Rstock = rest[r]
        elif Rstock > Lstock:
            cnt += Lstock
            Rstock -= Lstock
            l += 1
            Lstock = rest[l]
        else:
            cnt += Rstock
            l += 1
            r -= 1
    if cnt <= K:
        print(d)
        exit()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
s=sum(a)

candidates=set()
for i in range(1,int(s**0.5)+1):
  if s%i==0:
    candidates.add(i)
    candidates.add(s//i)

ans=0
for cdd in candidates:
  div_cdd=[0]*n
  for i in range(n):
    div_cdd[i]=a[i]%cdd
  div_cdd=sorted(div_cdd)
  pstv,ngtv,need=0,-sum(div_cdd),10**9
  # calc need
  for i in range(n):
    pstv+=cdd-div_cdd[-1-i]
    ngtv+=div_cdd[-1-i]
    if pstv==-ngtv:
      need=min(need,pstv)
  ans=max(ans,cdd) if need<=k else ans
    
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
s=sum(a)

candidates=set()
for i in range(1,int(s**0.5)+1):
  if s%i==0:
    candidates.add(i)
    candidates.add(s//i)

ans=0
for cdd in candidates:
  div_cdd=[0]*n
  for i in range(n):
    div_cdd[i]=a[i]%cdd
  div_cdd=sorted(div_cdd)
  pstv,ngtv=0,-sum(div_cdd)
  # calc need
  for i in range(n):
    pstv+=cdd-div_cdd[-1-i]
    ngtv+=div_cdd[-1-i]
    if pstv==-ngtv: break;
  ans=max(ans,cdd) if pstv<=k else ans
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


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

    total = sum(A)
    div = divisors(total)

    for d in reversed(div):
        vec = [a % d for a in A if a % d]
        vec.sort()
        M = len(vec)
        csum_sub = [0] * (M + 1)
        csum_add = [0] * (M + 1)
        for i in range(M):
            csum_sub[i + 1] = csum_sub[i] + vec[i]
            csum_add[i + 1] = csum_add[i] + d - vec[i]

        for i in range(1, M):
            if csum_sub[i] <= K and csum_sub[i] == csum_add[M] - csum_add[i]:
                print(d)
                return

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


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

    total = sum(A)
    div = divisors(total)

    def calc_diff(a, d):
        diff = a - (a // d) * d
        return min(diff, diff - d, key=abs)

    for d in reversed(div):
        diff = [calc_diff(a, d) for a in A]
        diff.sort(key=abs)
        k = 0
        cur = 0
        for x in diff:
            if x > 0 and cur < 0 or x < 0 and cur > 0:
                if abs(x) < abs(cur):
                    cur += x
                    continue
                else:
                    cur = 0
                    x += cur
            else:
                if x + cur >= d:
                    b = (x + cur) // d * d
                    cur -= (x + cur) - b
                    x = 0

            cur += x
            k += abs(x)
        if k <= K:
            print(d)
            break

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

x = sum(a)
search = []
i = 1
while i ** 2 <= x:
    if x % i == 0:
        heapq.heappush(search, -i)
        heapq.heappush(search, -x//i)
    i += 1

while search:
    ans = -heapq.heappop(search)
    u = [a[i] % ans for i in range(n)]
    u.sort()

    plus = [0]
    minus = [0]
    for i in range(n):
        plus.append(plus[-1] + ans - u[i])
        minus.append(minus[-1] + u[i])

    for i in range(n):
        m = minus[i]
        p = plus[-1] - plus[i]
        if m == p and m <= k:
            print(ans)
            exit()

Submission status: Wrong Answer

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

x = sum(a)
search = []
i = 1
while i ** 2 <= x:
    if x % i == 0:
        heapq.heappush(search, -i)
        heapq.heappush(search, -x//i)
    i += 1

while search:
    ans = -heapq.heappop(search)
    # print("ans = ", ans, "?")
    plus = 0
    pmax = 0
    minus = 0
    mmax = 0
    for i in range(n):
        y = a[i] % ans
        if min(y, ans - y) == y:
            minus -= y
            mmax = max(mmax, y)
        else:
            plus += ans - y
            pmax = max(pmax, ans - y)

    if (plus + minus) % ans != 0:
        continue

    if plus > abs(minus):
        plus -= pmax
        minus -= ans - pmax
    elif plus < abs(minus):
        minus += mmax
        plus += ans - mmax

    if plus <= k:
        print(ans)
        break

Submission status: Wrong Answer

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

sumA = sum(A)
div = []
for i in range(2, sumA):
    if sumA % i == 0:
        div.append(i)
print(div)

ans = 1

Submission status: Wrong Answer

Solution code:
def yakusu(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
N,K=map(int,input().split())
L=list(map(int,input().split()))
a=sum(L)
R=yakusu(a)[::-1]
minus=0
even=0
add=0
for i in range(len(R)):
  s=R[i]
  A=list()
  B=list()
  for j in range(N):
    k=L[j]
    a=k%s
    b=s-a
    if a>b:
      add+=b
      B.append(b)
    elif a<b:
      minus+=a
      A.append(a)
    else:
      add+=a
      B.append(a)
  #足した分=add else:minus どっちでも:even
  A=sorted(A)
  B=sorted(B)
  if minus==add:
    d=minus
    if d<=K:
      print(s)
      exit()
  elif minus>add:
    q=(minus-add)//s
    d=sum(A[:len(A)-q])
    if d<=K:
      print(s)
      exit()
  else:
    q=(add-minus)//s
    d=sum(B[:len(B)-q])
    if d<=K:
      print(s)
      exit()

Submission status: Wrong Answer

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#xの約数を昇順に列挙 O(√N)
def Enumeration(x):
    low = []
    high = []
    for i in range(1,x):
        if i**2 >= x:
            if i**2 == x:
                low.append(i)
            break
        if x%i == 0:
            low.append(i)
            high.append(x//i)
    return high+low[::-1]  #降順
#    return low+high[::-1]

def main():
    n,k = map(int,ipt().split())
#    n = 500
#    k = 1
#    a = [10**6 for i in range(n)]
    a = [int(i) for i in ipt().split()]
    sm = sum(a)
    ys = Enumeration(sm)

    for i in ys:
        nm = 0
        vs = [j%i for j in a]
        vs.sort()
        l = 0
        r = n-1
        rs = 0
#        print(vs)
        while l < r:
            if rs == 0:
                rs = vs[l]
                nm += rs
                l += 1
            if rs+vs[r] >= i:
                rs -= i-vs[r]
                r -= 1
            else:
                vs[r] -= rs
                rs = 0
#        print(i,nm)
        if nm <= k and rs == 0:
            print(i)
            exit()


    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#xの約数を昇順に列挙 O(√N)
def Enumeration(x):
    low = []
    high = []
    for i in range(1,x):
        if i**2 >= x:
            if i**2 == x:
                low.append(i)
            break
        if x%i == 0:
            low.append(i)
            high.append(x//i)
    return high+low[::-1]  #降順
#    return low+high[::-1]

def main():
    n,k = map(int,ipt().split())
#    n = 500
#    k = 1
#    a = [10**6 for i in range(n)]
    a = [int(i) for i in ipt().split()]
    sm = sum(a)
    ys = Enumeration(sm)

    for i in ys:
        nm = 0
        vs = [j%i for j in a]
        vs.sort()
        l = 0
        r = n-1
        rs = 0
#        print(vs)
        while l < r:
            if rs == 0:
                rs = vs[l]
                nm += rs
                l += 1
            if rs+vs[r] >= i:
                rs -= i-vs[r]
                r -= 1
            else:
                vs[r] -= rs
                rs = 0
#        print(i,nm)
        if nm <= k:
            print(i)
            exit()


    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

import sys
input = sys.stdin.readline

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

def is_ok(x):
  P = DD(int)
  Q = DD(int)
  for a in A:
    P[a%x] += 1
    Q[(-a)%x] += 1
  Pk = [k for k in P]
  Qk = [k for k in Q]
  Pk.sort()
  Qk.sort()
  temp = K
  Pshori = 0
  for k in Pk:
    if temp >= P[k]*k:
      temp -= P[k]*k
      Pshori += P[k]
    else:
      Pshori += temp//k
      break
  temp = K
  Qshori = 0
  for k in Qk:
    if temp >= Q[k]*k:
      temp -= Q[k]*k
      Qshori += Q[k]
    else:
      Qshori += temp//k
      break
  if Pshori+Qshori >= N:
    return True
  else:
    return False

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

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

Submission status: Wrong Answer

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

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

import sys
input = sys.stdin.readline

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

def is_ok(x):
  P = DD(int)
  Q = DD(int)
  for a in A:
    P[a%x] += 1
    Q[-a%x] += 1
  Pk = [k for k in P]
  Qk = [k for k in Q]
  Pk.sort()
  Qk.sort()
  temp = K
  Pshori = 0
  for k in Pk:
    if temp >= P[k]*k:
      temp -= P[k]*k
      Pshori += P[k]
    else:
      Pshori += temp//k
      break
  temp = K
  Qshori = 0
  for k in Qk:
    if temp >= Q[k]*k:
      temp -= Q[k]*k
      Qshori += Q[k]
    else:
      Qshori += temp//k
      break
  if Pshori+Qshori >= N:
    return True
  else:
    return False

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

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

Submission status: Wrong Answer

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

    divisors.sort(reverse = True)
    return divisors
divlis = make_divisors(sum(A))

for res in divlis:
    tmp_add,tmp_sub = 0,0
    tmp = [i%res for i in A]
    tmp += [0]
    tmp.sort()
    tmp = list(itertools.accumulate(tmp))
    for i in range(1,n+1):
        su = tmp[n-i]-tmp[i]
        if(su==0 and tmp[i]<=k):
            print(res)
            exit()

Submission status: Wrong Answer

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

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

import sys
input = sys.stdin.readline

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

print(D[binary_search_int(0,len(D),test)])

Submission status: Wrong Answer

Solution code:
from math import sqrt

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a_sum = sum(a)
    st = Divisor_Set(a_sum)
    ans = 1
    st.remove(1)
    for v in st:
        b = [x%v for x in a]
        p = sum(b)//2
        if p <= k and ans < v:
            ans = v
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

s = sum(A)

divisor = []  # s の約数

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

divisor.sort(reverse=True)

from itertools import accumulate

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

Submission status: Wrong Answer

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


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