GCD What (Editorial)

Solution

Observation 1. Let g=\gcd(a_1,\dots,a_n). Since $g$ divides every a_i, after one operation a_j \leftarrow a_j+g, all numbers are still divisible by $g$. Hence the new gcd g' satisfies g' \ge g (gcd never decreases).

Observation 2. k\le 3, so we can brute force all choices of indices for each operation. Number of sequences is n^k \le 100^3 = 10^6.

Do DFS/backtracking:

at state depth $d$ (already did $d$ ops), update answer with current $\max (a)$.

If d=k stop. Compute current gcd $g$.

Try every index $i$: add $g$ to a_i, recurse to d+1, then undo.

Complexity \mathcal{O}(n^k)

from math import gcd
n=0
k=0
a=[]
best=0

def gcdarray():
    g=a[0]
    for x in a[1:]:
        g=gcd(g, x)
    return g

def rec(d):
    global best
    best=max(best, max(a))
    if d==k:
        return
    g=gcdarray()
    for i in range(n):
        a[i]+=g
        rec(d+1)
        a[i]-=g

def solve():
    global n,k,a,best
    n,k=map(int, input().split())
    a=list(map(int, input().split()))
    best=max(a)
    rec(0)
    print(best)

for _ in range(int(input())):
    solve()