Atcoder ABC125 C --GCD on Blackboard

C problem but threatening light blue A guy who can solve it if he knows the story just by twisting it a little

Cumulative GCD

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)

Segment tree

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

Atcoder ABC125 C --GCD on Blackboard
AtCoder ABC176
Solved AtCoder ABC 114 C-755 with Python3
AtCoder ABC177
Atcoder ABC099 C --Strange Bank Separate Solution
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
AtCoder ABC 098 C --Attention Thinking about the answer
ABC125_C --GCD on Blackboard [Notes solved in Python]
Solving with Ruby AtCoder ABC110 C String Manipulation
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Looking back on ABC155
Atcoder ABC115 Past Exercises
Solve Atcoder ABC176 (A, B, C, E) in Python
ABC147 C --HonestOrUnkind2 [Python]
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
AtCoder ABC 177 Python (A ~ E)
Solve AtCoder ABC166 with python
ABC163 C problem with python3
AtCoder ABC 178 Python (A ~ E)
Atcoder ABC164 A-C in Python
ABC129 A, B, C commentary
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)
ABC188 C problem with python3
I participated in AtCoder (ABC158)
Solve AtCoder ABC 186 with Python
ABC187 C problem with python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with Python!
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial