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=[int(i) for i in input().split()]
S=sum(A)
DivS=set()
index=1
while(index*index<=S):
    if S%index==0:
        DivS.add(index)
        DivS.add(S//index)
    index+=1
#print(DivS)
ans=1
for d in DivS:
    B=[A[i] for i in range(N)]
    for i in range(N):
        if A[i]%d==0:
            continue
        #kd<A[i]<(k+1)d
        #k=A[i]//d
        tmp1=(A[i]//d)*d
        tmp2=tmp1+d
        if abs(tmp1-A[i])<=abs(tmp2-A[i]):
            B[i]=tmp1
        else:
            B[i]=tmp2
    nowsum=sum(B)
    #print(d,B)
    if nowsum!=S:
        B[0]+=(S-nowsum)
    #print(d,B)
    cost=sum([abs(A[i]-B[i]) for i in range(N)])
    if cost<=2*K:
        ans=max(ans,d)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
def divisor_list(N): #素因数分解
    res = []
    i = 1
    while i*i < N:
        if N%i == 0:
            res.append(i)
            res.append(N//i)
        i += 1
    if i*i == N: res.append(i)
    return sorted(res)

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

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


l = reversed(divisor_list(sum(a)))


def check(x):
    res = []
    for ai in a:
        res.append(min(ai%x,x-ai%x))
    
    res.sort()
    c = sum(res) - res[-1]
#    print(x,c,res)
    return (c <= k)



for x in l:
    if check(x):
        print(x)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

s = sum(A)
m = math.ceil(math.sqrt(s))

divs = []
divs2 = []
i = 1
while i < s:
	if s % i == 0:
		divs.append(i)
		divs2.append(s//i)
	i += 1
divs.reverse()
divs2 += divs

ans = 1
for n in divs2:
	B = [a % n for a in A]
	s = sum(B)
	if s % n != 0: continue
	B.sort()
	B = [b for b in B if b != 0]
	if len(B) == 0:
		ans = max(ans, n)
		break
	bsum = [0]*len(B)
	rbsum = [0]*len(B)
	bs = 0
	for i, b in enumerate(B):
		bs += b
		bsum[i] = bs
	bs = 0
	for i, b in reversed(list(enumerate(B))):
		bs += n - b
		rbsum[i] = bs
	need = float('inf')
	for i in range(len(B)-1):
		if bsum[i] == rbsum[i+1]:
			need = bsum[i]
			break
	if need <= K:
		ans = max(ans, n)
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

s = sum(A)
m = math.ceil(math.sqrt(s))

divs = set()
i = 1
while i < s:
	if s % i == 0:
		divs.add(i)
		divs.add(s//i)
	i += 1

ans = 1
for n in divs:
	B = [a % n for a in A]
	s = sum(B)
	if s % n != 0: continue
	B.sort()
	B = [b for b in B if b != 0]
	if len(B) == 0:
		ans = max(ans, n)
		continue
	bsum = [0]*len(B)
	rbsum = [0]*len(B)
	bs = 0
	for i, b in enumerate(B):
		bs += b
		bsum[i] = bs
	bs = 0
	for i, b in reversed(list(enumerate(B))):
		bs += n - b
		rbsum[i] = bs
	need = float('inf')
	for i in range(len(B)-1):
		if bsum[i] == rbsum[i+1]:
			need = bsum[i]
			break
	if need <= K:
		ans = max(ans, n)
print(ans)

Submission status: Time Limit Exceeded

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, a[i] % c - c] for i in range(n)]
        min_sum = sum([ai[1] for ai in arr])
        if (0 - min_sum) // c <= n:
            for i in range(1 << n):
                tmp = [0] * 2
                for j in range(n):
                    if i & (1 << j):
                        tmp[0] += arr[j][0]
                    else:
                        tmp[1] += arr[j][1]
                if sum(tmp) == 0 and tmp[0] <= k:
                    print(c)
                    exit()
    print(1)


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

Submission status: Time Limit Exceeded

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, a[i] % c - c] for i in range(n)]
        for i in range(1 << n):
            tmp = [0] * 2
            for j in range(n):
                if i & (1 << j):
                    tmp[0] += arr[j][0]
                else:
                    tmp[1] += arr[j][1]
            if sum(tmp) == 0 and tmp[0] <= k:
                print(c)
                exit()
    print(1)


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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)


