C Problem aber drohend hellblau Ein Typ, der es lösen kann, wenn er die Geschichte kennt, indem er sie ein wenig dreht
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)
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