ABC 125 C - GCD on Blackboard

問題概要

C - GCD on Blackboard
N個の数列Ai, Ai+1, Ai+2...のうち、任意の1つのみの数値を0～10^9の任意の値に
置きかえた際に数列全体の最大公約数として考えられる最大値を求めよ

解法(解説AC)

けんちょんさんの記事を参考にした。
AtCoder ABC 125 C - GCD on Blackboard (300 点) - けんちょんの競プロ精進記録

Aiを置き換える際には、Aiを消したと等価になる。
また、3つ以上の数列の最大公約数の求め方がgcd(Ai, gcd(Ai+1, Ai+2))とすることができることから再帰的な求め方が可能である。
上記を利用した累積gcd(1番目からNまでのgcdとN番目からの1番目までのgcd)の結果を用意し削除するiを決めた際の最大公約数がmaxとなる値を求める。

具体例

Inputを[10, 2, 15, 20]とする。
1番目の要素からN番目までの要素のgcdを求めた場合、
①gcd(10, 2) = 2
②gcd(①の結果=2, 15) = 1
③gcd(②の結果=1, 20) = 1
となり、[2,1,1]の要素となる。
上記に0と10を付加し、[0, 10, 2, 1, 1]の要素leftとする。

N番目の要素から1番目までの要素のgcdを求めた場合、
①gcd(20, 15) = 5
②gcd(②の結果=5, 2) = 1
③gcd(②の結果=1, 10) = 1
となり、[1,1,5]の要素となる。
上記に0と20を付加し、[1, 1, 5, 20, 0]の要素rightとする。

削除するiを1番目の要素としたとき、
left[0] = 0となる。
N番目から2番目の要素まで計算した結果は
right[i + 1] = 1となり、gcd(left[0], right[1]) = 1となる。

削除するiを2番目の要素としたとき、1番目の要素の計算結果は
left[1] = 10となる。
N番目から3番目の要素まで計算した結果は
right[i + 1] = 5となり、gcd(left[1], right[2]) = 5となる。

以降、計算を繰り返すと全体の最大公約数の最大値は5となる。

提出コード

# coding: UTF-8
n = int(input())
a = list(map(int, input().split()))
 
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = fractions.gcd(left[i], a[i])
for i in reversed(range(n)):
    right[i] = fractions.gcd(right[i + 1], a[i])
mx = 0
for i in range(n):
    l = left[i]
    r = right[i + 1]
    mx = max(mx, fractions.gcd(l, r))
print(mx)