[PYTHON] Atcoder ABC125 C - GCD auf Tafel

C Problem aber drohend hellblau Ein Typ, der es lösen kann, wenn er die Geschichte kennt, indem er sie ein wenig dreht

Kumulative GCD

Dies ist eine einfache Methode Nehmen Sie gcd in der Reihenfolge von links und nehmen Sie auf Ähnlich von rechts Freunde dich mit dem linken und dem rechten GCD an, die später für jeden Punkt aufgezeichnet wurden

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[:]
#Machen Sie von links die maximale Anzahl von Versprechungen, rechts
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)

Segmentbaum

Erste Implementierung Ich konnte es nicht sehr ordentlich schreiben ... In diesem Fall kann logN verwendet werden, um die gesamte gcd für jeden Punkt zu finden und zu besiegen.

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)