ABC125 : C - GCD on Blackboard(Python) - わからないけどわかりたい

ABC125: C - GCD on Blackboardをpythonで解きました

問題文

atcoder.jp
リストのうち１個を書き換えることにより全体の最大公約数を最大化しようという問題です

Atcoder Plobremsによると難易度は1217でABCのC問題にしては水色と高難易度
私がずっと放置してきた問題の１つです

解法

gcdとはgreatest common divisorの略で最大公約数を表します

最大公約数には結合法則が成り立ちます

例えば $li = [12,18,9$ ]というようなリストが存在していた場合に、
$gcd(gcd(12,18),9)$ を求めるのと
$gcd(12,gcd(18,9))$ を求めるのとでは
答えである $gcd(li) = 3$ には変わりがありません

どこから計算をしていっても最終的な答えは変わらないんですね

また、 $A_i$ 番目の数字を置き換える時には、他のn-1個の要素の最大公約数に変換するのが最適であることはすぐにわかります

なので $A_i$ 番目の数字を置き換える→i番目以外の要素の最大公約数を求める
という風に言い換えることができます

あとは全ての $A_i$ において
左側からi-1番目までの最大公約数を記録する $L(i)$ と
i番目から右端までの最大公約数を記録する $R(i)$
において漸化式を作ります

漸化式は以下のようになります(※ $gcd(0,n) = n$ とする)
$L(0) = 0\\ L(i + 1) = gcd(L(i), A(i))\\ R(N + 1) = 0\\ R(i) = gcd(R(i + 1), A(i))$

i番目の要素を置き換えたと仮定したときの答えを $M(i)$ とすると
$M(i) = L(i) + R(i-1)$ の中の最大値が答えです

pythonにはmath関数にgcdが存在しますが、Atcoderのpythonは3.4系でmath.gcdに対してエラーを起こします
(もう少しすればAtcoderに3.8系が実装されるのでmath.gcdが使えるようになります)

そこで代替としてfractions関数のgcdを用います
fractions.gcd(a,b)でaとbの最大公約数が求められます

pythonでの実装例

※実装例では上記の漸化式を簡易的にしてあります

from fractions import gcd
 
N = int(input())
A = list(map(int,input().split()))
 
M = [0]*N
 
#漸化式を作る
L = [0]*N
R = [0]*N
 
for i in range(1,N):
    L[i] = gcd(L[i-1],A[i-1])
    R[N-1-i] = gcd(R[N-i],A[N-i])
 
for j in range(N):
    M[j] = gcd(L[j],R[j])
 
print(max(M))