GCD Що (Розбір)

Розв'язок

Спостереження 1. Нехай g=\gcd(a_1,\dots,a_n). Оскільки $g$ ділить кожне a_i, після однієї операції a_j \leftarrow a_j+g, всі числа все ще діляться на $g$. Отже, новий gcd g' задовольняє g' \ge g (gcd ніколи не зменшується).

Спостереження 2. k\le 3, тому ми можемо перебрати всі вибори індексів для кожної операції. Кількість послідовностей n^k \le 100^3 = 10^6.

Зробіть DFS/зворотний зв'язок:

на глибині стану $d$ (вже виконано $d$ операцій), оновіть відповідь з поточним $\max (a)$.

Якщо d=k, зупиніться. Обчисліть поточний gcd $g$.

Спробуйте кожен індекс $i$: додайте $g$ до a_i, рекурсивно переходьте до d+1, потім скасуйте.

Складність \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()