C problem but threatening light blue A guy who can solve it if he knows the story just by twisting it a little
This is a straightforward method Take gcd in order from the left and record Similarly from the right Make friends with the left gcd and right gcd recorded for each point later
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[:]
#From the left, make the greatest common divisor, right
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)
First implementation I couldn't write it very neatly ... In this case, you can find and defeat the entire gcd with logN for each one 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