ABC125

atcoder.jp
ABDの3完。Dが簡単だったみたいですぐできたんですが、CでTLEから逃れられず。。

Cは、数を書き直せるとは数を消すと同じ、というところまではわかって、あとは残りの数のgcd(最大公約数)をどう早く解くかなんですが、これも累積和と同じような感じで予め求めておけるんですね〜
消す数をA[i]とした時、その左側のgcdをL[i]、右側のgcdをR[i+1]として、

N = int(input())
A = list(map(int, input().split()))


def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a % b)


L = [0] * (N + 1)
R = [0] * (N + 1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

ans = 1
for i in range(N):
    ans = max(ans, gcd(L[i], R[i+1]))

print(ans)

LとRで分けて最後にgcd(L, R)と計算できること、L, Rの要素が漸化式で高速に求められることがミソですか〜
全完狙ってたけどおあずけ...