Atcoder ABC125 C --GCD sur tableau noir

Problème C mais bleu clair menaçant Un mec qui peut le résoudre s'il connaît l'histoire juste en la tordant un peu

GCD cumulatif

C'est une méthode simple Prenez le gcd dans l'ordre à partir de la gauche et enregistrez De même de la droite Faites-vous des amis avec le pgcd gauche et le pgcd droit enregistrés pour chaque point plus tard

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[:]
#De la gauche, faites le nombre maximum de promesses, à droite
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)

Arborescence des segments

Première implémentation Je ne pouvais pas l'écrire très proprement ... Dans ce cas, logN peut être utilisé pour trouver et vaincre le pgcd entier pour chaque point.

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 sur tableau noir
AtCoder ABC176
Résolu AtCoder ABC 114 C-755 avec Python3
AtCoder ABC177
Atcoder ABC099 C - Solution séparée de Strange Bank
AtCoder ABC 174 Python
AtCoder ABC 175 Python
AtCoder ABC 098 C - Idées d'attention menant à la réponse
ABC125_C --GCD sur tableau noir [Notes résolues en Python]
Manipulation de chaîne C AtCoder ABC110 à résoudre dans Ruby
Défiez AtCoder (ABC) 164 avec Python! Un problème ~ C
Retour sur ABC155
Atcoder ABC115 Exercice de questions passées
Résoudre Atcoder ABC176 (A, B, C, E) en Python
ABC147 C --HonestOrUnkind2 [Python]
[Explication AtCoder] Contrôle ABC158 Problèmes A, B, C avec Python!
Résolution avec Ruby et Python AtCoder ABC011 C Méthode de planification dynamique
AtCoder ABC151 Problème D Comparaison de la vitesse en C ++ / Python / PyPy
[Explication AtCoder] Contrôle ABC164 Problèmes A, B, C avec Python!
[Explication AtCoder] Contrôle ABC168 Problèmes A, B, C avec Python!
AtCoder ABC 177 Python (A ~ E)
Résolvez AtCoder ABC166 avec python
AtCoder ABC 178 Python (A ~ E)
Atcoder ABC164 A-C en Python
ABC129 Commentaire A, B, C
Mémorandum ABC [ABC163 C --managementr] (Python)
AtCoder Beginner Contest # 002 Problème C
AtCoder ABC 176 Python (A ~ E)
Atcoder ABC167 A-D en Python
AtCoder Regular Contest # 002 Problème C
Atcoder ABC165 A-D en Python
Atcoder ABC166 A-E en Python
AtCoder ABC 182 Python (A ~ D)
J'ai participé à AtCoder (ABC158)
Atcoder ABC169 A-E en Python
AtCoder ABC177 A-D avec python
[Commentaire d'AtCoder] Gagnez le problème ABC165 C "Many Requirements" avec Python!
Résolution avec Ruby, Perl, Java et Python AtCoder ABC 065 C-th power