Gcd nə (Həll təhlili)

Həll

Müşahidə 1. g=\gcd(a_1,\dots,a_n) olsun. $g$ hər a_i-ni bölür, bir əməliyyatdan sonra a_j \leftarrow a_j+g, bütün ədədlər hələ də $g$-yə bölünür. Buna görə yeni gcd g' aşağıdakı şərti ödəyir: g' \ge g (gcd heç vaxt azalmaz).

Müşahidə 2. k\le 3, buna görə də hər əməliyyat üçün indekslərin bütün seçimlərini sınaqdan keçirə bilərik. Sıraların sayı n^k \le 100^3 = 10^6.

DFS/geri qaytarma ilə edin:

dərinlik $d$ (artıq $d$ əməliyyatını yerinə yetirmişik) vəziyyətində, cari $\max (a)$ ilə cavabı yeniləyin.

Əgər d=k-dirsə, dayanın. Cari gcd $g$-ni hesablayın.

Hər indeks $i$-ni sınayın: $g$-ni a_i-yə əlavə edin, d+1-ə geri çağırın, sonra geri qaytarın.

Çətinlik \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()