[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)

Recommended Posts

Atcoder ABC125 C - GCD auf Tafel
AtCoder ABC176
AtCoder ABC 114 C-755 mit Python3 gelöst
AtCoder ABC177
Atcoder ABC099 C - Separate Bank Separate Lösung
AtCoder ABC 174 Python
AtCoder ABC 175 Python
AtCoder ABC 098 C - Aufmerksamkeitsideen, die zur Antwort führen
ABC125_C --GCD auf Blackboard [In Python gelöste Notizen]
AtCoder ABC110 C-String-Manipulation zum Lösen in Ruby
Fordern Sie AtCoder (ABC) 164 mit Python heraus! A ~ C Problem
Rückblick auf ABC155
Atcoder ABC115 Vergangene Frage Übung
Löse den Atcoder ABC176 (A, B, C, E) in Python
ABC147 C --HonestOrUnkind2 [Python]
[AtCoder Erklärung] Kontrollieren Sie ABC158 A, B, C Probleme mit Python!
Lösen mit Ruby und Python AtCoder ABC011 C Dynamische Planungsmethode
AtCoder ABC151 Problem D Geschwindigkeitsvergleich in C ++ / Python / PyPy
[AtCoder Erklärung] Kontrollieren Sie ABC164 A, B, C Probleme mit Python!
[AtCoder Erklärung] Kontrollieren Sie ABC168 A, B, C Probleme mit Python!
AtCoder ABC 177 Python (A ~ E)
Löse AtCoder ABC166 mit Python
AtCoder ABC 178 Python (A ~ E)
Atcoder ABC164 A-C in Python
ABC129 A, B, C Kommentar
ABC-Memorandum [ABC163 C --managementr] (Python)
AtCoder Beginner Contest # 002 C Problem
AtCoder ABC 176 Python (A ~ E)
Atcoder ABC167 A-D in Python
AtCoder Regular Contest # 002 C Problem
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
AtCoder ABC 182 Python (A ~ D)
Ich habe an AtCoder (ABC158) teilgenommen.
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D mit Python
[AtCoder-Kommentar] Gewinnen Sie mit Python das ABC165 C-Problem "Many Requirements"!
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 065 C-te Potenz