Problem:


Score : 300 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, written on the blackboard.

You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.

Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Sample Input 1

3
7 6 8

Sample Output 1

2

If we replace 7 with 4, the greatest common divisor of the three integers on the blackboard will be 2, which is the maximum possible value.

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=deque([self.unit])
        self.fold_l=deque([self.unit])
        self.data_r=deque()
        self.data_l=deque()
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(list(self.data_l)[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(list(self.data_r))
        if not self.data_l:
            return False
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    l,r=SWAG(0,gcd,[]),SWAG(0,gcd,a[1:])
    m=r.fold_all()
    for i in range(n-1):
        l.append(a[i])
        r.popleft()
        m=max(m,gcd(l.fold_all(),r.fold_all()))
    print(m)
main()

Submission status: Accepted

Solution code:
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(self.data_l[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        if not self.data_l:
            return False
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    l,r=SWAG(0,gcd,[]),SWAG(0,gcd,a[1:])
    m=r.fold_all()
    for i in range(n-1):
        l.append(a[i])
        r.popleft()
        m=max(m,gcd(l.fold_all(),r.fold_all()))
    print(m)
main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
from collections import deque

n = int(input())
a = deque(map(int,input().split()))

#累積GCD
left = deque([0])
right = deque([0])
for i in range(n):
    left.append(fractions.gcd(left[i],a[i]))
    right.appendleft(fractions.gcd(right[0],a[n - 1 - i]))

ans = 0
for i in range(n):
    ans = max(ans,fractions.gcd(left[i],right[i + 1]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import copy

class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = 2 ** (N-1).bit_length()
        self.func = copy.deepcopy(func)
        self.I = copy.deepcopy(I)
        self.seg = [copy.deepcopy(I) for i in range(self.sz * 2)]

    def assign(self, k, x):
        self.seg[k + self.sz] = copy.deepcopy(x)

    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = copy.deepcopy(x)
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = copy.deepcopy(self.I)
        R = copy.deepcopy(self.I)
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

N = int(input())
A = list(map(int,input().split()))

def f(x,y):
    if x * y == 0:
        return x + y
    else:
        return gcd(x,y)

seg = SegmentTree(N + 1, f, 0)
for i in range(N):
    seg.assign(i , A[i])
seg.build()

ans = 1
for i in range(N):
    ans = max(ans , f(seg.query(0 , i) , seg.query(i + 1 , N)))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
A = [int(i) for i in input().split()]

cuml = [0]
cumr = [0]

for i in range(N):
    cuml.append(gcd(cuml[i], A[i]))
    cumr.append(gcd(cumr[i], A[N-i-1]))


maxg = 0
for i in range(N):
    # print(gcd(cuml[i], cumr[N-i-1]))
    maxg = max(maxg, gcd(cuml[i], cumr[N-i-1]))
print(maxg)

Submission status: Accepted

Solution code:
import fractions
n = int(input())
a = list(map(int,input().split()))
m = []
l = [0]
r = [0]
for i in range(n):
  l.append(fractions.gcd(l[i],a[i]))
  r.append(fractions.gcd(r[i],a[-i-1]))
r.reverse()
for i in range(n):
  m.append(fractions.gcd(l[i],r[i+1]))
print(max(m))

Submission status: Accepted

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter
    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    A = list(map(int, input().split()))

    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    l = [0]
    for i in range(N-1):
        l.append(gcd(l[-1], A[i]))
    r = [0]
    for i in range(N-1, 0, -1):
        r.append(gcd(r[-1], A[i]))
    
    res = 0
    for i in range(N):
        res = max(res, gcd(l[i], r[-(i+1)]))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))

mx = 0
gd_pos = [] # 0からiまでのgcd
gd_pos.append(a[0])
for i in range(1, n):
    gd_pos.append(fractions.gcd(gd_pos[i-1], a[i]))
gd_neg = [] # 末尾からiまでのgcd
gd_neg.append(a[-1])
a_rev = a[::-1]
for i in range(1, n):
    gd_neg.append(fractions.gcd(gd_neg[i-1], a_rev[i]))

def popped_g(i):
    if i == 0: return gd_neg[n-2]
    elif i == n-1: return gd_pos[n-2]
    else:
        return fractions.gcd(gd_pos[i-1], gd_neg[n-i-2])

ans = [popped_g(i) for i in range(n)]
print(max(ans))

Submission status: Accepted

Solution code:
import functools

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def gcd(nums):
    return functools.reduce(euclid, nums)

N = int(input())
A = list(map(int,(input().split())))
L = [0]*N
R = [0]*N
L[0] = A[0]
R[0] = A[N-1]
for i in range(1,N):
    L[i] = gcd([L[i-1],A[i]])
for i in range(1,N):
    R[i] = gcd([R[i-1],A[N-1-i]])

p = []

for i in range(N):
    if i == 0:
        p.append(R[N-2])
    elif i == N-1:
        p.append(L[N-2])
    else:
        p.append( gcd([L[i-1], R[N-2-i]]) )

print(max(p))

Submission status: Accepted

Solution code:
from fractions import gcd
N, *A, = map(int, open(0).read().split())
l = [0]*N
r = [0]*N

# [0,i]のgcd
l[0] = A[0]
for i in range(1, N):
    l[i] = gcd(l[i-1],A[i])

# [i,N-1]のgcd
r[N-1] = A[N-1]
for i in range(N-1)[::-1]:
    r[i] = gcd(r[i+1],A[i])

m = [0]*N
for i in range(1, N-1):
    m[i] = gcd(l[i-1], r[i+1])
m[0] = r[1]
m[N-1] = l[N-2]
print(max(m))

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int,input().split()))

M = [0]*N

#漸化式を作る
L = [0]*N
R = [0]*N

for i in range(1,N):
    L[i] = gcd(L[i-1],A[i-1])
    R[N-1-i] = gcd(R[N-i],A[N-i])

for j in range(N):
    M[j] = gcd(L[j],R[j])

print(max(M))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

def gcd(x, y):
    if x < y:
         x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y

l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
for i in range(0, n - 1):
    if i == 0:
        l[i] = a[0]
    else:
        l[i] = gcd(l[i - 1], a[i])

for i in range(n - 1, 0, -1):
    if i == n - 1:
        r[i] = a[i]
    else:
        r[i] = gcd(a[i], r[i + 1])

max = 0
for i in range(n):
    if i == 0:
        gcd_i = r[i + 1]
    elif i == n - 1:
        gcd_i = l[i - 1]
    else:
        gcd_i = gcd(l[i - 1], r[i + 1])
    if max < gcd_i:
        max = gcd_i

print(max)

Submission status: Accepted

Solution code:
# import bisect
# import copy
from fractions import gcd


# import math
# import numpy as np
# from collections import Counter, deque
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
import sys
sys.setrecursionlimit(10**9)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    # A[0:i]の最大公約数
    L=[0]*N
    for i in range(1,N):
        L[i]=gcd(L[i - 1], A[i - 1])

    # A[i:]の最大公約数
    R=[0]*(N+1)
    for i in reversed(range(N)):
        R[i]=gcd(R[i + 1], A[i])


    maxgcd = 0
    for i in range(N):
        maxgcd = max(maxgcd, gcd(L[i], R[i + 1]))

    print(maxgcd)


resolve()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

n = int(input())
a = list(map(int,input().split()))

#累積GCD
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (fractions.gcd(left[i],a[i]))
    right[n - i - 1] = (fractions.gcd(right[n - i],a[n - 1 - i]))

ans = 0
for i in range(n):
    ans = max(ans,fractions.gcd(left[i],right[i + 1]))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from fractions import gcd
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    A=list(map(int,readline().split()))
    A.insert(0,0)
    A.append(0)

    L=[0]*N
    R=[0]*N
    for i in range(1,N):
        L[i]=gcd(L[i-1],A[i])
    for i in range(N-2,-1,-1):
        R[i]=gcd(R[i+1],A[i+2])

    res=0
    for i in range(N):
        res=max(res,gcd(L[i],R[i]))
    print(res)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from fractions import gcd
n = inn()
a = inl()
l = [a[0]]*n
for i in range(1,n):
    l[i] = gcd(l[i-1],a[i])
r = [a[n-1]]*n
for i in range(n-2,-1,-1):
    r[i] = gcd(r[i+1],a[i])
mx = max(l[n-2],r[1])
for i in range(1,n-1):
    mx = max(mx, gcd(l[i-1],r[i+1]))
print(mx)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #

from fractions import gcd
n = inn()
a = inl()
sgt = Segtree(n,0,gcd)
sgt.setary(a)
mx = max(sgt.query(1,n), sgt.query(0,n-1))
for i in range(1,n-1):
    g = gcd(sgt.query(0,i),sgt.query(i+1,n))
    mx = max(mx,g)
print(mx)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    if a==b:
      return a
    else:
      a,b=max(a,b),min(a,b)
      if a%b==0:
        return b
      else:
        return gcd(b,a%b)
R=[]
L=[]
for i in range(n):
  if i==0:
    L.append(a[i])
    R.append(a[-i-1])
  else:
    vl,vr=gcd(a[i],L[-1]),gcd(a[-i-1],R[-1])
    L.append(vl)
    R.append(vr)
ans=0
for i in range(n):
  if i==0:
    ans=max(ans,R[-i-2])
  elif i==n-1:
    ans=max(ans,L[i-1])
  else:
    ans=max(ans,gcd(L[i-1],R[-i-2]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = [int(i) for i in input().split()]

b = [0] * n
c = [0] * n

j = 0
for i, k in enumerate(a):
    b[i] = j
    j = gcd(j, k)

j = 0
for i, k in reversed(list(enumerate(a))):
    c[i] = j
    j = gcd(j, k)

ma = 0
for i in range(n):
    ma = max(ma, gcd(b[i], c[i]))
print(ma)

Submission status: Accepted

Solution code:
class SegTree():
    def __init__(self,data,unit,f):
        self.size=n=len(data)
        self.data=[unit for _ in range(n)]+data
        for i in range(n-1,0,-1):self.data[i]=f(self.data[i+i],self.data[i-~i])
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=x
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def add(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def query(self,l,r):
        c,f=self.data,self.f
        x,y=self.unit,self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l&1:
                x=f(x,c[l])
                l+=1
            if r&1:
                r-=1
                y=f(c[r],y)
            l>>=1
            r>>=1
        return f(x,y)
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    f=SegTree(a,0,gcd).query
    m=max(f(1,n),f(0,n-1))
    for i in range(n-2):
        m=max(m,gcd(f(0,i+1),f(i+2,n)))
    print(m)
main()

Submission status: Accepted

Solution code:
class DisjointSparseTable():
    def __init__(self,data,f):
        from math import ceil,log#2
        self.n=n=len(data)
        m=ceil(log(n,2)) # ceil(log2(n))
        self.f=f
        self.h=[0,0]
        for i in range(2,2**m):self.h.append(self.h[i//2]+1)
        self.data=[data]
        for i in range(1,m):
            d=[0]*n
            w=2**i
            for j in range(0,n,w*2):
                c=min(j+w,n)
                d[c-1]=data[c-1]
                for k in range(c-2,j-1,-1):d[k]=f(data[k],d[k+1])
                if c<n:
                    d[c]=data[c]
                    for k in range(c+1,min(j+w*2,n)):d[k]=f(data[k],d[k-1])
            self.data.append(d)
    def get(self,l,r): # [l,r)
        r-=1
        if l==r:return self.data[0][l]
        d=self.data[self.h[l^r]]
        return self.f(d[l],d[r])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    f=DisjointSparseTable(a,gcd).get
    m=max(f(1,n),f(0,n-1))
    for i in range(n-2):
        m=max(m,gcd(f(0,i+1),f(i+2,n)))
    print(m)
main()

Submission status: Accepted

Solution code:
from fractions import gcd
n=int(input())
A=list(map(int, input().split()))
#####segfunc######
def segfunc(x,y):
  return gcd(x,y)

def init(init_val):
  #set_val
  for i in range(n):
    seg[i+num-1]=init_val[i]    
  #built
  for i in range(num-2,-1,-1) :
    seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
  k += num-1
  seg[k] = x
  while k:
    k = (k-1)//2
    seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
  if q<=p:
    return ide_ele
  p += num-1
  q += num-2
  res=ide_ele
  while q-p>1:
    if p&1 == 0:
      res = segfunc(res,seg[p])
    if q&1 == 1:
      res = segfunc(res,seg[q])
      q -= 1
    p = p//2
    q = (q-1)//2
  if p == q:
    res = segfunc(res,seg[p])
  else:
    res = segfunc(segfunc(res,seg[p]),seg[q])
  return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

ans=-1
init(A)
for i in range(n):
  ans=max(ans, gcd(query(0,i), query(i+1,n)))
  
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int, input().split()))
LtR=[0]*N
LtR[0]=A[0]
RtL=[0]*N
RtL[-1]=A[-1]
for i in range(N-1):
  LtR[i+1]=gcd(A[i+1],LtR[i])
  RtL[-(i+2)]=gcd(A[-(i+2)], RtL[-(i+1)])
  
  
ans=max(LtR[-2], RtL[1])
for i in range(1,N-1):
  ans=max(ans, gcd(LtR[i-1], RtL[i+1]))
  
#print(LtR, RtL)
print(ans)

Submission status: Accepted

Solution code:
import fractions

N = int(input())
A = list(map(int, input().split()))

left = [0]*(N+1)
for i in range(1,N+1):
    left[i] = fractions.gcd(left[i-1],A[i-1])

right = [0]*(N+1)
right[N-1] = A[N-1]
for i in range(N-2,-1,-1):
    right[i] = fractions.gcd(right[i+1],A[i])

ans = 0
for i in range(N):
    ans = max(ans,fractions.gcd(left[i],right[i+1]))
print(ans)

Submission status: Accepted

Solution code:
# 区間[i,j]における最小値を返す
# 値の更新をする
import sys,fractions
input = sys.stdin.readline
class segment_tree:
    '''
    init_val(int): 初期化値
    Input(array):  入力
    '''
    def __init__(self, init_val, Input):
        #self.num:n以上の最小の2のべき乗(一番下のNodeの数)
        n=len(Input)
        self.init_val = init_val
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [init_val] * 2 * self.num
        for i in range(n):
            self.seg[i + self.num - 1] = Input[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i]=self._segfunc(self.seg[2*i+1],self.seg[2*i+2])
    def _segfunc(self, left, right):
        '''
        ここに求めたい関数を入れる
        ex)最小値問題→min, 
        left:左の子
        right:右の子
        '''
        res=fractions.gcd(left,right)
        return res
    def update(self, k, x):
        '''
        k番目の値をxに書き換える
        '''
        k += self.num - 1
        self.seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.seg[k] = self._segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    def query(self, p, q):
        '''
        区間[p,q)の目的の値を取り出す
        '''
        if q <= p:
            return self.init_val
        p += self.num - 1
        q += self.num - 2
        res = self.init_val
        while q - p > 1:
            if p % 2 == 0: #始点が偶数or終点が奇数だと端っこが余る
                res = self._segfunc(res, self.seg[p])
            if q % 2 == 1:
                res = self._segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        res = self._segfunc(res, self.seg[p])
        res = self._segfunc(res, self.seg[q])
        return res
INF = 10 ** 10
n=int(input())
a=list(map(int,input().split()))

# a = [randint(0,N*2) for _ in range(N)]
dp = segment_tree(0, a)
ans=-1
for i in range(n):
  ans=max(ans,fractions.gcd(dp.query(0,i),dp.query(i+1,n)))
print(ans)

Submission status: Accepted

Solution code:
# セグメント木を用いた解法
from fractions import gcd
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    # セグ木は 1-indexed
    def __init__(self, n, initial=0):
        """
        n: 配列の大きさ
        initial: 単位元 (RMQでは大きな値)
        """
        self.offset = 2**(n-1).bit_length()  # 2進数表記の長さ
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)
        

    def build(self, A):
        """
        A: 処理したい配列
        """
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = a
        for i in range(self.offset-1,0,-1):
            self.seg[i] = gcd(self.seg[i<<1] ,self.seg[(i<<1)+1])

            
    def update(self, k, a):
        """
        k番目の値をaに変更
        """
        k += self.offset
        self.seg[k] = a
        while k:
            k >>= 1
            self.seg[k] = gcd(self.seg[k<<1], self.seg[(k<<1)+1])

            
    def query(self, a, b):
        """
        区間[a, b)に対して最小公倍数を求める
        """
        a += self.offset
        b += self.offset - 1 
        res = self.initial
        while a < b:
            if a & 1:  # 兄弟の右なら
                res = gcd(res, self.seg[a])
                a += 1
            if not b & 1:  # 兄弟の左なら
                res = gcd(res, self.seg[b])
                b -= 1
            a >>= 1
            b >>= 1
        
        if a == b:
            res = gcd(res, self.seg[a])
        
        return res


if __name__ == "__main__":
    N = int(readline())
    A = [int(i) for i in readline().split()]
    seg = SegmentTree(N)
    seg.build(A)

    ans = seg.query(1, N)
    for i in range(N-2):
        tmp = gcd(seg.query(0, i+1), seg.query(i+2, N))
        ans = max(ans, tmp)
    ans = max(ans, seg.query(0, N-1))

    print(ans)

Submission status: Accepted

Solution code:
# セグメント木を用いた解法

from fractions import gcd
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    # セグ木は 1-indexed
    def __init__(self, n, initial=0):
        """
        n: 配列の大きさ
        initial: 単位元 (RMQでは大きな値)
        """
        self.offset = 2**(n-1).bit_length()  # 2進数表記の長さ
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)
        

    def build(self, A):
        """
        A: 処理したい配列
        """
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = a
        for i in range(self.offset-1,0,-1):
            self.seg[i] = gcd(self.seg[i<<1] ,self.seg[(i<<1)+1])

            
    def update(self, k, a):
        """
        k番目の値をaに変更
        """
        k += self.offset
        self.seg[k] = a
        while k:
            k >>= 1
            self.seg[k] = gcd(self.seg[k<<1], self.seg[(k<<1)+1])

            
    def query(self, a, b):
        """
        区間[a, b)に対して最小公倍数を求める
        """
        a += self.offset
        b += self.offset - 1 
        res = self.initial
        while a < b:
            if a & 1:  # 兄弟の右なら
                res = gcd(res, self.seg[a])
                a += 1
            if not b & 1:  # 兄弟の左なら
                res = gcd(res, self.seg[b])
                b -= 1
            a >>= 1
            b >>= 1
        
        if a == b:
            res = gcd(res, self.seg[a])
        
        return res


if __name__ == "__main__":
    N = int(readline())
    A = [int(i) for i in readline().split()]
    seg = SegmentTree(N)
    seg.build(A)

    ans = seg.query(1, N)
    for i in range(N-2):
        tmp = gcd(seg.query(0, i+1), seg.query(i+2, N))
        ans = max(ans, tmp)
    ans = max(ans, seg.query(0, N-1))

    print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    # セグ木は 1-indexed
    def __init__(self, n, initial=0):
        """
        n: 配列の大きさ
        initial: 単位元 (RMQでは大きな値)
        """
        self.offset = 2**(n-1).bit_length()  # 2進数表記の長さ
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)
        

    def build(self, A):
        """
        A: 処理したい配列
        """
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = a
        for i in range(self.offset-1,0,-1):
            self.seg[i] = gcd(self.seg[i<<1] ,self.seg[(i<<1)+1])

            
    def update(self, k, a):
        """
        k番目の値をaに変更
        """
        k += self.offset
        self.seg[k] = a
        while k:
            k >>= 1
            self.seg[k] = gcd(self.seg[k<<1], self.seg[(k<<1)+1])

            
    def query(self, a, b):
        """
        区間[a, b)に対して最小公倍数を求める
        """
        a += self.offset
        b += self.offset - 1 
        res = self.initial
        while a < b:
            if a & 1:  # 兄弟の右なら
                res = gcd(res, self.seg[a])
                a += 1
            if not b & 1:  # 兄弟の左なら
                res = gcd(res, self.seg[b])
                b -= 1
            a >>= 1
            b >>= 1
        
        if a == b:
            res = gcd(res, self.seg[a])
        
        return res


if __name__ == "__main__":
    N = int(readline())
    A = [int(i) for i in readline().split()]
    seg = SegmentTree(N)
    seg.build(A)

    ans = seg.query(1, N)
    for i in range(N-2):
        tmp = gcd(seg.query(0, i+1), seg.query(i+2, N))
        ans = max(ans, tmp)
    ans = max(ans, seg.query(0, N-1))

    print(ans)

Submission status: Accepted

Solution code:
def gcd(x: int, y: int):
    if x < y:
        x, y = y, x
    if y == 0:
        return x
    return gcd(x % y, y)

N = int(input())
A = list(map(int, input().split()))
L = [A[0]]
R = [A[N - 1]]

for i in range(N - 1):
    L.append(gcd(L[i], A[i + 1]))
    R.append(gcd(R[i], A[N - i - 2]))

R.reverse()

ans = 0
for i in range(0, N):
    if i == 0:
        ans = max(ans, R[i + 1])
    elif i == N -1:
        ans = max(ans, L[i - 1])
    else:
        ans = max(ans, gcd(L[i - 1], R[i + 1]))

print(ans)

Submission status: Accepted

Solution code:
"""
AtCoder Beginner Contest 125  C - GCD on Blackboard

配列中の数字を一つ好きな値に書き換えて最大公約数を計算するときの最大値を求める
・書き換える→取り除くと考えてよい。
・全体のGCD = GCD(前半のGCD, 後半のGCD) のように、分割したり順番を入れ替えたりしても結果は変わらない。
なので、左からの累積GCDと、右からの累積GCDをあらかじめとっておくことで、要素を一個除いたときの全体のGCDも求められる。　

区間に対する処理 -> セグメント木いけるやん
"""
class SegmentTree:
    # セグメント木として初期化する配列、単位元、[a,b)に実行する関数
    def __init__(self, lst, ide_ele, segfunc):
        self.ide_ele = ide_ele
        self.func = segfunc
        # lstのサイズより大きい2^xで最小の値
        self.size = 2**(len(lst) - 1).bit_length()
        self.seg_lst = [self.ide_ele] * 2 * self.size

        """
        値を詰めていく
        ノードiの親：(i-1) // 2
        ノードiの子：2*i+1 と　2*i+2

        """
        for i in range(len(lst)):
            self.seg_lst[i + self.size - 1] = lst[i]

        # クエリが実行されたときに取り出せるように処理をしておく
        # この辺は何がしたいかによって自分で関数用意する
        for i in range(self.size-2, -1, -1):
            # 子から親に向かって結果を吸い上げるような形
            self.seg_lst[i] = self.func(self.seg_lst[2*i + 1], self.seg_lst[2*i + 2])

    def update(self, i, num):
        # 一番下の子の部分を更新するため、配列中のindexからseg_lstのindexに変える
        i += self.size - 1
        self.seg_lst[i] = num
        while i:
            # 親に更新を伝播
            i = (i - 1) // 2
            self.seg_lst[i] = self.func(self.seg_lst[2*i + 1], self.seg_lst[2*i + 2])

    def query(self, l, r):
        # 範囲がおかしい場合
        if r <= l:
            return self.ide_ele

        # seg_lst内でのindexに直す
        l += self.size - 1
        # 
        r += self.size - 2
        ret = self.ide_ele
        # 区間が閉じ切る = 同じ親のところに戻るまで
        while r - l > 1:
            # lの下位1ビットが立っていない。たぶんだが、あるノードの左右の子の左が範囲に入ってるかどうかの判断で、入ってないときか？
            if l & 1 == 0:
                # 一番初めは単位減であるretとlについてfuncをかけることになるので、やはり左の子が範囲に入ってないとき！
                ret = self.func(ret, self.seg_lst[l])
            # こっちは右の子が入ってるかどうかで、入っている場合の処理だと思う
            if r & 1 == 1:
                # 一番最初は単位元とrの処理なので、右側が範囲に入ってない時。
                ret = self.func(ret, self.seg_lst[r])
                r -= 1

            # それぞれの親に移動というか、一個上のdepthに移動
            l = l // 2
            r = (r - 1) // 2

        # retには下から積み上げてきたself.funcの結果が入ってるので、たどり着いた親の所で同じく処理を実行して戻す
        if l == r:
            ret = self.func(ret, self.seg_lst[l])
        else:
            ret = self.func(self.func(ret, self.seg_lst[l]), self.seg_lst[r])
        
        return ret

    
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))

seg_tree = SegmentTree(A, 0, gcd)

ans = -1

for i in range(N):
    # 要素iを除いたときの全体のGCD
    ans = max(ans, gcd(seg_tree.query(0, i), seg_tree.query(i+1, N)))

print(ans)

Submission status: Accepted

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


class Ruiseki_lr:
    """左右からの畳み込みをそれぞれ計算する"""
    def __init__(self, array, op, e):
        self.op = op
        self.e = e

        n = len(array)
        self.left = [e] * (n + 1)
        self.right = [e] * (n + 1)
        for i in range(n):
            self.left[i + 1] = self.op(self.left[i], array[i])
        for i in reversed(range(n)):
            self.right[i] = self.op(self.right[i + 1], array[i])

    def left(self, p):
        """区間[0, p)の畳み込み結果を返す"""
        return self.left[p]
    
    def right(self, p):
        """区間[p, n)の畳み込みを返す"""
        return self.right[p]

    def fold(self, p):
        """p番目を除いた区間[0, n)の畳み込み結果を返す"""
        return self.op(self.left[p], self.right[p + 1])


n = int(input())
a = list(map(int, input().split()))
ru = Ruiseki_lr(a, gcd, 0)

ans = 0
for i in range(n):
    ans = max(ru.fold(i), ans)
print(ans)