Atcoder ABC125 C - GCD on Blackboard 別解集

C問題なのに脅威の水色
ちょっと捻ってるだけでネタが分かれば解けるヤツ

累積GCD

これが正攻法
左から順番にgcdを取っていって記録していく
右からも同様に
あとで各一点に対して記録した左側gcdと右側gcdで仲良しさせる

ruiseki.py

def euclid(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        a,b=b,a%b
        return euclid(a,b)

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

org_A=A[:]
#左から最大公約数作る右もね
A=A[::-1]
l=[A.pop(-1)]
while A:
    l.append(euclid(l[-1],A.pop(-1)))

A=org_A
r=[A.pop(-1)]
while A:
    r.append(euclid(r[-1],A.pop(-1)))
r=r[::-1]

ans=0
for i in range(N):
    temp=euclid(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    ans=max(ans,temp)

print(ans)

セグメント木

初実装
あんまり綺麗に書けなかった、、、
これなら各一点に対してlogNで全体のgcdを求め倒すことができる

seg.py

import fractions

N=int(input())

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

M=[2]
while M[-1]<N:
    M.append(M[-1]*2)

A=A+[0]*(M[-1]-len(A))
A=A[::-1]

for i in range(len(A)-1):
    A.append(fractions.gcd(A[2*i],A[2*i+1]))

A=A[::-1]

ans=0
for index in range(len(A)-M[-1],len(A)-M[-1]+N):
    temp=A[index+1] if index%2==1 else A[index-1]
    index=((index-1) if index%2==1 else (index-2))//2

    while index!=0:
        if index%2==1:
            temp=fractions.gcd(temp,A[index+1])
            index=(index-1)//2
        else:
            temp=fractions.gcd(A[index-1],temp)
            index=(index-2)//2
    ans=max(temp,ans)
print(ans)