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

Solution code:
#pragma region Macros
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vecll>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define endl "\n"
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),(x)))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),(x)))
using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
string stin() {string s;cin>>s;return s;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
vec iota(int n){vec a(n);iota(all(a),0);return a;}
void print(){putchar(' ');}
void print(bool a){cout<<a;}
void print(int a){cout<<a;}
void print(long long a){cout<<a;}
void print(char a){cout<<a;}
void print(string &a){cout<<a;}
void print(double a){cout<<a;}
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ cout<<'(';print(p.first); cout<<","; print(p.second);cout<<')'; }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ cout<<" "; print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
#define _GLIBCXX_DEBU
#ifdef _MY_DEBUG
    #undef endl
    #define debug(x) cout<<#x<<": "<<x<<endl
    void err(){}
    template<class T> void err(const T& t){ print(t);  cout<<" ";}
    template<class Head, class... Tail> void err(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); }
#else
    #define debug(x)
    template<class... T> void err(const T&...){}
#endif
#pragma endregion




const ll MOD=1e9+7;
const int N=1100000;
 
template <ll Modulus> class modint {
  using u64 = ll;
 
public:
  u64 a;
 
  constexpr modint(const u64 x = 0) noexcept : a(((x % Modulus) + Modulus)%Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};
 
#define mint modint<MOD>
mint inv[N],comb[N],prd[N],invprd[N];
void calc_inv(){
    inv[1]=1;
    rep2(i,2,N-1){
        inv[i]=inv[MOD%i]*(-MOD/i);
    }
    return;
}
void calc_product(){
    prd[0]=prd[1]=1;
    invprd[0]=invprd[1]=1;
    rep2(i,2,N-1){
        prd[i]=prd[i-1]*i;
        invprd[i]=inv[i]*invprd[i-1];
    }
    return ;
}
mint cmb(int a,int b){
    if(a<b)return 0;
    if(a<0||b<0)return 0;
    return {prd[a]*invprd[b]*invprd[a-b]};
}
mint modpow(mint x,ll n){
    if(n==0) return 1;
    mint res=modpow(x*x,n/2);
    if(n&1) res=res*x;
    return res;
}
void calc(){calc_inv();calc_product();}
using vmint = vector<mint> ;
ostream& operator<<(ostream& os, mint a){
    os << a.a ;
    return os;
}


signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15);
    int n=in();
    int k=in();
    ll sum=0;
    vecll a;
    rep(i,n)a.pb(in());
    sum=accumulate(all(a),0);
    vec d;
    for(int i=1;i*i<=sum;i++){
        if(sum%i==0){
            d.pb(i);
            if(sum/i!=i)d.pb(sum/i);
        }
    }
    sort(all(d),greater<int>());
    for(auto e:d){
        ll res=0;
        vec x;
        rep(i,n){
            int t=(a[i]%e);
            x.pb((min(t,e-t)));
        }
        sort(all(x));
        rep(i,n-1)res+=x[i];
        if(res<=k){
            cout<<e<<endl;return 0;
        }
    }

}

Submission status: Runtime Error

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#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()
[0]%l:
            B.popleft()
        if not B[-1]%l:
            B.pop()

    if not B:
        print(l)
        exit()

Submission status: Runtime Error

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 m:
        ans = max(ans, d)

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define show(x) for(auto i: x){cout << i << " ";}
#define showm(m) for(auto i: m){cout << m.x << " ";}
typedef long long ll;

template<class X> void divisor(X input, vector<X>& Dnumber){
    for (X i = 2; i*i <= input; i++)
    {
        if (input % i == 0){
            Dnumber.push_back(i);
            if (i * i  != input) Dnumber.push_back(input / i);
        }
    }
    Dnumber.push_back(input);
    Dnumber.push_back(1);
    sort(Dnumber.begin(), Dnumber.end(), greater<X>());
}