S = sum(A)
divisors = []

for i in range(1, S):
    if S < i * i:
        break

    if S % i == 0:
        divisors.append(i)
        divisors.append(S // i)


def check(x):
    modX = A % x
    modX = np.sort(modX)
    modX = modX[modX > 0]

    L = len(modX)
    rtn = False

    for i in range(L):
        cnt = 0
        minus = modX[:i]
        plus = modX[i:]

        cnt_minus = sum(minus - 0)
        cnt_plus = sum(x - plus)

        if cnt_minus <= K and cnt_plus <= K:
            rest = abs(cnt_minus - cnt_plus)
            if rest % x == 0:
                rtn = True
                break

    return rtn


ans = 1
for x in divisors:
    if check(x):
        ans = max(x, ans)

print(ans)

Submission status: Time Limit Exceeded

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

    divisors.sort()
    return divisors

def judge(cand, a, k, plus, minus, length, place):
    if plus > k or minus > k:
        return False
    
    if place == length:
        if plus - minus == 0 and plus <=  k:
            return True
        else:
            return False
    else:
        m = a[place] % cand
        p = cand - m
        return judge(cand, a, k, plus+p, minus, length, place+1) or judge(cand, a, k, plus, minus+m, length, place+1)
        
n,k = map(int, input().split())
a = list(map(int, input().split()))
# 候補はsum(a)の正約数。
total = sum(a)
length = len(a)
candidate = make_divisors(total)
candidate.sort(reverse = True)
for cand in candidate:
    if judge(cand, a, k, 0, 0, length, 0):
        print(cand)
        break

Submission status: Time Limit Exceeded

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

def main():
    N,K = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    s = sum(a)
    div = [1]
    for i in range(2,s//2+1):
        if s%i == 0:
            div.append(i)
    
    div.append(sum(a))
    ans = 1
    for use in div:
        rest = -(a%use)
        rest = np.sort(rest)
        ch = -sum(rest)//use
        do = use*ch+sum(rest[:ch])
        if do <= K:
            ans = use
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

divs = []
maxA = sum(A)
for i in range(1, maxA + 1):
    if maxA % i == 0:
        divs.append(i)
        divs.append(maxA // i)

divs.sort(reverse=True)

for d in divs:
    rest = [a % d for a in A]
    rest.sort(reverse=True)
    restSum = sum(rest) // d
    cnt = 0
    for i in range(restSum):
        cnt += d - rest[i]
    if cnt <= K:
        print(d)
        exit()

Submission status: Time Limit Exceeded

Solution code:
from math import ceil


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

divs = []
maxA = sum(A)
for i in range(maxA, ceil(maxA ** 0.5) - 1, -1):
    if maxA % i == 0:
        divs.append(i)
        divs.append(maxA // i)

divs.sort(reverse=True)

for d in divs:
    rest = [a % d for a in A]
    rest.sort(reverse=True)
    restSum = sum(rest) // d
    cnt = 0
    for i in range(restSum):
        cnt += d - rest[i]
    if cnt <= K:
        print(d)
        exit()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

M = sum(A)
L = []
i = 1
while i <= M**0.5:
    if M%i == 0:
        L.append(i)
        L.append(M//i)
    i += 1
    
L.sort(reverse=True)

for i in L:
    temp = [0]*N
    for j in range(N):
        temp[j] = A[j]%i
    temp.sort()
    cnt = 0
    l = 0
    r = N-1
    while l < r:
        if temp[l] == 0:
            l += 1
            continue
        if temp[r] == 0:
            r -= 1
            continue
        temp[l] -= 1
        temp[r] += 1
        temp[r] %= i
        cnt += 1
    if cnt <= K:
        ans = i
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

#def Min_Step_To_Divides(A, k):
#    # A: array
#    N = A.size
#    Red = (A/k)*k - A
#    Add = ((A+k-1)/k)*k - A
#    #f[i][j]: residual operation after A[0~i] operate j times
#    f = np.full([N, 2*k+1], -1, dtype=int)
#    f[0][k+1+Red[0]] = -Red[0]
#    f[0][k+1+Add[0]] =  Add[0]
#    for i in xrange(1, N):
#        for j in xrange(2*k+1):
#            List = []
#            if (j-Red[i] < 2*k+1) and f[i-1][j-Red[i]] != -1:
#                List.append(f[i-1][j-Red[i]] - Red[i])
#            if (j-Add[i] >= 0) and f[i-1][j-Add[i]] != -1:
#                List.append(f[i-1][j-Add[i]] + Add[i])
#            if List != []:
#                f[i][j] = min(List)
#    return f[N-1][k+1]

def Min_Step_To_Divides(A, k):
    N = A.size
    r = np.sort(A%k)
    m = N-r.sum()/k
    return np.sum(r[:m])    

def All_combine(N):
    ans = []
    for i in xrange(N+1,0,-1):
        if N%i == 0:
            ans.append(i)
    return ans


N, K = map(int, raw_input().split())  
A = np.array(map(int, raw_input().split()))

Sum = np.sum(A)
Divides = All_combine(Sum)

for d in Divides:
    a = Min_Step_To_Divides(A, d)
    if a == -1 or a > K :
        pass
    else:
        print d
        break

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

def Min_Step_To_Divides(A, k):
    # A: array
    N = A.size
    Red = (A/k)*k - A
    Add = ((A+k-1)/k)*k - A
    #f[i][j]: residual operation after A[0~i] operate j times
    f = np.full([N, 2*k+1], -1, dtype=int)
    f[0][k+1+Red[0]] = -Red[0]
    f[0][k+1+Add[0]] =  Add[0]
    for i in xrange(1, N):
        for j in xrange(2*k+1):
            List = []
            if (j-Red[i] < 2*k+1) and f[i-1][j-Red[i]] != -1:
                List.append(f[i-1][j-Red[i]] - Red[i])
            if (j-Add[i] >= 0) and f[i-1][j-Add[i]] != -1:
                List.append(f[i-1][j-Add[i]] + Add[i])
            if List != []:
                f[i][j] = min(List)
    return f[N-1][k+1]

def All_combine(N):
    ans = []
    for i in xrange(N+1,0,-1):
        if N%i == 0:
            ans.append(i)
    return ans


N, K = map(int, raw_input().split())  
A = np.array(map(int, raw_input().split()))

Sum = np.sum(A)
Divides = All_combine(Sum)

for d in Divides:
    a = Min_Step_To_Divides(A, d)
    if a == -1 or a > 2*K :
        pass
    else:
        print d
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

for x in yakusu:
    tmp = list(map(lambda y: y%x, A))
    tmp.sort()
    for i in range(N):
        minuscnt = sum(tmp[:i+1])
        pluscnt = x*(N-i-1)-sum(tmp[i+1:])
        if minuscnt%x == pluscnt%x and K >= max(minuscnt,pluscnt):
            print(x)
            sys.exit()

Submission status: Time Limit Exceeded

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

def divisors(n):
  ans = set()
  d = 1
  while(d*d<=n):
    if(n%d==0):
      ans.add(d)
  return sorted(list(ans),reverse = True)
cost = 0
for d in divisors(sum(a)):
  for i in range(n): 
    cost += min(a[i]%d,d-a[i]%d)
  if(cost<=k):
    print(d)
    break

Submission status: Time Limit Exceeded

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

import math

Asum = sum(A)
candidates = []
for i in range(1, int(math.sqrt(Asum)) + 1):
    if Asum % i == 0:
        candidates.append(i)
        candidates.append(Asum // i)
candidates.sort()

# print("#", Asum)
# print("#", candidates)

ans = 1
for targ in candidates:
    if targ == 1: continue
    A_tmp = [(Ai % targ) for Ai in A]
    # A_tmp.sort(key=lambda x: min((x % targ), ((targ - x) % x)))
    A_tmp.sort()
    idx_l = 0
    idx_r = N - 1
    cnt = 0
    while sum(A_tmp) > 0 and idx_l < idx_r:
        cap_l = A_tmp[idx_l]
        cap_r = targ - A_tmp[idx_r]
        A_tmp[idx_l] = (A_tmp[idx_l] - min(cap_l, cap_r)) % targ
        A_tmp[idx_r] = (A_tmp[idx_r] + min(cap_l, cap_r)) % targ
        cnt += min(cap_l, cap_r)
        if A_tmp[idx_l] == 0:
            idx_l += 1
        if A_tmp[idx_r] == 0:
            idx_r -= 1
    #
    if cnt <= K and sum(A_tmp) == 0: ans = targ

print(ans)

Submission status: Time Limit Exceeded

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

import math

Asum = sum(A)
candidates = []
for i in range(1, int(math.sqrt(Asum)) + 1):
    if Asum % i == 0:
        candidates.append(i)
        candidates.append(Asum // i)
candidates.sort()

# print("#", Asum)
# print("#", candidates)

ans = 1
for targ in candidates:
    if targ == 1: continue
    A_tmp = [(Ai % targ) for Ai in A]
    # A_tmp.sort(key=lambda x: min((x % targ), ((targ - x) % x)))
    A_tmp.sort()
    idx_l = 0
    idx_r = N - 1
    cnt = 0
    while sum(A_tmp) > 0:
        cap_l = A_tmp[idx_l]
        cap_r = targ - A_tmp[idx_r]
        A_tmp[idx_l] = (A_tmp[idx_l] - min(cap_l, cap_r)) % targ
        A_tmp[idx_r] = (A_tmp[idx_r] + min(cap_l, cap_r)) % targ
        cnt += min(cap_l, cap_r)
        if A_tmp[idx_l] == 0:
            idx_l += 1
        if A_tmp[idx_r] == 0:
            idx_r -= 1
    #
    if cnt <= K: ans = targ

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N,K = map(int , input().split())
    A = list(map(int , input().split()))
    max_A = max(A)
    total = sum(A)
    # ave_region = total//N

    max_d = 1
    for d in A:
        if all(a%d==0 for a in A) and d > max_d:
            max_d = d
    if K >= total:
        max_d = total
    search_region = range(max_d, min(total, max_A+K)+1)
    
    for d in search_region:
        if total % d == 0:
            remainders = [a%d for a in A]
            remainders = sorted(remainders)
            # print(d, remainders)
            positive_rem = 0
            negative_rem = 0
            flag = True
            for rem in remainders:
                if positive_rem+rem <= K:
                    positive_rem += rem
                elif negative_rem+(d-rem) <=K:
                    negative_rem += (d-rem)
                else: 
                    flag = False
                    break

            if flag :
                # print(d, remainders, positive_rem, negative_rem)
                max_d = d
            
    print(max_d)
    
solve()

Submission status: Time Limit Exceeded

Solution code:
import math

def solve():
    N,K = map(int , input().split())
    A = list(map(int , input().split()))
    total = sum(A)
    max_a = max(A)
    search_region = min( total+1, N*max_a+1)
    
    max_d = 1
    for d in range(2, search_region):
        if total % d == 0:
            remainders = [a%d for a in A]
            remainders = sorted(remainders)
            # print(d, remainders)
            positive_rem = 0
            negative_rem = 0
            flag = True
            for rem in remainders:
                if positive_rem+rem <= K:
                    positive_rem += rem
                elif negative_rem+(d-rem) <=K:
                    negative_rem += (d-rem)
                else: 
                    flag = False
                    break

            if flag :
                # print(d, remainders, positive_rem, negative_rem)
                max_d = d
            
    print(max_d)
    
solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
from copy import copy
N, K = map(int,input().split())
As = list(map(int,input().split()))

A_sum = np.sum(As)

possible_answers = [i for i in range(1,A_sum+1) if A_sum % i == 0]


for p in possible_answers[::-1]:
    candidates = copy(As)
    candidates = [i%p for i in candidates]
    candidates = sorted(candidates)
    for i in range(1,len(candidates)):
        a0 = np.sum([e for e in candidates[:i]])
        a1 = np.sum([p-e for e in candidates[i:]])
        if np.max([a0,a1]) <= K and (a0+a1)%2 == 0:
            print(p)
            sys.exit()
print(1)

Submission status: Time Limit Exceeded

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

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

def maxGCD(k, a):
    for d in make_divisors(sum(a)):
        divided_a = sorted([x%d for x in a])
        for i in range(len(divided_a)):
            sum_p = sum(divided_a[0:i])
            sum_n = sum([d-x for x in divided_a[i:]])
            if sum_p == sum_n and sum_p <= k:
                return d
    return 1

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    print(maxGCD(k, a))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def get_divisors(n):
    from math import ceil
    divisors = []
    for num in range(ceil(n**0.5), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.append(num)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)

Submission status: Time Limit Exceeded

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

def get_divisors(n):
    from math import sqrt, ceil
    divisors = []
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.append(num)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)

Submission status: Time Limit Exceeded

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

# nの約数を求める。計算量O(sqrt(N))
def get_divisors(n):
    from math import sqrt, ceil
    divisors = []
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.append(num)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)

Submission status: Time Limit Exceeded

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

# nの約数を求める。計算量O(sqrt(N))
def get_divisors(n):
    from math import sqrt, ceil
    from collections import deque
    divisors = deque([])
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.appendleft(num)
    return list(divisors)

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)

Submission status: Time Limit Exceeded

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

# nの約数を求める。計算量O(sqrt(N))
def get_divisors(n):
    from math import sqrt, ceil
    from collections import deque
    divisors = deque([])
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.appendleft(num)
    return list(divisors)

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if (-nr) == pr:
            if pr <= K:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)

Submission status: Time Limit Exceeded

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

total_a = sum(a_list)
#約数の列挙
candidates = set()
for i in [a for a in range(1, total_a) if a * a <= total_a]:
    if total_a % i == 0:
        candidates.add(i)
        candidates.add(total_a // i)

ans = 1
for x in candidates:
    remainders = sorted(map(lambda a: a % x, a_list))
    total_r = sum(remainders)
    border = total_r // x
    need = sum(remainders[:(N - border)])
    if need <= K:
        ans = max(ans, x)
print(ans)

Submission status: Time Limit Exceeded

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]

for d in dc_list:
    mods = [a % d for a in A]
    mod_sum = sum(mods)
    if mod_sum % d != 0:
        continue
    mods = sorted(mods)

    op = 0
    mod_len = len(mods)
    for i, mod in enumerate(mods):
        op += mod

        if op > K:
            break

        if (mod_len - (i + 1)) * d == mod_sum and op <= K:
            print(d)
            exit(0)

Submission status: Time Limit Exceeded

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]

for d in dc_list:
    mods = sorted([a % d for a in A])
    if sum(mods) % d != 0:
        continue

    # cs:sumulative sum(累積和)
    mod_cs = [0] * (len(mods) + 1)
    for i, mod in enumerate(mods):
        mod_cs[i + 1] = mod_cs[i] + mod

    for i, mod_cumulative in enumerate(mod_cs):
        minus_op = mod_cumulative
        plus_op = (d * (len(mod_cs) - 1 - i)) - (mod_cs[-1] - mod_cs[i])

        if minus_op == plus_op and minus_op <= K:
            print(d)
            exit(0)
        elif minus_op > K:
            break

Submission status: Time Limit Exceeded

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]

for d in dc_list:
    mods = sorted([a % d for a in A])
    # cs:sumulative sum(累積和)
    mod_cs = [0] * (len(mods) + 1)
    for i, mod in enumerate(mods):
        mod_cs[i + 1] = mod_cs[i] + mod

    for i, mod_cumulative in enumerate(mod_cs):
        minus_op = mod_cumulative
        plus_op = (d * (len(mod_cs) - 1 - i)) - (mod_cs[-1] - mod_cs[i])

        if minus_op == plus_op and minus_op <= K:
            print(d)
            exit(0)
        elif minus_op > K:
            break

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = sum(A)
flag = False
for x in range(s, 0, -1):
    if flag:
        break
    sortedA = sorted([a%x for a in A])
    sumA = sum(sortedA)
    index_len = len(sortedA)
    sump = 0
    for i, a in enumerate(sortedA):
        sump += a
        summ = x*(index_len - (i+1)) - (sumA - sump)
        if sump == summ and sump <= K:
            print(x)
            flag = True
            break

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,K = II()
A = III()

sumA = sum(A)

for i in range(1,sumA+1)[::-1]:
  if sumA%i != 0:
    continue
  r = [0]*N
  for j in range(N):
    r[j] = A[j]%i
  sumr = sum(r)
  if sumr%i != 0:
    continue
  r.sort(reverse=True)
  num = 0
  for k in range(sumr//i):
    num += i-r[k]
  if num <= K:
    print(i)
    exit()

Submission status: Time Limit Exceeded

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

# 2以上の約数を求める
def make_divisors(n):
    divisors = []
    for i in range(1, n+1):
        if n % i == 0:
            divisors.append(i)

    divisors.sort()
    return divisors

# 答えはaの合計の約数
divisors = make_divisors(sum(a))

answer = 1
for candi in divisors:
    nokori_shori = k
    amari_list = [i%candi for i in a]
    amari_list.sort()
    # 後ろからマイナスにしていく
    cursor = n-1
    while nokori_shori > 0 and sum(amari_list) != 0:
        if (candi - amari_list[cursor]) <= nokori_shori:
            nokori_shori -= (candi - amari_list[cursor])
            amari_list[cursor] -= candi
            cursor -= 1
            if cursor < 0:
                break
        else:
            break
    if sum(amari_list) == 0:
        answer = candi

print(answer)

Submission status: Time Limit Exceeded

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


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


if __name__ == '__main__':
    n, k = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))
    divisors = make_divisors(sum(A))
    for divisor in divisors:
        remainders = sorted(map(lambda x: x % divisor, A))
        for i in range(1, n):
            ope_num = max(sum(remainders[0:i]), sum(map(lambda x: divisor - x, remainders[i:n])))
            if ope_num <= k:
                print(divisor)
                exit()

Submission status: Time Limit Exceeded

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

asum = sum(a)
gcdmax = int(math.sqrt(asum))
li = [i for i in range(2,gcdmax+1)]
for i in range(gcdmax,0,-1):
    if asum%i==0:
        li.append(asum//i)


ans = 1

for i in li:
    b = [a[ii] % i for ii in range(n)]
    b.sort()
#     print(i,b)
    l = 0
    r = 0
    x = 0
    y = n-1
    while x<=y:
        if r>=l:
            l += b[x]
            x += 1
        else:
            r += i - b[y]
            y -= 1
#         print(l,r)
    if max(l,r) <= k and (l-r)%i==0 :
        ans = i

print(ans)