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の要素が漸化式で高速に求められることがミソですか〜
全完狙ってたけどおあずけ...