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:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(A, n):
    L = [0] + sorted([a % n for a in A if a % n != 0])
    R = [n - a for a in L[1:]] + [0]
    for i in range(len(L) - 1):
        L[i + 1] += L[i]
        R[len(L) - i - 2] += R[len(L) - i - 1]

    res = 10 ** 20
    for l, r in zip(L, R):
        res = min(res, max(l, r))
    return res


def main():
    N, K = read_values()
    A = read_list()
    S = sum(A)
    
    res = 0
    for n in range(1, int(S ** 0.5) + 1):
        if S % n != 0:
            continue
        m = S // n
        if f(A, n) <=  K:
            res = max(res, n)
        if f(A, m) <=  K:
            res = max(res, m)
    print(res)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

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

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

    ans = 1
    for x in d:

        B = []
        s = 0
        for y in A:
            c1 = x - y % x
            B.append((c1,y))
            s += c1

        B.sort(reverse=True)
        cnt = 0
        for y,_ in B[s//x:]:
            cnt += y
        if cnt <= K:
            ans = max(ans,x)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
s = sum(a)
def fs(n):
    s = set()
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            s.add(i)
            s.add(n//i)
    l = sorted(list(s))
    return l
l = fs(s)
def sub(v):
    val0 = [item%v for item in a if item%v!=0]
    val1 = [(v-item)%v for item in val0]
    val0.sort()
    val1.sort(reverse=True)
#     print(val0,val1)
    i = 0
    j = len(val0)-1
    ans = 0
    while i<j:
        if val0[i]<val1[j]:
            val1[j] -= val0[i]
            ans += val0[i]
            i += 1
        else:
            val0[i] -= val1[j]
            ans += val1[j]
            j -= 1
    return ans
for v in reversed(l):
    if k>=sub(v):
        break
print(v)

Submission status: Accepted

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

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

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

sumA = sum(A)

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

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

Submission status: Accepted

Solution code:
from collections import deque

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


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


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                                                                                     31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p] + 1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret, reverse=True)


def is_ok(n):
    B_ = []
    for a in A:
        b = a % n
        B_.append(b)
    B_.sort()
    B = deque(B_)
    start = 0
    end = 0
    cnt = 0
    while B:
        start += B.popleft()
        while start > end:
            end += n - B.pop()
        end -= start
        cnt += start
        start = 0
        if cnt > K:
            return False
    return True






Can = divisors(AS)

for c in Can:
    if is_ok(c):
        print(c)
        exit()

Submission status: Accepted

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


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

divisors = list(make_divisors(sum(A)))
divisors.sort(reverse=True)

