[AtCoder abc136] E-Max GCD[python]

 

E - Max GCD

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500 points

Problem Statement

We have a sequence of NN integers: A_1, A_2, \cdots, A_NA1​,A2​,⋯,AN​.

You can perform the following operation between 00 and KK times (inclusive):

• Choose two integers ii and jj such that i \neq ji=j, each between 11 and NN (inclusive). Add 11 to A_iAi​ and -1−1 to A_jAj​, possibly producing a negative element.

Compute the maximum possible positive integer that divides every element of AA after the operations. Here a positive integer xx divides an integer yy if and only if there exists an integer zz such that y = xzy=xz.

Constraints

$2≤N≤500$

$1≤A_i​≤10^6$

$0≤K≤10^9$

All values in input are integers.

======================================================================

주어진 수열 A의 숫자들을 대상으로 Operation(한 수에는 +1, 다른 한 수에는 -1)이 아무리 이루어지더라도, 

수열 A의 총 합$S$는 변하지 않는다는 성질을 이용합니다.

 

합$S$에 대해, 문제에서 구하고자 하는 GCD는 $S$의 약수중에 있음을 알 수 있습니다.

(Operation 이후 수열 A의 모든 수가 어떤 수 $X$에 의해 나누어 떨어진다면, 이 수는 $S$의 약수여야 합니다.)

$if$  $Sum($$A_i$  $mod$ $X) = 0,$ $S$ $mod$ $X= 0$

 

모든 수가 X에 의해 나누어 떨어지도록 값들을 변경하는 과정에서, 결과적으로 어떤 수는 $A_i$ $mod$ $X$값을 빼주어야 할 것이고, 어떤 수는 $N - $$A_i$ $mod$ $X$값을 더해주어야 할 것입니다.

모든 $A_i$을 $mod$ $X$한 결과수열을 PS, X - $(A_i$ $mod$ $X)$한 결과수열을 SS라고 할 때,

$X-(A_i$ $mod$ $X)-A_i$ $mod$ $X = X$이므로 어느 한쪽의 총 합에서 특정 요소값(V)을 빼고

반대쪽에는 X-V를 더해준다면, 둘의 차이는 D씩 감소하며,  Sum(SS),Sum(PS) 모두 X의 배수이므로 둘의 값은 특정 시점에서 같아집니다.

 

이 때, 모든 값이 X에 의해 나누어 떨어질 수 있도록 하는 Operation의 최소 수행 횟수 M은 Sum(SS),Sum(PS)값이 만나는 지점의 값과 같으며, ( 배열 내의 수들에 대해 수열 SS 내에 있는 수들은 총 M만큼 값을 빼주고, 수열 PS 내에 있는 수들은 총 M만큼 값을 더해줍니다.) M값을 구하기 위해선, Sum(SS),Sum(PS)가 가능한 작은 수에서 만나도록 해야합니다.

 

Sum(SS)에서 요소를 빼주고, Sum(PS) = 0으로 시작해 요소를 채워나간다고 할 때,

Sum(SS)에서 가능한 한 큰 수를 빼주면(PS에 가능한 한 작은 수를 더해주면) M값을 최소화할 수 있습니다.

 

그렇게 두 값이 같아졌을 때, M값과 K값을 비교하여, M값이 K보다 작거나 같은 경우 주어진 조건을 만족함을 알 수 있습니다.

 

n,k = map(int,input().split())
nums = list(map(int,input().split()))
total = sum(nums)
for i in range(total,0,-1):
    if total % i: continue

    prefixSum = 0
    suffix = []
    for v in nums:
        if v % i:
            prefixSum += i - (v % i)  #숫자 i로 나눈 나머지
            suffix.append(v % i)

    if not prefixSum:
        print(i)
        exit(0)

    suffix.sort()    #큰거부터 차례대로 빼기
    suffixSum = 0
    for v in suffix:
        prefixSum -= (i - v)    #v%i 뺴줌
        suffixSum += v

        #print(abs(prefixSum - suffixSum))
        if prefixSum == suffixSum and prefixSum <= k:
            print(i)
            exit(0)