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

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def fact(n):
        if n < 4:
            return [n,1]
        i = 2
        res = [1,n]
        while i*i <= n:
            if n%i == 0:
                res.append(i)
                m = n//i
                if m != i:
                    res.append(m)
            i += 1
        res.sort(reverse = True)
        return res
    n,k = LI()
    a = LI()
    s = sum(a)
    f = fact(s)
    for i in f:
        s = [j%i for j in a]
        s.sort()
        s = list(accumulate(s))
        for j in range(n-1):
            sl = s[j]
            sr = i*(n-j-1)-s[-1]+s[j]
            if sl == sr:
                break
        if sl <= k:
            print(i)
            return
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

    divisors.sort()
    return divisors

l=make_divisors(s)
ans=1
for y in l[1:]:
    x=[i%y for i in a]
    x.sort()
    ss=sum(x)
    l1=[0]
    for i in range(n):
        l1.append(l1[-1]+x[i])
    l2=[0]
    for i in range(n):
        l2.append(l2[-1]+y-x[-i-1])
    l2.reverse()
    c=-1
    for i in range(n+1):
        if l1[i]==l2[i]:
            c=l1[i]
            break
    if c>-1 and c<=k:
        ans=max(ans,y)

print(ans)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    sumA = sum(A)
    D = []
    for i in range(1, sumA + 1):
        if i ** 2 > sumA: break
        if sumA % i == 0:
            D.append(i)
            if i ** 2 != sumA: D.append(sumA // i)
    D.sort(reverse = True)
    for i, d in enumerate(D):
        L = []
        count = 0
        for a in A:
            if a % d > 0: 
                L.append(a % d)
                count += 1
        L.sort()
        if count > 0:
            minus, plus = [0] * count, [0] * count
            minus[0] = L[0]
            plus[count - 1] = d - L[count - 1]
            for i in range(1, count):
                minus[i] = minus[i-1] + L[i]
                plus[count - 1 - i] = plus[count - i] +  d - L[count - 1 - i]
            Op = K + 1
            for i in range(count - 1):
                if abs(minus[i] - plus[i + 1]) % d == 0: Op = min(Op, max(minus[i], plus[i + 1]))
            if Op <= K:
                print(d)
                break
    else: print(1)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def make_divisors(n: int) -> list:
    """自然数nの約数を列挙したリストを出力する
    計算量: O(sqrt(N))
    入出力例: 12 -> [1, 2, 3, 4, 6, 12]
    """
    divisors = []
    for k in range(1, int(n ** 0.5) + 1):
        if n % k == 0:
            divisors.append(k)
            if k != n // k:
                divisors.append(n // k)
    divisors = sorted(divisors)
    return divisors


def solve(val):
    res = []
    for i in range(n):
        tmp = a[i] % val
        if tmp == 0:
            continue
        res.append(a[i] % val)
    res = sorted(res)
    if not res:
        return True
    l_val = 0
    for i in range(len(res)):
        l_val += res[i]
        if l_val > k:
            l_pos = i - 1
            break
    else:
        return True
    r_val = 0
    for i in range(l_pos + 1, len(res)):
        r_val += val - res[i]
    return r_val <= k
            
      
        
    
n, k = map(int, input().split())
a = list(map(int, input().split()))

sum_a = sum(a)
div = make_divisors(sum_a)
ans = 0
for i in div:
    if solve(i):
        ans = max(ans, i)
print(ans)

Submission status: Accepted

Solution code:
def divisor(n):
    divisors = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.append(i)
            if i * i < n:
                divisors.append(n // i)
        i += 1
    divisors.sort()
    return divisors

N, K = map(int, input().split())
A = list(map(int, input().split()))
divisors = divisor(sum(A))
for d in divisors[::-1]:
    r = [a % d for a in A]
    r.sort(reverse=True)
    i = sum(r) // d
    if sum(r[i:]) <= K:
        print(d)
        exit()

Submission status: Accepted

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

def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass
f = divisor(m)
f.sort(reverse=True)

for p in f:
  b = [x%p for x in a]
  b.sort()
  t = 0
  c = n
  for x in b:
    if x + t > k:
      break
    t += x
    c -= 1
  if c*p - sum(b) + t <= k:
    print(p)
    break

Submission status: Accepted

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

def canMake(n):
    B = [a % n for a in A]
    B.sort()

    left = 0
    right = sum(B)
    for i, b in enumerate(B, start=1):
        left += b
        right -= b
        if left == n * (N - i) - right:
            return left <= K
    return False

ans = 1
for i in range(1, int(S**0.5) + 100):
    if S % i != 0:
        continue
    k = S // i

    if canMake(i):
        ans = max(ans, i)
    if canMake(k):
        ans = max(ans, k)
        break

print(ans)

Submission status: Accepted

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

def ok(d):
    m = sorted(a % d for a in a)
    s, e, plus, minus = 0, len(m) - 1, 0, 0
    while True:
        if s > e:
            return (plus == minus)
        if plus <= minus:
            plus += m[s]
            if plus > k:
                return False
            s += 1
        else:
            minus += d - m[e]
            if minus > k:
                return False
            e -= 1
    return False

b = sum(a)
ret = 1
d = 1
while d * d <= b:
    if b % d == 0:
        if ok(d):
            ret = max(ret, d)
        if ok(b // d):
            ret = max(ret, b //d)
    d += 1
print(ret)

Submission status: Accepted

Solution code:
def divisor(n):
    divisors = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.append(i)
            if i * i < n:
                divisors.append(n // i)
        i += 1
    divisors.sort()
    return divisors


N, K = map(int, input().split())
A = list(map(int, input().split()))
divisors = divisor(sum(A))
for d in divisors[::-1]:
    rem = [a % d for a in A]
    rem.sort(reverse=True)
    i = sum(rem) // d
    if sum(rem[i:]) <= K:
        print(d)
        exit()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

def divisor(n):
    divisors = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.append(i)
            if i != n / i:
                divisors.append(n // i)
        i += 1
    divisors.sort()
    return divisors


N, K = map(int, input().split())
A = list(map(int, input().split()))
divisors = divisor(sum(A))
for d in divisors[::-1]:
    heap = []
    s = 0
    for a in A:
        x = a // d * d - a
        heap.append(x)
        s += -x
    heapify(heap)
    n = 0
    for _ in range(s // d):
        x = heappop(heap)
        if x + d > K:
            break
        else:
            if x + d > 0:
                n += x + d
            heappush(heap, x + d)
    else:
        if sum(abs(x) for x in heap) <= 2 * K:
            print(d)
            exit()

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a)
d=set()
for i in range(1,int(sum(a)**0.5)+5):
    if s%i==0: d.add(i);d.add(s//i)
d=sorted(list(d),reverse=True)
for x in d:
    b=sorted([a[i]%x for i in range(n)],reverse=True)
    s=sum(b)
    p=s//x
    if s-sum(b[:p])<=k: break
print(x)

Submission status: Accepted

Solution code:
def divisor(n):
  ass=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ass.append(i)
      if i!=n//i:ass.append(n//i)
  return ass
_,k=map(int,input().split())
a=list(map(int,input().split()))
for ans in sorted(divisor(sum(a)))[::-1]:
  b=[i%ans for i in a if i%ans]
  n=len(b)
  b.sort()
  m=[0]+[i for i in b]
  p=[ans-i for i in b]+[0]
  for i in range(n):
    m[i+1]+=m[i]
    p[-i-2]+=p[-i-1]
  flag=False
  for i in range(n+1):
    if max(m[i],p[i])>k:continue
    if abs(m[i]-p[i])%ans!=0:continue
    flag=True
  if flag:print(ans);exit()

Submission status: Accepted

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


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 for a in A if a % x != 0]
    modX.sort()

    L = len(modX)
    rtn = False

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

        cnt_minus = sum(minus)
        cnt_plus = x * (L - i) - sum(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: Accepted

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

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

    divisors.sort(reverse=True)
    return divisors

G = make_divisors(s)

from itertools import accumulate

for g in G:
    B = [a%g for a in A]
    B.sort()
    B = [0] + B
    B = list(accumulate(B))
    p = 0
    q = 0
    for i in range(n-1):
        p = B[i+1]
        q = g*(n-1-i)-(B[-1]-B[i+1])
        if max(p, q) <= k and (p-q)%g == 0:
            break
    else:
        continue
    break
print(g)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

N, K = map(int, input().split())
*A, = map(int, input().split())
cands = divisors(sum(A))
for d in sorted(cands, reverse=True):
    rems = sorted([a % d for a in A])
    cumsum_rems = [0] + list(accumulate(rems))
    for i in range(1, N):
        minus = cumsum_rems[i]
        plus = d * (N - i) - (cumsum_rems[N] - minus)
        if max(minus, plus) <= K: break
    else:
        continue
    break
print(d)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

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)

    divisors.sort()
    return divisors

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

div = divisors(total)
ans = 1
for d in div:
    modd = []
    for item in a:
        modd.append(item % d)
    modd.sort(reverse=True)
    plus = sum(modd)
    opr = 0
    for i, item in enumerate(modd):
        if plus == 0:
            opr += sum(modd[i:])
            break
        plus -= d
        opr += d - item 

    if opr <= k * 2:
        ans = max(ans, d)
print(ans)

Submission status: Accepted

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

def isOk(n):
    B = [a % n for a in A]
    B.sort()

    now = 0
    S = sum(B)
    for i, b in enumerate(B[: -1]):
        now += b
        S -= b
        if now == n * (N - i - 1) - S and now <= K:
            return True
    return False

ans = 1
for i in range(1, int(S**0.5) + 100):
    if S % i != 0:
        continue
    j = S // i

    if isOk(i):
        ans = max(ans, i)
    if isOk(j):
        ans = max(ans, j)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
ans = 1
div = []
for i in range(1,int(S**0.5)+2):
    if S%i == 0:
        if S//i != i:
            div.append(S//i)
            div.append(i)
        else:
            div.append(i)
div.sort()
L = []
for i in range(len(div)):
    cur = div[i]
    mod = []
    for j in range(n):
        if A[j]%cur != 0:
            mod.append(A[j]%cur)
    if len(mod) == 0:
        ans = max(ans, cur)
    else:
        mod.sort()
        mod_dash = []
        for j in range(len(mod)):
            mod_dash.append(cur-mod[j])
        mod2 = [mod[0]]
        mod3 = [mod_dash[0]]
        for j in range(1,len(mod)):
            t = mod2[j-1]+mod[j]
            mod2.append(t)
            u = mod3[j-1]+mod_dash[j]
            mod3.append(u)
        c = 10**10
        for j in range(1,len(mod2)):
            c = min(c, max(mod2[len(mod2)-j-1],mod3[len(mod3)-1]-mod3[len(mod3)-j-1]))
        if c <= k:
            ans = max(ans, cur)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def make_divisors(n): # nの約数を列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

# 全ての合計の約数が答えの候補、上から可能かどうか見ていく
N, K = lr()
A = np.array(lr())
total = A.sum()
D = make_divisors(total) # 降順
for d in D:
    B = A % d   
    B.sort()
    inc = d - B
    B_cum = B.cumsum()
    inc_cum = inc.cumsum()
    for i in range(N):
        x = B_cum[i]
        y = inc_cum[N-1] - inc_cum[i]
        if x > K: # xは単調増加
            break
        if y > K:
            continue
        if (x+y) // 2 <= K:
            print(d); exit()

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def make_divisors(n): # nの約数を列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

# 全ての合計の約数が答えの候補、上から可能かどうか見ていく
N, K = lr()
A = np.array(lr())
total = A.sum()
D = make_divisors(total) # 降順
for d in D:
    B = A % d   
    B.sort()
    inc = d - B
    B_cum = B.cumsum()
    inc_cum = inc.cumsum()
    for i in range(N):
        x = B_cum[i]
        y = inc_cum[N-1] - inc_cum[i]
        if x > K or y > K:
            continue
        if (x+y) // 2 <= K:
            print(d); exit()

Submission status: Accepted

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

import math



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

    s = sum(A)

    D1 = []
    D2 = []

    for i in range(1, int(math.sqrt(s))+1):
        if s%i == 0:
            D1.append(s//i)
            D2.append(i)

    for d in D1 + list(reversed(D2)):
        B = sorted([a%d for a in A])
        x = sum(B[:-sum(B)//d])
        
        if x <= K:
            print(d)
            return

main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a)
ii=[]
for i in range(1,int(s**0.5)+1):
  if s%i>0:
    continue
  ii+=[i,s//i]
ii.sort(reverse=True)
for i in ii:
  r=[]
  for j in range(n):
    r+=[a[j]%i]
  r.sort()
  b=0
  l=0
  while l<n and b+r[l]<=k:
    b+=r[l]
    l+=1
  if sum([i-x for x in r[l:]]) <= k:
    print(i)
    break

Submission status: Accepted

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())

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

M=sum(A)
maxi=round(M**.5)+2
lst=[]
i=2

for i in range(1,maxi):
    if M%i==0:
        lst.append(i)
        lst.append(M//i)


lst.sort(reverse=True)
for l in lst:
    B=deque(sorted([i%l for i in A if i%l!=0]))
    _K=K
    #print(B,l)
    while len(B)>=2 and _K:

        n=min(B[0],l-B[-1],_K)
        B[0]-=n
        B[-1]+=n
        _K-=n
        if not B[0]%l:
            B.popleft()
        if not B[-1]%l:
            B.pop()

    if not B:
        print(l)
        exit()

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import accumulate


def common_divisors(x):
    ret = []
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)

    return ret


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

sm = sum(a)
cd = common_divisors(sm)

ans = 0
for ecd in cd:
    r = [e % ecd for e in a]
    r.sort()
    sub = [0] + list(accumulate(r))
    add = [0] + list(accumulate(ecd - e for e in r[::-1]))
    add = add[::-1]
    for sb, ad in zip(sub, add):
        if sb == ad and sb <= k:
            ans = max(ans, ecd)

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import accumulate


def common_divisors(x):
    ret = []
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)

    return ret


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

sm = sum(a)
cd = common_divisors(sm)

ans = 1
for ecd in cd:
    r = [e % ecd for e in a]
    r.sort()
    sub = [0] + list(accumulate(r))
    add = [0] + list(accumulate(ecd - e for e in r[::-1]))
    add = add[::-1]
    for sb, ad in zip(sub, add):
        if sb == ad and sb <= k:
            ans = max(ans, ecd)

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import accumulate


def common_divisors(x):
    ret = []
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)

    return ret


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

sm = sum(a)
cd = common_divisors(sm)

ans = 1
for ecd in cd:
    r = [e % ecd for e in a]
    r.sort()
    acc = [0] + list(accumulate(r))
    for i in range(1, n + 1):
        sub = acc[i-1]
        add = ecd * (n - i + 1) - (acc[n] - acc[i-1])
        if sub == add:
            if sub <= k:
                ans = max(ans, ecd)

print(ans)

Submission status: Accepted

Solution code:

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

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

divisor.sort()

def judge(x):
    # 全てのAiをK回以下の操作で0(mod x)にできるか？
    modlist = []
    for a in A:
        b = a%x
        modlist.append([b, x-b])
    modlist.sort()
    sum1 = [0]*(N+1)
    sum2 = [0]*(N+1)
    idx = 0
    for b,c in modlist:
        sum1[idx+1] = sum1[idx] + b
        sum2[idx+1] = sum2[idx] + c
        idx += 1
    
    res = 10**10
    for i in range(1,N+1):
        tmp = max(sum1[i], sum2[N]-sum2[i])
        res = min(res, tmp)
    
    if res>K:
        return False
    else:
        return True
    
ok = 1
for d in divisor:
    if judge(d):
        ok = d


print(ok)

Submission status: Accepted

Solution code:
import math

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

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

x=sum(A)

X=[]

for i in range(1,int(math.sqrt(x))+1):
    if x%i==0:
        X.append(i)
        X.append(x//i)
X.sort(reverse=True)

for i in X:
    B=[]
    for j in range(n):
        B.append(A[j]%i)
    B.sort()
    if sum(B[:-1*(sum(B)//i)])<=k:
        print(i)
        break

Submission status: Accepted

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

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

ans = 1
for d in div:
    R = [a % d for a in A]
    R.sort()
    r = sum(R) // d
    l = N - r
    need = sum(R[:l])
    if need <= K:
        ans = max(ans, d)
print(ans)

Submission status: Accepted

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

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

ans = 1
for d in div:
    now = 10 ** 18
    R = [a % d for a in A]
    R.sort()
    Rsum = sum(d - r for r in R)
    Lsum = 0
    for r in R:
        Lsum += r
        Rsum -= d - r
        now = min(now, max(Lsum, Rsum))

    if now <= K:
        ans = max(ans, d)

print(ans)

Submission status: Accepted

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 SumArea(r, l, a2):
    return a2[l]-a2[r]

def judge(cand, a, k):
    m_list = [i%cand for i in a]
    m_list.sort()
    p_list = [cand-r for r in m_list]
    
    # 累積和
    b=list(range(1,30))
    m2=[0]
    p2=[0]
    for i in m_list:m2.append(m2[-1]+i)
    for i in p_list:p2.append(p2[-1]+i)
        
    length = len(a)
    for i in range(length):
        m_total  = SumArea(0, i, m2)
        p_total = SumArea(i, length, p2)
        if m_total == p_total and p_total <= k:
            return True
    return False
    
        
n,k = map(int, input().split())
a = list(map(int, input().split()))
pflag = True
# 候補は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):
        print(cand)
        pflag = False
        break
if pflag:
    print(1)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

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

def isPrime(x):
    if x < 2 or x % 2 == 0:
        return False
    if x == 2:
        return True
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 2
    return True

def divisor(x):
    res = []
    i = 1
    while i * i <= x:
        if x % i == 0:
            res.append(i)
            if i * i != x:
                res.append(x // i)
        i += 1
    res = sorted(res)
    return res

def factor(x):
    res = []
    if x == 1:
        res.push_back(1)
        return res
    i = 2
    while i * i <= x:
        while x % i == 0:
            res.append(i)
            x //= i
    if x != 1:
        res.append(x)
    res = sorted(res)
    return res

        


if __name__ == "__main__":
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A = sorted(A)
    sum_v = sum(A)
    div = divisor(sum_v)
    div = sorted(div, reverse=True)
    for e in div:
        ok = True
        b = [int(a % e) for a in A]
        b = sorted(b)
        v = sum(b)
        v //= e
        ans = 0
        for i in range(N-v):
            ans += b[i]
        
        if ans <= K:
            print(e)
            exit()

Submission status: Accepted

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

S = sum(A)
ans = 0

for i in range(1,int(S**0.5)+1):
    if S%i != 0:
        continue
        
    for j in range(2):
        d = i if j else S//i
        B = sorted(map(lambda a:a%d,A))
        C = [0]
        for k in range(N):
            C.append(C[-1]+B[k])
            
        for k in range(N+1):
            if ((N-k)*d-(C[-1]-C[k])-C[k])%d == 0:
                if max(C[k],(N-k)*d-(C[-1]-C[k])) <= K:
                    ans = max(ans,d)
                    
print(ans)

Submission status: Accepted

Solution code:
def main():
    N,K,*A=map(int, open(0).read().split())
    S=sum(A)
    X=[S]
    for i in range(2,int(S**.5)+1):
        if S%i==0:
            X.append(i)
            if i*i!=S:
                X.append(S//i)
    ans=1
    for x in X:
        B=[a%x for a in A]
        y=sum(B)//x
        z=sum(sorted(B, reverse=True)[y:])
        if z<=K:
            ans=max(ans,x)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def yaku(N):
    res = []
    for i in range(1, round(N**(1/2)) + 3 ):
        if N%i == 0:
            res.append(i)

    res2 = [N//i for i in res]
    res = list(set(res + res2))
    return res

ys = yaku(sum(A))
ys.sort(reverse=True)
for y in ys:
    M = [a%y for a in A if a%y]
    ma = 0
    mi = y*len(M) - sum(M)
    M.sort()
    for m in M:
        ma += m
        mi -= (y - m)
        if ma == mi:
            break
    if ma <= K:
        print(y)
        exit()

Submission status: Accepted

Solution code:
import heapq as h

def partions(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d


N,K=map(int,input().split())
A=list(map(int,input().split()))
s=sum(A)
candidate=partions(s)
ans=1
for i in range(0,len(candidate)):
    X=[A[j]%candidate[i] for j in range(0,N)]
    s=sum(X)//candidate[i]
    test=0
    h.heapify(X)
    for j in range(0,N-s):
        test=h.heappop(X)
    test=candidate[i]*s-sum(X)
    if K>=test:
        ans=candidate[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr())
sum = A.sum()
# Aiが1以上のため、answerはsumの約数

def make_divisors(n): # 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

B = make_divisors(sum)

for x in B[::-1]:
    c = A % x
    c.sort()
    d = x - c
    c_cum = c.cumsum()
    d_cum = d.cumsum()
    
    for i in range(N):
        y = c_cum[i]
        z = d_cum[N-1] - d_cum[i]
        if y > K or z > K:
            continue
        result = (y + z) // 2
        if result <= K:
            print(x)
            exit()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    m = sum(A)
    d = []
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            d.append(i)
            if i != m // i:
                d.append(m//i)
    d.sort(reverse=True)
    for j in d:
        if j > K + max(A):
            continue
        l = []
        for i in A:
            l.append(i % j)
        t = N - sum(l) // j
        l.sort()
        if sum(l[:t]) <= K:
            print(j)
            return
    print(1)
main()

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = sum(A)

# 答えの候補を列挙
ans_candidates = []
for n in range(1, int(M ** 0.5) + 1):
    if M % n == 0:
        ans_candidates.append(n)
        ans_candidates.append(M // n)


ans = 0
for X in ans_candidates:
    A_mod = sorted([a % X for a in A])
    U = [X - a for a in A_mod]
    D = [-a for a in A_mod]  # わかりやすいので

    U = list(accumulate(U))
    D = list(accumulate(D))

    for i in range(N):
        if -D[i] > K:
            break

        if -D[i] == (U[-1] - U[i]):
            ans = max(ans, X)
            break

print(ans)

Submission status: Accepted

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

S = sum(A)
candidates = []
for i in range(1, int(S**0.5)+1):
    if S%i:continue
    a, b = i, S//i
    
    candidates.append(a)
    if a!=b:
        candidates.append(b)
candidates.sort()

ans = 0
for d in candidates:
    rems = []
    rems_size, rems_sum = 0, 0

    for i in A:
        if i%d:
            rems.append(i%d)
            rems_size += 1
            rems_sum += i%d

    rems.sort()

    a = 0
    for i, j in enumerate(rems[:-1], start=1):
        a += j
        b = d*(rems_size-i)-(rems_sum-a)
        if max(a, b)<=K:
            ans = max(ans, d)
    if not rems:
        ans = max(ans, d)

print(ans)