for divisor in divisors:
    M = [a % divisor for a in A]
    M.sort(reverse=True)
    # divisorで割った余が大きい方に貪欲に+1していく
    if sum(M[sum(M) // divisor:]) <= K:
        print(divisor)
        exit()

Submission status: Accepted

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

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

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

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

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

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

for a in reversed(A):
    if check(a):
        break
print(a)

Submission status: Accepted

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

    divisors.sort()
    return divisors


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

x=sum(a)

lst=make_divisors(x)

lst.reverse()

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

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

Submission status: Accepted

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

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

解法としては、Aの総和の約数を列挙して、大きい順に実現可能かどうかを試していく。
実現可能かどうかを試すには、各Aを総和の約数dで割ったときの余りをもとめて、小さい順にソートする。
そのうえで、左からL番目までを「数を与える側」、L+1番目以降を「数をもらう側」として余りが0になるように調整できないかを確かめる。
これは累積和を活用することですくない計算量で実行可能である。
最後に、移動した数がK以下かどうかを確認する。
"""
from itertools import accumulate
N,K = map(int,input().split())
A = list(map(int,input().split()))
sumA = sum(A)
 
yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)
for d in yakusu:
    #約数の大きい順に、実現可能かどうかを試していく。
    rest = [a%d for a in A]
    rest.sort()
    
    rest = [a%d for a in A]
    rest.sort()
    Rrest = [d-r for r in rest]
    Rrest = Rrest[::-1]
    rest = [0]+list(accumulate(rest))
    Rrest = [0]+list(accumulate(Rrest))
    for i in range(N+1):
        if rest[i] == Rrest[N-i]:
            if rest[i] <= K:
                print(d)
                exit()
            break

Submission status: Accepted

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

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

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

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

"""

from itertools import accumulate

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

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

Submission status: Accepted

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

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

ans=0
for cdd in candidates:
  f=sorted([x%cdd for x in a])
  # calc need
  ans=max(ans,cdd) if sum(f[:-sum(f)//cdd])<=k else ans   
    
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

# 約数の列挙
#############################################################
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
#############################################################

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

# 操作後も総和は変わらない
# 操作後にdivが公約数なら、divは総和の約数でもある
sum_A = sum(A)
div_list = make_divisors(sum_A)
ans = 1

for div in div_list:
    # divで割った余りのリストをソート
    # どこかを境に、左側は-1をして右側は+1をすると仮定する
    tmp = [a % div for a in A]
    tmp.sort()

    # 累積和
    cumsum1 = [0]
    cumsum2 = [0]
    for i in tmp:
        cumsum1.append(cumsum1[-1] + i)
        if i != 0:
            cumsum2.append(cumsum2[-1] + (div - i))
        else:
            cumsum2.append(cumsum2[-1])

    for i in range(1, N):
        cnt_minus = cumsum1[i]
        cnt_plus = cumsum2[N] - cumsum2[i]
        # 条件を満たす時、必ずどこかで等しくなる
        # （証明が理解できていないが、実験すると確かにそうなりそう）
        if cnt_minus == cnt_plus and cnt_minus <= K:
            ans = div

print(ans)

Submission status: Accepted

Solution code:
# 約数の列挙
#############################################################


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
#############################################################


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

sum_A = sum(A)
div_list = make_divisors(sum_A)
ans = 1
# print(div_list)

for div in div_list:
    tmp = []
    for a in A:
        tmp.append(a % div)
    tmp.sort()
    cumsum1 = [0]
    cumsum2 = [0]
    for i in tmp:
        cumsum1.append(cumsum1[-1] + i)
        if i != 0:
            cumsum2.append(cumsum2[-1] + (div - i))
        else:
            cumsum2.append(cumsum2[-1])
    for i in range(1, N):
        if cumsum1[i] <= K and cumsum2[N] - cumsum2[i] <= K:
            ans = div

print(ans)

Submission status: Accepted

Solution code:
# 約数の列挙
#############################################################
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
#############################################################


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

sum_A = sum(A)
div_list = make_divisors(sum_A)
ans = 1
# print(div_list)

for div in div_list:
    tmp = []
    for a in A:
        tmp.append(a % div)
    tmp.sort()
    cumsum1 = [0]
    cumsum2 = [0]
    for i in tmp:
        cumsum1.append(cumsum1[-1] + i)
        if i != 0:
            cumsum2.append(cumsum2[-1] + (div - i))
        else:
            cumsum2.append(cumsum2[-1])
    for i in range(1, N):
        if cumsum1[i] <= K and cumsum2[N] - cumsum2[i] <= K:
            ans = div

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import floor, sqrt
N, K = map(int,input().split())
A = list(map(int,input().split()))
sm = sum(A)
divs = set()
for i in range(1, floor(sqrt(sm))+1):
    if sm % i == 0:
        divs.add(i)
        divs.add(sm // i)
ans = 1
for d in divs:
    ls = sorted(map(lambda x: x%d, A))
    acc = [0]+list(accumulate(ls, lambda x,y:x+y))
    for i in range(1, N):
        minus = acc[i]-acc[0]
        plus = d*(N-i) - (acc[-1]-acc[i])
        if plus == minus and plus <= K:
            ans = max(ans, d)
print(ans)

Submission status: Accepted

Solution code:
import sys

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


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

    lower.extend(reversed(upper))
    return lower


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

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

    for d in reversed(div):
        vec = [a % d for a in A]
        vec.sort()

        M = len(vec)
        csum_sub = [0] * (M + 1)
        csum_add = [0] * (M + 1)
        for i in range(M):
            csum_sub[i + 1] = csum_sub[i] + vec[i]
            csum_add[i + 1] = csum_add[i] + d - vec[i]

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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

    lower.extend(reversed(upper))
    return lower


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

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

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

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
import math

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

sumA = sum(A)
factors = []

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

div =  make_divisors(sumA)
ans = 1
for div_ in div:
    A_ = sorted([a % div_ for a in A])[::-1]
    if sum(A_[sum(A_) // div_:]) <= K:
        ans = div_
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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


def resolve():
    n, k = map(int, input().split())
    A = sorted(list(map(int, input().split())))

    div = make_divisors(sum(A))
    res = 1
    for x in div:
        B = sorted([a % x for a in A])
        M, P = [0], [0]
        for i in range(n):
            M.append(M[-1] + B[i])
            P.append(P[-1] + x - B[i])
        M.pop(0)
        P.pop(0)
        for i in range(n - 1):
            m = M[i]
            p = P[n - 1] - P[i]
            if m <= k and p <= k and m % x == p % x:
                res = max(res, x)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def divisor(n):
    d = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            d.append(i)
            if i != n//i:
                d.append(n//i)
    #d.sort()
    return d

n,k = ma()
A = lma()
s = sum(A)
ds = divisor(s);ds.sort(reverse=True)
for d in ds:
    ls = []
    cost=0
    for a in A:
        p,r = divmod(a,d)
        ls.append(r)
    ls.sort(reverse=True)
    s0 = sum(ls)
    cost=s0
    #print("d",d,"s0",s0,"ls",ls)
    for r in ls:
        if s0==0:
            break
        s0 -=d
        cost-=r
    if cost<=k:
        print(d)
        exit()

Submission status: Accepted

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

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

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

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


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def calc_min_ops(r, d):
    i, j = 0, len(r)
    while i < j and r[i] == 0:
        i += 1
    i -= 1
    a, b = 0, 0
    while j-i != 1:
        if a <= b:
            i += 1
            a += r[i]
        else:
            j -= 1
            b += d - r[j]
    return a


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

c = sum(A)
divisors = make_divisor_list(c)
divisors.sort(reverse=True)
r = [None] * N

for d in divisors:
    for i in range(N):
        r[i] = A[i] % d
    r.sort()
    if calc_min_ops(r, d) <= K:
        print(d)
        break

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

    def enum_divisors(n):
        # 約数列挙
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        if d == 1:
            print(d)
            return
        diff_n = [a % d for a in A if a % d != 0]
        diff_n.sort()
        diff_p = [d - dn for dn in diff_n]
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        M = len(S_n) - 1
        if any(max(S_n[i], S_p[M] - S_p[i]) <= K for i in range(1, M)):
            print(d)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

    def enum_divisors(n):
        # 約数列挙
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        if d == 1:
            print(d)
            return
        diff_n = [a % d for a in A if a % d != 0]
        diff_n.sort()
        diff_p = [d - dn for dn in diff_n]
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        M = len(S_n) - 1
        if min(S_n[i] for i in range(1, M)
               if (S_n[i] - (S_p[M] - S_p[i])) == 0) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

    def enum_divisors(n):
        # 約数列挙
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        if d == 1:
            print(d)
            return
        diff_n = []
        for a in A:
            if a % d != 0:
                diff_n.append(a % d)
        diff_n.sort()
        diff_p = [d - dn for dn in diff_n]
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        M = len(S_n) - 1
        if min(S_n[i] for i in range(1, M)
               if (S_n[i] - (S_p[M] - S_p[i])) == 0) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()