int process(int num, vector<int>& a){
    vector<int> sorted_div;

    rep(i, a.size()) sorted_div.push_back(a[i]%num);
    sort(sorted_div.begin(), sorted_div.end());

    ll sum_to_next = 0;
    rep(i, a.size()) sum_to_next += num - sorted_div[i];
    int ans = 0;
    rep(i, (sum_to_next / num)) ans += sorted_div[i];
    return ans; 
}

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a;
    rep(i, n) {int tmp; cin >> tmp; a.push_back(tmp);}

    int sum = 0;
    rep(i, n) sum += a[i];

    vector<int> div;
    divisor(sum, div);

    //show(div);    

    int ans = 0;
    rep(i, div.size()){
        int num = div[i];
        if(process(num, a) <= k){
            ans = num;
            break;
        }
    }

    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    # memo
    def divisions(self, n):
        if n in self.ds_memo:
            return self.ds_memo[n]

        for c in self.T:
            if n % c == 0:
                rs = set([c])
                for cc in self.divisions(n // c):
                    rs.add(cc)
                    rs.add(cc * c)
                self.ds_memo[n] = rs
                return rs

        rs = set([n])
        self.ds_memo[n] = rs
        return rs

def main():
    n,k = LI()
    a = LI()
    s = sum(a)
    pr = Prime(s*s)
    dv = pr.divisions(s)

    def f(i):
        pm = []
        for c in a:
            t = c % i
            if t == 0:
                continue
            pm.append((i-t, t))
        pm.sort()
        p = pi = m = 0
        mi = len(pm) - 1
        while pi <= mi:
            if p < m:
                p += pm[pi][0]
                pi += 1
            else:
                m += pm[mi][1]
                mi -= 1
        return min(p,m) <= k

    r = 1
    for c in dv:
        if f(c):
            if r < c:
                r = c

    return r


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    # memo
    def divisions(self, n):
        if n in self.ds_memo:
            return self.ds_memo[n]

        for c in self.T:
            if n % c == 0:
                rs = set([c])
                for cc in self.divisions(n // c):
                    rs.add(cc)
                    rs.add(cc * c)
                self.ds_memo[n] = rs
                return rs

        rs = set([n])
        self.ds_memo[n] = rs
        return rs

def main():
    n,k = LI()
    a = LI()
    pr = Prime(10**13)
    dv = pr.divisions(sum(a))

    def f(i):
        pm = []
        for c in a:
            t = c % i
            if t == 0:
                continue
            pm.append((i-t, t))
        pm.sort()
        p = pi = m = 0
        mi = n - 1
        while pi <= mi:
            if p < m:
                p += pm[pi][0]
                pi += 1
            else:
                m += pm[mi][1]
                mi -= 1
        return max(p,m) <= k

    r = 1
    for c in dv:
        if f(c):
            if r < c:
                r = c

    return r


print(main())

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,K=LI()
AS=LI()
SUMM= sum(AS)

DIVS=set()
for i in range(1,40000):
    if SUMM % i == 0:
        DIVS.add(i)
        DIVS.add(SUMM//i)
# DIVS.sort(reversed=True)
# print(DIVS)

DIFF=[0]*N
ACC=[0]*N

# res = 0

for x in devisor:
  b = [a[i]%x for i in range(n)]
  b.sort()
  sumb = list(accumulate(b))
  for y in range(n-1):
    bf = sumb[y]
    bl = sumb[n-1]-sumb[y]
    if bf%x == (x-(bl%x))%x:
      if k>=max(bf,(n-1-y)*x-bl):
        print(x)
        exit()
      else:
        continue

for div in sorted(DIVS, reverse=True):
    for i in range(N):
        DIFF[i] = AS[i]%div
    DIFF.sort()
    ACC[0] = DIFF[0]
    for i in range(1,N): ACC[i] = ACC[i-1] + DIFF[i]
    # print(ACC)
    for i in range(N-1):
        left = ACC[i]
        right = (N-1-i)*div-(ACC[N-1]-ACC[i])
        if left%div == right%div:
            if max(left, right) <= K:
                # print(max(left, right))
                print(div)
                exit()


# print(DIFF)
# print(res)

Submission status: Runtime Error

Solution code:
import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int64)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    subcum = np.cumsum(mods)
    idx = subcum[n-1] // div
    count = subcum[-1-idx]
    if count <= k:
        print(count)
        exit()

Submission status: Runtime Error

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

def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(40000)

lis = []
for p in plis:
    if S%p == 0:
        lis.append([p,1])
        S = S//p
        while S%p == 0:
            lis[-1][1] += 1
            S = S//p
    if S == 1:
        break
if S != 1:
    lis.append([[S,1]])

yakulis =[1]
for l in lis:
    for j in range(len(yakulis)):
        for k in range(l[1]):
            n = yakulis[j]
            yakulis.append(l[0]**(k+1)*n)
yakulis.sort(reverse=True)

s = True
for r in yakulis:
    B = [i%r for i in A]
    B.sort()
    le = -1
    ri = N
    while ri-le > 1:
        mid = (le+ri)//2
        pl = sum(B[:mid+1])
        mi = r*(N-1-mid) - sum(B[mid+1:])
        if pl > mi:
            ri = mid
        else:
            le = mid
    k = sum(B[:le+1])
    if k <= K:
        s = False
        print(r)
        break
if s:
    print(1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

s=sum(A)
n=int(s**0.5)

#約数のリスト
cd=[]

for i in range(1,n+2):
	if s%i==0:
		cd.append(i)
		cd.append(s/i)

cd.sort(reverse=True)

def check(t):
	A_temp=[]
	for x in A:
		A_temp.append(x%t)

	A_temp.sort()

	#Aの配列をmod tした配列A_tempの累積和
	A_temp_sum=[]

	for i,x in enumerate(A_temp):
		if i==0: A_temp_sum.append(x)
		else: A_temp_sum.append(A_temp_sum[-1]+x)

	#配列の前半は、数字をマイナスしていく
	p1=bisect_left(A_temp_sum,K)
	if A_temp_sum[p1]<=K:
		k1=A_temp_sum[p1]
	else:
		p1-=1
		k1=A_temp_sum[p1]

	#配列の後半で、数字をどれだけプラスする必要があるか
	k2=t*(N-p1-1)-(A_temp_sum[-1]-A_temp_sum[p1])

	#プラスする量が、マイナスする量より少なければ成立
	if k2<=k1:
		return True
	else:
		return False

for x in cd:
	if check(x):
		print x
		quit()

Submission status: Runtime Error

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

res=[]
for d in range(1,int(s**0.5)+1):
	if s%d==0:
		res.append(d)
		res.append(s//d)
ans=[]
for d in res:
	r1=[t%d for t in a]
	r1.sort()
	r2=[d-t for t in r1]
	r2=r2[::-1]
	x=[r1[0]]
	_=[x.append(x[-1]+r1[i]) for i in range(1,n)]
	y=[r2[0]]
	_=[y.append(y[-1]+r2[i]) for i in range(1,n)]
	#print(r1,r2,d,x,y)
	for i in range(n-1):
		#print(x[i],y[-i-2])
		if x[i]==y[-i-2] and x[i]<k:
			ans.append(d)
print(max(ans))

Submission status: Runtime Error

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

# n, k = 4, 5
# arr = list(map(int, "10 1 2 22".split()))

add = sum(arr)

def check(factor):
	mod_factor = [x%factor for x in arr]
	left, right = 0, n-1
	reqd, rem = 0, 0
	mod_factor.sort()
	counter = 0
	while left <= right:
		reqd = factor - mod_factor[right]
		while mod_factor[right]% factor != 0:
			if reqd < mod_factor[left]:
				mod_factor[left] -= reqd
				mod_factor[right] = 0
				counter += reqd
			else:
				mod_factor[right] -= mod_factor[left]
				reqd -= mod_factor[left]
				counter += mod_factor[left]
				left += 1
		right -= 1
	return countera <= k

ans = i = 1
while i*i <= add:
	if add % i == 0:
		if check(i):
			ans = max(ans, i)
		if check(add//i):
			ans = max(ans, add//i)
	i += 1
print(ans)

Submission status: Runtime Error

Solution code:

inputs = [int(x) for x in input().split()]
n, k = inputs[0], inputs[1]
ls = [int(x) for x in input().split()]
s = sum(ls)

# https://qiita.com/LorseKudos/items/9eb560494862c8b4eb56
divisors = []
for i in range(1, int(s ** 0.5) + 1):
  if s % i == 0:
    divisors.append(i)
    if i != s // i:
      divisors.append(s // i)

divisors.sort(reverse=True)
ans = 1
for d in divisors:
  mods = sorted([l % d for l in ls if l % d != 0])
  opcnt = 0
  is_success = False
  # print("{}: {}".format(d, ", ".join([str(m) for m in mods])))
  while True:
    if mods[0] + mods[-1] < d:
      mods[-1] += mods[0]
      opcnt += mods[0]
      mods.pop(0)
    elif mods[0] + mods[-1] == d:
      opcnt += mods[0]
      mods.pop(0)
      mods.pop(-1)
    else:
      opcnt += (d - mods[-1])
      mods[0] -= (d - mods[-1])
      mods.pop(-1)
    # print("{}: {}".format(d, ", ".join([str(m) for m in mods])))

    if opcnt > k or len(mods) == 1:
      # print("opcnt: {}".format(opcnt))
      is_success = False
      break
    if len(mods) == 0:
      is_success = True
      ans = d
      # print("ans: {}, opcnt: {}".format(ans, opcnt))
      break

  if is_success:
    break

print(ans)

Submission status: Runtime Error

Solution code:
# E - Max GCD
import sympy
import sys

def check(targetSet):

    # Aiを割り切れる整数を大きいものから順に、指定回数の値操作で実現可能か判定する
    for target in sorted(targetSet, reverse=True):
        ret = True
        incDecList = [[0, 0, 0]]
        for ai in a:
            dec = -(ai % target)
            inc = target + dec
            if min(inc, abs(dec)) > k:
                ret = False
                break
            updateList = list()
            for incDec in incDecList:
                if inc <= k:
                    updateList.append([incDec[0] + inc, incDec[1] + inc, incDec[2]])
                if abs(dec) <= k:
                    updateList.append([incDec[0] + dec, incDec[1], incDec[2] + dec])
            incDecList = updateList
        if ret:
            for incDec in incDecList:
                if incDec[0] == 0 and incDec[1] <= k:
                    print(target)
                    return

                
                
input1 = list(map(int, input().split()))
n = input1[0]
k = input1[1]
a = list(map(int, input().split()))

# Aiの合計値を素因数分解
a.sort(reverse=True)
sumFact = sympy.factorint(sum(a))
targetSet = {1}
for fact, power in sumFact.items():
    for i in range(power):
        for ele in list(targetSet):
            targetSet.add(ele * fact)
check(targetSet)