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

sumA = sum(A)
candiate = []
# sumAの約数を列挙する
tmp = 1
while tmp * tmp <= sumA:
    if sumA % tmp == 0:
        candiate.append(tmp)
        candiate.append(sumA // tmp)
    tmp += 1

def f(x):
    A.sort(key=lambda z:abs(z)%x)
    ret = 0
    for a in A[:-1]:
        if a % x < (x-(a%x)):
            ret += a % x
        else:
            ret += (x-(a%x))
    return ret
ans = -1
for cand in candiate:
    if f(cand) <= K:
        ans = max(ans, cand)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def make_divisors(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())
a = list(map(int,input().split()))

asum = sum(a)
adiv = make_divisors(asum)
adiv.reverse()

a = np.array(a)
ans = 1
flg = False
for i in adiv:
    a_ = np.sort(a % i)
    # print(i, a_)
    msum = a_.sum()
    msum_ = 0
    for j in range(-1, -n-1, -1):
        msum -= a_[j]
        msum_ += i - a_[j]

        if msum == msum_ :
            ans = i
            flg = True
            break
    if flg:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def make_divisors(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())
a = list(map(int,input().split()))

asum = sum(a)
adiv = make_divisors(asum)
adiv.reverse()

a = np.array(a)
ans = 1
flg = False
for i in adiv:
    a_ = np.sort(a % i)
    # print(i, a_)
    msum = a_.sum()
    msum_ = 0
    for j in range(-1, -n-1, -1):
        msum -= a_[j]
        msum_ += i - a_[j]
        if msum > k:
            break
        if msum < msum_:
            break
        if msum == msum_ :
            ans = i
            flg = True
            break
    if flg:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def make_divisors(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())
a = list(map(int,input().split()))

asum = sum(a)
adiv = make_divisors(asum)
adiv.reverse()

a = np.array(a)

for i in adiv:
    a_ = np.sort(a % i)
    msum, j = 0, 0
    while msum <= k and j < n-1:
        msum += a_[j]
        j += 1
    a_[j:] = i - a_[j:]
    if a_[:j].sum() <= k and a_[j:].sum() <= k:
        ans = i
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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)

    return divisors


def main():
    from itertools import accumulate
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    s = sum(a)
    divs = divisors(s)
    divs.sort()

    ans = 1
    for div in divs:
        rem = [0] * n
        for i, x in enumerate(a):
            rem[i] = x % div
        rem.sort()
        acc = list(accumulate(rem))
        for i, x in enumerate(acc, 1):
            cnt = max(x, div * (n - i) - acc[-1])
            if cnt <= k:
                ans = div
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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)

    return divisors


def main():
    from itertools import accumulate
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    s = sum(a)
    divs = divisors(s)
    divs.sort()

    ans = 1
    for div in divs:
        rem = [0] * n
        for i, x in enumerate(a):
            rem[i] = x % div
        rem.sort()
        acc = list(accumulate(rem))
        for i, x in enumerate(acc, 1):
            cnt = max(x, acc[-1] - x)
            if cnt <= k:
                ans = div
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

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

    for div in divs:
        a_mod = list(map(lambda x: x % div, a))
        sum_mod = sum(a_mod)
        if k >= sum_mod//2:
            print(div)
            break

resolve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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

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

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


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
def divisors(N):
    return sorted(sum((list({n, N // n}) for n in range(1, int(N ** 0.5) + 1) if not N % n), []))
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
D = np.array(divisors(A.sum()), dtype=np.int64)
ans = 0
for d in D:
    L = A % d
    if not L.sum():
        ans = d
        continue
    L = sorted(L)
    left, right = 0, N - 1
    count = 0
    while left < right:
        if L[left] + L[right] <= d:
            next_right = right - (L[right] + L[left] == d)
            next_left = left + 1
            count += L[left]
            L[right] += L[left]
            L[left] = 0
        else:
            next_right = right - 1
            m = L[left] + L[right] - d
            count += m
            L[right] -= m
            L[left] += m
        left, right = next_left, next_right
    if count > K:
        break
    ans = d
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


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

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

    for c in cand:
        arr = [a[i] % c for i in range(n)]
        tmp_sum = sum([arr[i] for i in range(n) if arr[i] < c - 1])
        tmp_count = 0
        for i in range(n):
            if arr[i] == c - 1:
                tmp_count += 1
        if tmp_sum + tmp_count <= 2 * k and tmp_count <= k:
            print(c)
            exit()

    print(1)


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

Submission status: Wrong Answer

Solution code:
def isok(x):
    li=sorted(z%x for z in a)
    res=0
    cum=[0]*(n+1)
    for i in range(n):
        cum[i+1]=cum[i]+li[i]
    for i in range(n):
        l,r=cum[i],x*(n-i)-(cum[n]-cum[i])
        if l==r and r<=k:
            return True
    return False
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

fac=sorted(factor(sum_),reverse=True)
for x in fac:
    if isok(x):
        print(x)
        exit()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

fac=sorted(factor(sum_))
ans=-1
for x in fac:
    if isok(x):
        ans=max(ans,x)
print(ans)

Submission status: Wrong Answer

Solution code:
def isok(x):
    li=sorted(map(lambda a:a%x,a))
    res=0
    l,r=0,n-1
    cuml=[0]*(n+1)
    cumr=[0]*(n+1)
    for i in range(n):
        cuml[i+1]=cuml[i]+li[i]
        cumr[i+1]=cumr[i]+(x-li[i])
    for i in range(n):
        if cuml[i]==cumr[n]-cumr[i] and cuml[i]<=k:
            return True
    return False

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

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

fac=sorted(factor(sum_))
ans=-1
for x in fac:
    if isok(x):
        ans=max(ans,x)
print(ans)

Submission status: Wrong Answer

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

print(cnt)

Submission status: Wrong Answer

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

print(cnt)

Submission status: Wrong Answer

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

print(cnt)

Submission status: Wrong Answer

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

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


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

    divisors.sort()
    return divisors

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

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

print(ans)

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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 += a
      cnt -= a
      i += 1
    elif a>p-b:
      if cnt<p-b:
        break
      a -= 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: Wrong Answer

Solution code:
from copy import copy, deepcopy
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 = A.copy()
            age = 0
            delete = 0
            for j in range(N):
                AA[j] = AA[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(delete, 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: Wrong Answer

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)]
    sb[0] = b[0]
    for i in range(n):
        sb[i+1] = sb[i] + b[i]

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

    if flg:
        print(cand)
        break

Submission status: Wrong Answer

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

s = sum(A)

from math import sqrt

P = []

for i in range(2,int(sqrt(s))+1):
    if s % i == 0:
        P.append(i)
        if i != s//i:
            P.append((s//i))

from copy import deepcopy

ans = 1

for p in P:
    B = deepcopy(A)
    r = 0
    for i in range(N):
        B[i] = B[i] % p
        a = 0
        b = 0
        if 0 <= B[i] <= p//2:
            a += B[i]
        else:
            b += B[i]
        r = min(a,b)+(max(a,b)-min(a,b))//2
    if r <= K:
        ans = max(ans,p)
print(ans)

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

tmp=make_divisors(sum(a))[::-1]
for c in tmp:
    cnt=0
    for ca in a:
        if ca<c:
            cnt+=ca
        else:
            ca%=c
            if ca<c-ca:
                cnt+=ca
            else:
                cnt-=(c-ca)

    if cnt%c==0 and 0<=cnt<=2*k:
        print(c)
        exit()