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

def checker(A,k):
    if sum(sorted(A)[:-1]) <= k:
        return True
    return False

n,k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

for d in make_divisors(sum(A)):
    buf = []
    if d == 1:
        print(d)
    else:
        for a in A:
            buf.append(a%d)
        if checker(buf,k):
            print(d)
            break

Submission status: Wrong Answer

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

    divisors.sort(reverse=True)
    return divisors

def checker(A,k):
    if sum(sorted(A)[:-1]) <= k:
        return True
    return False

n,k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

for d in make_divisors(sum(A))[1:]:
    buf = []
    if d == 1:
        print(d)
    else:
        for a in A:
            buf.append(a%d)
        if checker(buf,k):
            print(d)
            break

Submission status: Wrong Answer

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

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

divisors.sort(reverse=True)

ans = 0
for d in divisors:
    # 一旦全部マイナス方向に調整することにしたら総和はXの倍数になる
    # どれか一つ符号を逆転すると総和がx減るので、総和/d番目が境目になる
    # A = [8, 20]
    # d = 7
    # costs = [1, 6]
    # 20をプラス方向に調整することにすると、マイナス方向の調整は6減ってプラス方向に(7 - 1)増える
    # 1個をマイナス方向をプラス方向に変更すると、マイナス方向のコストの総和の差とプラス方向のコストの総和の差がdだけ詰まる
    # よって、最初全部マイナス方向に調整したときのコストの総和7を7で割ったところが境目
    # プラス方向にはcostが大きい方から変更したい(調整の量が少なくてすむ)ので、最初にソートしておく
    costs = [a % d for a in A]
    costs.sort(reverse=True)
    if sum(costs[:sum(costs) // d]) <= K:
        print(d)
        break

Submission status: Wrong Answer

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

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

divisors.sort(reverse=True)

ans = 0
for d in divisors:
    # 一旦全部マイナス方向に調整することにしたら総和はXの倍数になる
    # どれか一つ符号を逆転すると総和がx減るので、総和/d番目が境目になる
    # A = [8, 20]
    # d = 7
    # costs = [1, 6]
    # 20をプラス方向に調整することにすると、マイナス方向の調整は6減ってプラス方向に(7 - 1)増える
    # 1個をマイナス方向をプラス方向に変更すると、マイナス方向のコストの総和の差とプラス方向のコストの総和の差がdだけ詰まる
    # よって、最初全部マイナス方向に調整したときのコストの総和7を7で割ったところが境目
    # プラス方向にはcostが大きい方から変更したい(調整の量が少なくてすむ)ので、最初にソートしておく
    costs = [a % d for a in A]
    costs.sort(reverse=True)
    if sum(costs[:sum(costs) // d + 1]) <= K:
        print(d)
        break

Submission status: Wrong Answer

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

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

divisors.sort(reverse=True)

ans = 0
for d in divisors:
    costs = [a % d for a in A]
    costs.sort()
    plus = sum(costs)
    minus = 0
    for j in range(N):
        if plus == minus:
            break
        else:
            plus -= costs[j]
            minus += d - costs[j]

    if plus <= K:
        print(d)
        break

Submission status: Wrong Answer

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]
    if sum(mods) % d != 0:
        continue
    mods = sorted(mods)
    mod_sum = sum(mods)

    # 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):

        if mod_cumulative == (mod_sum - mod_cumulative) and mod_cumulative <= K:
            print(d)
            exit(0)
        elif mod_cumulative > K:
            break

Submission status: Wrong Answer

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

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

total = sum(A)
divisors = divisor(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:
        break
print(ans)

Submission status: Wrong Answer

Solution code:

import sys
import math
INF = 1 << 20

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    divisor = 1
    # list all possible divisors
    while divisor * divisor <= total:
        if total % divisor == 0:
            candidates.append(divisor)
            candidates.append(total/divisor)
        divisor += 1
    candidates = sorted(candidates, reverse=True)

    for divisor in candidates:
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()
        A = sum(mods)

        need = INF
        index = math.floor(-1 * A/divisor)
        need = sum(mods[0:index])
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

import sys
import math
INF = 1 << 20

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    divisor = 1
    # list all possible divisors
    while divisor * divisor < total:
        if total % divisor == 0:
            candidates.append(divisor)
            candidates.append(total/divisor)
        divisor += 1
    candidates = sorted(candidates, reverse=True)

    for divisor in candidates:
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()
        A = sum(mods)

        need = INF
        index = math.floor(-1 * A/divisor)
        need = sum(mods[0:index])
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

import sys
import math
INF = 1 << 20

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    # list all possible divisors
    for i in range(1, int(math.ceil(math.sqrt(total)))):
        if total % i != 0:
            continue
        candidates.append(i)
        candidates.append(total/i)
    candidates = sorted(candidates, reverse=True)

    for divisor in candidates:
        need = 1 << 20
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()
        A = sum(mods)
        need = INF
        if A % divisor != 0:
            continue
        index = math.floor(-1 * A/divisor)
        need = sum(mods[0:index])
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

import sys
import math

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    
    # list all possible divisors
    for i in range(1, int(math.ceil(math.sqrt(total)))):
        if total % i != 0:
            continue
        candidates.append(i)
        candidates.append(total/i)
    candidates = [i for i in reversed(candidates)]

    for divisor in candidates:
        need = 1 << 20
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()

        
        A = B = 0
        A = sum(mods)
        for i in reversed(range(len(mods))):
            A -= mods[i]
            B += divisor - mods[i]
            need = min(need, max(A,B))
        if need <= K:
            ans = max(ans, divisor)

    return ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

import sys
import math

def main():
    N, K = [int(i) for i in sys.stdin.readline().strip().split()]
    numbers = [int(i) for i in sys.stdin.readline().strip().split()]
    print(solve(N, K, numbers))


def solve(N, K, numbers):

    total = sum(numbers)
    ans = 1
    candidates = []
    candidates.append(total)
    if total % 2 == 0:
        candidates.append(2)
        candidates.append(total / 2)
    
    # list all possible divisors
    for i in range(3, int(math.ceil(math.sqrt(total)))):
        if total % i != 0:
            continue
        candidates.append(i)
        candidates.append(total/i)
    candidates = [i for i in reversed(candidates)]

    for divisor in candidates:
        need = 1 << 20
        mods = []
        for number in numbers:
            mods.append(number % divisor)
        mods.sort()

        A = 0
        B = 0
        
        for j in range(1, len(mods)):
            A += sum(mods[0:j])
            for k in range(j, len(mods)):
                B += divisor - mods[k]
            need = max(A,B)

            if need < K and A == B:
                ans = max(ans, divisor)
            A = 0
            B = 0   
    return ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

ans = 0

for i in range(len(divisors)):
    listA = [0]*N
    for j in range(N):
        listA[j] = A[j] % divisors[i]
    
    listA.sort()
    for j in range(N-int(sum(listA)/divisors[i])):
        if sum(listA[:j+1])<= K:

            ans = max(ans,divisors[i])
            
print(ans)

Submission status: Wrong Answer

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

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

ans = 0

for i in range(len(divisors)):
    listA = [0]*N
    for j in range(N):
        listA[j] = A[j] % divisors[i]
    
    listA.sort()
    for j in range(N):
        if sum(listA[j:-1]) <= K and sum(listA[0:j])<=K:
            ans = max(ans,divisors[i])
            
print(ans)

Submission status: Wrong Answer

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

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

divisors.sort()

ans_temp = 0

for i in range(len(divisors)):
    listA = [0]*N
    for j in range(N):
        listA[j] = A[j] % divisors[i]
    
    listA.sort()
    for j in range(N):
        sumKp = 0
        sumKm = 0
        for k in range(len(listA)):
            if k >= j:
                sumKp += divisors[i] - listA[k]
            else:
                sumKm += listA[k]

        if sumKp > K:
            continue

        sumK = sumKp - sumKm

        if sumK == 0 and divisors[i] > ans_temp:

            ans_temp = divisors[i]
            
print(ans_temp)

Submission status: Wrong Answer

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

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

divisors.sort()

ans_temp = 0

for i in range(len(divisors)):
    listA = [0]*N
    for j in range(N):
        listA[j] = A[j] % divisors[i]
    listA.sort()
    #if divisors[i] > 4:
        #print(listA)
    for j in range(N):
        sumKp = 0
        sumKm = 0
        for k in range(len(listA)):
            if k >= j:
                sumKp += divisors[i] - listA[k]
            else:
                sumKm += listA[k]

        if sumKp > K:
            continue

        sumK = sumKp - sumKm
        #print(str(divisors[i]) + ':' +str(sumK) + ':' + str(sumKm))

        if sumK == 0 and divisors[i] > ans_temp:

            ans_temp = divisors[i]
            
    

print(ans_temp)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split(' ')))
a = [int(i) for i in input().split(' ')]
ave_a = sum(a)/n
count = 0
sa = 0
for i in range(n):
    if a[i] != ave_a and a[i]%ave_a != 0:
        count += 1
    if a[i]%ave_a != 0:
        sa += ave_a - a[i]
if sa == 0 and count <= k:
    print(ave_a)

Submission status: Wrong Answer

Solution code:
# ABC 136 E
import math

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

P = [1,S]
for k in range(2,math.floor(math.sqrt(S))+1):
    if S % k == 0:
        P.append(k)
        P.append(S//k)
P = sorted(P)[::-1]

for e in P:
    t = []
    u = []
    for a in A:
        if a%e != 0:
            t.append(a%e)
            u.append(e-a%e)
    t = sorted(t)
    if len(t) == 0:
        print(e)
        exit(0)
    else:
        p = [f for f in t]
        for k in range(1,len(t)):
            p[k] += p[k-1]
        m = [e-f for f in t]
        print(m)
        for k in range(1,len(t)):
            m[-k-1] += m[-k]
        for k in range(len(t)-1):
            if p[k] == m[k+1] and p[k] <= K:
                print(e)
                exit(0)

Submission status: Wrong Answer

Solution code:
# ABC 136 E
import math

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

P = [1,S]
for k in range(2,math.floor(math.sqrt(S))+1):
    if S % k == 0:
        P.append(k)
        P.append(S//k)
P = sorted(P)[::-1]

for e in P:
    t = []
    u = []
    for a in A:
        if a%e != 0:
            t.append(a%e)
            u.append(e-a%e)
    t = sorted(t)
    if len(t) == 0:
        print(e)
        exit(0)
    else:
        p = [0]*len(t)
        p[0] = t[0]
        for k in range(1,len(t)):
            p[k] = p[k-1] + t[k]
        m = [e-f for f in t]
        for k in range(1,len(t)):
            m[k-1] += m[k]
        for k in range(len(t)-1):
            if p[k] == m[k+1] and p[k] <= K:
                print(e)
                exit(0)

Submission status: Wrong Answer

Solution code:
import math
N,K = map(int,input().split())

A_array = list(map(int,input().split()))

# print(A_array)

A_sum = sum(A_array)

candidate_array = []

for i in range(1,int(math.sqrt(A_sum))+1):
    if A_sum % i == 0:
        candidate_array.append(i)
        if A_sum // i != i:
            candidate_array.append(A_sum//i)

candidate_array.sort()

left = 0
right = len(candidate_array) - 1

# print(candidate_array)
while right - left > 0:
    check = (left+right+1) // 2
    check_num = candidate_array[check]
    # print(check_num)
    q_array = [a % check_num for a in A_array]
    q_array.sort()
    # print(q_array)
    start = 0
    rest = N * check_num - sum(q_array)
    for q in q_array:
        start += q
        rest -= (check_num-q)
        # print(start,rest)
        if start == rest:
            break
    if start > K: #NG
        if right == check:
            break
        right = check
    else: #OK
        left = check
    # print(left,right,check)
print(candidate_array[left])

Submission status: Wrong Answer

Solution code:
import math
N,K = map(int,input().split())

A_array = list(map(int,input().split()))

# print(A_array)

A_sum = sum(A_array)

candidate_array = []

for i in range(1,int(math.sqrt(A_sum))+1):
    if A_sum % i == 0:
        candidate_array.append(i)
        if A_sum // i != i:
            candidate_array.append(A_sum//i)

candidate_array.sort()

left = 0
right = len(candidate_array) - 1

# print(candidate_array)
while right - left > 0:
    check = (left+right+1) // 2
    check_num = candidate_array[check]
    # print(check_num)
    q_array = [a % check_num for a in A_array]
    q_array.sort()
    # print(q_array)
    k = 0
    for i,q in enumerate(q_array):
        if (k + q) <= K:
            k += q
        else:
            break
    else:
        i = N
    rest = check_num * (N-i) - sum(q_array[i:])
    # print(i,q,rest)
    if rest > k: #NG
        if right == check:
            break
        right = check
    else: #OK
        left = check
    # print(left,right,check)
print(candidate_array[left])

Submission status: Wrong Answer

Solution code:
import sys
import math

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


def ok(x):
    b = []
    for an in a:
        b.append(an % x)
    b.sort(reverse=True)
    print(x, a, b, file=sys.stderr)
    t = int(sum(b) / x)
    print(t, file=sys.stderr)
    if t == 0:
        return True
    return True if sum(b[:t]) <= k else False


s = 0
for an in a:
    s += an

ans = 1
for x in range(1, int(math.sqrt(s)) + 1):
    if s % x != 0:
        continue
    if ok(x):
        ans = max(ans, x)
    if ok(int(s / x)):
        ans = max(ans, x)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
S=sum(A)
facts=set()
for i in range(1,int(S**0.5)+1):
    if S%i==0:
        facts.add(i)
        facts.add(S//i)
for f in sorted(facts,key=lambda x:-x):
    rs = [i%f for i in A]
    rs2=sorted(rs)
    rsr = [f-r for r in rs2]
    if f-rs2[-1]>K and rs2[-1]>K:
        continue
    cum=0
    ruiseki=[0]*(N)
    tmp=0
    for i,a in enumerate(rs2):
        cum+=a
        ruiseki[i]=cum
    for i in range(N-1):
        s_l=ruiseki[i]
        if s_l==0:continue
        s_h = f*(N-i-1)-(ruiseki[-1]-s_l)
        if max(s_l,s_h)<=K:
            print(f)
            break
    else:
        continue
    break

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
S=sum(A)
facts=set()
for i in range(1,int(S**0.5)+1):
    if S%i==0:
        facts.add(i)
        facts.add(S//i)
for f in sorted(facts,key=lambda x:-x):
    rs = [i%f for i in A]
    rs2=sorted(rs)
    rsr = [f-r for r in rs2]
    if f-rs2[-1]>K and rs2[-1]>K:
        continue
    cum=0
    ruiseki=[0]*(N)
    for i,a in enumerate(rs2):
        cum+=a
        ruiseki[i]=cum
    for i in range(N-1):
        s_l=ruiseki[i]
        if s_l==0:continue
        s_h = f*(N-i-1)-(ruiseki[-1]-s_l)
        d1,d2=divmod(s_h,s_l)
        if d2==0 and s_l+(d1-1)*f<=K:
            print(f)
            break
    else:
        continue
    break

Submission status: Wrong Answer

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


def factorize(n: int) -> dict:
    b = 2
    fct = defaultdict(int)
    fct[n] = 1
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct[b] += 1
        b = b + 1
    if n > 1:
        fct[n] = 1
    return fct


def solve(B, f):
    cost = sum(B)
    cost = sum(B[:-cost//f])
    return cost


fct = factorize(sum(A))
for f in sorted(list(fct.keys()), reverse=True):
    B = sorted([b%f for b in A])
    if K >= solve(B, f):
        print(f)
        quit()

Submission status: Wrong Answer

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


def factorize(n: int) -> dict:
    b = 2
    fct = defaultdict(int)
    fct[n] = 1
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct[b] += 1
        b = b + 1
    if n > 1:
        fct[n] = 1
    return fct


def solve(B, f):
    cost = sum(B)
    cost = sum(B[:-cost//f])
    return cost


fct = factorize(sum(A))
for f in sorted(list(fct.keys()), reverse=True):
    B = sorted([b%f for b in A if b%f != 0])
    if K >= solve(B, f):
        print(f)
        quit()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# A.sort()
totalA = sum(A)
# print (totalA)

def make_divisors(n): #nの約数をO(root(n))で全列挙、sortして取り出すときはO(root(n) log(n))
    import math
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0: #割り切れるとき
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    divisors.sort(reverse = True)
    return divisors

divisors_lst = make_divisors(totalA)
# print (divisors_lst)
for i in divisors_lst: #答えの候補を全探索
    lst = []
    for j in A:
        lst.append(j % i)
    lst.sort()
    total_lst = sum(lst)
    if total_lst <= K:
        print (i)
        exit()
    tmp = 0
    for k in lst:
        tmp += k
        total_lst -= k
        if max(tmp, total_lst) <= K:
            print (i)
            exit()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
# from numba import njit


def solve(A, K, div):
    for d in range(div.shape[0] - 1, 0, -1):
        res = div[d]
        B = np.sort(A % res)
        if B[B.shape[0] - 1] == 0:
            return res
        i = 0
        j = B.shape[0] - 1
        sreqired = B[i]
        lreqired = B[j]
        while j - i > 1:
            if sreqired < lreqired:
                i += 1
                sreqired += B[i]
            else:
                j -= 1
                lreqired += res - B[j]
        if sreqired <= K:
            return res
    return 1


def divisor(d, div):
    r = int(d ** 0.5 + 0.0000001) + 1
    ind = 0
    for i in range(1, r):
        if d % i == 0:
            div[ind] = i
            ind += 1
            div[ind] = d // i
            ind += 1
        if d % r == 0:
            div[ind] = r
            ind += 1
    return ind


line = sys.stdin.readline
N, K = map(int, line().split())
A = np.fromstring(line(), dtype=np.int64, sep=' ')
d = A.sum()
div = np.empty(10 ** 6, dtype=np.int64)
num = divisor(d, div)
div = np.sort(div[:num])
print(solve(A, K, div))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
# from numba import njit


def solve(A, K, div):
    for d in range(div.shape[0] - 1, 0, -1):
        res = div[d]
        B = np.sort(A % res)
        if B[B.shape[0] - 1] == 0:
            return res
        i = 0
        j = B.shape[0] - 1
        sreqired = B[i]
        lreqired = B[j]
        while j - i > 1:
            if sreqired < lreqired:
                i += 1
                sreqired += B[i]
            else:
                j -= 1
                lreqired += res - B[j]
        if sreqired <= K:
            return res
    return 1


def divisor(d, div):
    r = int(d ** 0.5 + 0.0000001) + 1
    ind = 0
    for i in range(1, r):
        if d % i == 0:
            div[ind] = i
            ind += 1
            div[ind] = d // i
            ind += 1
        if d % r == 0:
            div[ind] = r
            ind += 1
    return ind

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
# from numba import njit


def solve(A, K, div):
    for d in range(div.shape[0] - 1, 0, -1):
        res = div[d]
        B = np.sort(A % res)
        if B[B.shape[0] - 1] == 0:
            return res
        i = 0
        j = B.shape[0] - 1
        cost = res - B[j]
        scost = 0
        while j - i > 0:
            for n in range(i, j):
                scost += B[n]
                if scost > cost:
                    j -= 1
                    cost += res - B[j]
                    i = n + 1
                    break
            else:
                i = j

        if cost <= K:
            return res
    return 1


def divisor(d, div):
    r = int(d ** 0.5 - 0.0000001) + 1
    ind = 0
    for i in range(1, r):
        if d % i == 0:
            div[ind] = i
            ind += 1
            div[ind] = d // i
            ind += 1
    if d % r == 0:
        div[ind] = r
        ind += 1
    return ind


line = sys.stdin.readline
N, K = map(int, line().split())
A = np.fromstring(line(), dtype=np.int64, sep=' ')
d = A.sum()
div = np.empty(10 ** 6, dtype=np.int64)
num = divisor(d, div)
div = np.sort(div[:num])
print(solve(A, K, div))

Submission status: Wrong Answer

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

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

s = sum(a)

dlist = []
for p in range(1,int(s**(1/2))+1):
    if s % p == 0:
        dlist.append(p)
        dlist.append(int(s/p))

anslist = []

for d in dlist:
    r = [a[_] % d for _ in range(n)]
    r.sort()

    w = [r[0]]#累積和
    for i in range(1,n):
        w.append(w[-1]+r[i])
    
    can = "no"
    for j in range(0,n):
        if max(w[j],d*(n-j-1)-w[n-1]+w[j])<k:
            can = "yes"
            break
    if can == "yes":
        anslist.append(d)

print(max(anslist))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# A.sort()
totalA = sum(A)
# print (totalA)

def make_divisors(n): #nの約数をO(root(n))で全列挙、sortして取り出すときはO(root(n) log(n))
    import math
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0: #割り切れるとき
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    divisors.sort(reverse = True)
    return divisors

divisors_lst = make_divisors(totalA)

for i in divisors_lst:
    lst = []
    for j in A:
        lst.append(min(j % i, i - i % j))

    if sum(lst)//2 <= K:
        print (i)
        exit()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
# from numba import njit


def solve(A, K, div):
    for d in range(div.shape[0] - 1, 0, -1):
        res = div[d]
        B = np.sort(A % res)
        if B[B.shape[0] - 1] == 0:
            return res
        i = 0
        j = B.shape[0] - 1
        sreqired = B[i]
        lreqired = B[j]
        while j - i > 1:
            if sreqired < lreqired:
                i += 1
                sreqired += B[i]
            else:
                j -= 1
                lreqired += res - B[j]
        if sreqired <= K:
            return res
    return 1


def divisor(d, div):
    r = int(d ** 0.5 + 0.1)
    ind = 0
    for i in range(1, r):
        if d % i == 0:
            div[ind] = i
            ind += 1
            div[ind] = d // i
            ind += 1
    return ind


line = sys.stdin.readline
N, K = map(int, line().split())
A = np.fromstring(line(), dtype=np.int64, sep=' ')
d = A.sum()
div = np.empty(10 ** 6, dtype=np.int64)
num = divisor(d, div)
div = np.sort(div[:num])
print(solve(A, K, div))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
# from numba import njit


def solve(A, K, div):
    for d in range(div.shape[0] - 1, 0, -1):
        res = div[d]
        B = np.sort(A % res)
        i = 0
        j = B.shape[0] - 1
        sreqired = B[i]
        lreqired = B[j]
        while j - i > 1:
            if sreqired < lreqired:
                i += 1
                sreqired += B[i]
            else:
                j -= 1
                lreqired += res - B[j]
        if sreqired <= K:
            return res
    return 1


def divisor(d, div):
    r = int(d ** 0.5 + 0.1)
    ind = 0
    for i in range(1, r):
        if d % i == 0:
            div[ind] = i
            ind += 1
            div[ind] = d // i
            ind += 1
    return ind


line = sys.stdin.readline
N, K = map(int, line().split())
A = np.fromstring(line(), dtype=np.int64, sep=' ')
d = A.sum()
div = np.empty(10 ** 6, dtype=np.int64)
num = divisor(d, div)
div = np.sort(div[:num])
print(solve(A, K, div))

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

input1 = input()
input2 = input()

N = int(input1.split()[0])
K = int(input1.split()[1])

nums = [int(s) for s in input2.split()]

divs = make_divisors(sum(nums))

possible = []

for i in divs:
    nord = [s%i for s in nums]
    nord.sort()
    mt_size = sum(nord) // i
    moves = sum(nord[0:N-1-mt_size])
    if moves <= K:
        possible.append(i)

print(int(max(possible)))