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:
class PSTNode():
    def __init__(self, val=None):
        self.val = val
        self.key = 0
        self.dep = None
        self.lt = None
        self.rt = None
        self.par = None

class PersistentSegmentTree():
    def __init__(self, q, array, func=min, ie=2**63-1):
        self.q = q
        self.h = (len(array) - 1).bit_length()
        self.n = 2**self.h
        array += [ie] * (self.n - len(array))
        self.roots = [None for _ in range(q + 2)]
        self.roots[-1] = root = PSTNode()
        root.dep = 0
        self.idx = -1
        self.func = func
        self.ie = ie
        stack = [root]
        order = [root]
        while stack:
            node = stack.pop()
            node.lt = PSTNode()
            node.rt = PSTNode()
            node.lt.par = node
            node.rt.par = node
            ndep = node.dep + 1
            node.lt.dep = ndep
            node.rt.dep = ndep
            node.lt.key = node.key
            node.rt.key = node.key + 2**(self.h - ndep)
            if ndep == self.h:
                node.lt.val = array[node.lt.key]
                node.rt.val = array[node.rt.key]
            else:
                stack.append(node.lt)
                stack.append(node.rt)
                order.append(node.lt)
                order.append(node.rt)
        for node in order[::-1]:
            node.val = self.func(node.lt.val, node.rt.val)

    def get_node(self, idx, t=-1):
        node = self.roots[t]
        k = self.h - 1
        while k != -1:
            if (idx >> k) & 1:
                node = node.rt
            else:
                node = node.lt
            k -= 1
        return node

    def get_val(self, idx, t=-1):
        return self.get_node(idx, t).val

    def set_val(self, idx, x, t=-1):
        old_node = self.get_node(idx, t)
        new_node = PSTNode(x)
        new_node.key = old_node.key
        for i in range(self.h):
            new_par = PSTNode()
            old_par = old_node.par
            new_par.key = old_par.key
            new_node.par = new_par
            if old_par.lt == old_node:
                new_par.lt = new_node
                new_par.rt = old_par.rt
                old_par.rt.par = new_par
            else:
                new_par.lt = old_par.lt
                new_par.rt = new_node
                old_par.lt.par = new_par
            new_par.val = self.func(new_par.lt.val, new_par.rt.val)
            old_node = old_par
            new_node = new_par
        self.roots[self.idx] = new_node

    def get_range(self, lt, rt, t=-1):
        node = self.roots[t]
        res = self.ie
        stack = [node]
        while stack:
            node = stack.pop()
            if lt <= node.key and node.key + 2**(self.h - node.dep) <= rt:
                res = self.func(res, node.val)
            elif node.key + 2**(self.h - node.dep) <= lt or rt <= node.key:
                continue
            else:
                stack.append(node.lt)
                stack.append(node.rt)
        return res

    def update(self):
        self.idx += 1
        self.roots[self.idx] = self.roots[self.idx - 1]

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

st = SegmentTree(A, gcd, 0)
res = 1

for i in range(N):
    res = max(res, gcd(st.query(0, i), st.query(i + 1, N)))

print(res)

Submission status: Accepted

Solution code:
class PSTNode():
    def __init__(self, val=None):
        self.val = val
        self.key = 0
        self.dep = None
        self.lt = None
        self.rt = None
        self.par = None

class PersistentSegmentTree():
    def __init__(self, q, array, func=min, ie=2**63-1):
        self.q = q
        self.h = (len(array) - 1).bit_length()
        self.n = 2**self.h
        array += [ie] * (self.n - len(array))
        self.roots = [None for _ in range(q + 2)]
        self.roots[-1] = root = PSTNode()
        root.dep = 0
        self.idx = -1
        self.func = func
        self.ie = ie
        stack = [root]
        order = [root]
        while stack:
            node = stack.pop()
            node.lt = PSTNode()
            node.rt = PSTNode()
            node.lt.par = node
            node.rt.par = node
            ndep = node.dep + 1
            node.lt.dep = ndep
            node.rt.dep = ndep
            node.lt.key = node.key
            node.rt.key = node.key + 2**(self.h - ndep)
            if ndep == self.h:
                node.lt.val = array[node.lt.key]
                node.rt.val = array[node.rt.key]
            else:
                stack.append(node.lt)
                stack.append(node.rt)
                order.append(node.lt)
                order.append(node.rt)
        for node in order[::-1]:
            node.val = self.func(node.lt.val, node.rt.val)

    def get_node(self, idx, t=-1):
        node = self.roots[t]
        k = self.h - 1
        while k != -1:
            if (idx >> k) & 1:
                node = node.rt
            else:
                node = node.lt
            k -= 1
        return node

    def get_val(self, idx, t=-1):
        return self.get_node(idx, t).val

    def set_val(self, idx, x, t=-1):
        old_node = self.get_node(idx, t)
        new_node = PSTNode(x)
        new_node.key = old_node.key
        for i in range(self.h):
            new_par = PSTNode()
            old_par = old_node.par
            new_par.key = old_par.key
            new_node.par = new_par
            if old_par.lt == old_node:
                new_par.lt = new_node
                new_par.rt = old_par.rt
                old_par.rt.par = new_par
            else:
                new_par.lt = old_par.lt
                new_par.rt = new_node
                old_par.lt.par = new_par
            new_par.val = self.func(new_par.lt.val, new_par.rt.val)
            old_node = old_par
            new_node = new_par
        self.roots[self.idx] = new_node

    def get_range(self, lt, rt, t=-1):
        node = self.roots[t]
        res = self.ie
        stack = [node]
        while stack:
            node = stack.pop()
            if lt <= node.key and node.key + 2**(self.h - node.dep) <= rt:
                res = self.func(res, node.val)
            elif node.key + 2**(self.h - node.dep) <= lt or rt <= node.key:
                continue
            else:
                stack.append(node.lt)
                stack.append(node.rt)
        return res

    def update(self):
        self.idx += 1
        self.roots[self.idx] = self.roots[self.idx - 1]

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

pst = PersistentSegmentTree(0, A, gcd, 0)
res = 1

for i in range(N):
    res = max(res, gcd(pst.get_range(0, i), pst.get_range(i + 1, N + 1)))

print(res)

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
left = [0]*(n+1)
right = [0]*(n+1)

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

Submission status: Accepted

Solution code:
from math import gcd

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
INF=float('inf')

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

class SegmentTree:
    def __init__(self,n,ele=0): #!
        self.ide_ele=ele
        self.num=2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
        
    def segfunc(self,x,y): #!
        return math.gcd(x,y)
    
    def init(self,init_val):#初期化
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]
        #built
        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 upgrade(self,k,x):#A[k]をxに変更
        k+=self.num-1
        self.seg[k]=x
        while k:
            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.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1==0:
                res=self.segfunc(res,self.seg[p])
            if q&1==1:
                res=self.segfunc(res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:
            res=self.segfunc(res,self.seg[p])
        else:
            res=self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

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

Submission status: Accepted

Solution code:
#a, b, k = map(int, input().split( ))
import math

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

left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (math.gcd(left[i],a[i]))
    right[n - i - 1] = (math.gcd(right[n - i],a[n - 1 - i]))
#print(left, right)

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


n = onem()

a = l()

R = [1 for i in range(n)]
L = [1 for i in range(n)]

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

for i in range(n):
    if i == 0:
        ma = max(ma,R[1])
    elif i == n-1:
        ma = max(ma,L[-2])
    else:
        ma = max(ma,gcd(L[i-1],R[i+1]))
print(ma)

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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

Left = [A[0]]
for i in range(N-1):
    Left.append(gcd(Left[i], A[i+1]))

Right = [A[N-1]]
for i in range(N-1):
    Right.append(gcd(Right[i], A[N-2-i]))
Right.reverse()

ans_list = []
ans_list.append(Right[1])
for i in range(1, N-1):
    ans_list.append(gcd(Left[i-1], Right[i+1]))
ans_list.append(Left[N-2])

print(max(ans_list))

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))

B = [0 for _ in range(N)]
C = [0 for _ in range(N)]

B[0] = A[0]
for i in range(1,N):
  B[i] = math.gcd(B[i-1],A[i])

C[N-1] = A[N-1]
for i in range(N-2,-1,-1):
  C[i] = math.gcd(C[i+1],A[i])
  
ans = max(C[1],B[N-2])
for i in range(1,N-1):
  #print(i, math.gcd(C[i+1],B[i-1]))
  ans = max(math.gcd(C[i+1],B[i-1]), ans)
          
print(ans)
#print(B)
#print(C)

Submission status: Accepted

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

import math
L = [0] * (N + 1)
R = [0] * (N + 1)

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

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

print(ans)

Submission status: Accepted

Solution code:
from math import gcd
#================================================
N=int(input())
A=list(map(int,input().split()))

F=[0]*N
G=[0]*N

F[0]=A[0]
G[-1]=A[-1]

for i in range(1,N):
    F[i]=gcd(F[i-1],A[i])
    G[-(i+1)]=gcd(G[-i],A[-(i+1)])

F=[0]+F+[F[-1]]
G=[G[0]]+G+[0]

M=0
for i in range(N):
    M=max(M,gcd(F[i],G[i+2]))
print(M)

Submission status: Accepted

Solution code:
import math

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

b=list(reversed(a))

g=[]
g.append(a[0])
for i in range(1,n):
  x=math.gcd(g[-1],a[i])
  g.append(x)

h=[]
h.append(b[0])
for j in range(1,n):
  y=math.gcd(h[-1],b[j])
  h.append(y)
  
ans=[]
for k in range(n):
  if k==0:
    ans.append(h[n-2])
  elif k==n-1:
    ans.append(g[n-2])
  else:
    e=g[k-1]
    f=h[n-1-k-1]
    ans.append(math.gcd(e,f))
    
print(max(ans))

Submission status: Accepted

Solution code:
def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    if n==2:
        print(a[1])
        return
    ans = 0
    g = math.gcd(a[0],a[1])
    ans_list = []
    for i in range(1,int(g**0.5)+1):
        if g%i==0:
            ans_list.append(i)
    ans_list.append(g)
    for an in ans_list:
        cnt = 0
        for i in range(n):
            if a[i] % an != 0:
                cnt += 1
        if cnt < 2:
            if an>ans:
                ans = an
    g = math.gcd(a[1],a[2])
    ans_list = []
    for i in range(1,int(g**0.5)+1):
        if g%i==0:
            ans_list.append(i)
    ans_list.append(g)
    for an in ans_list:
        cnt = 0
        for i in range(n):
            if a[i] % an != 0:
                cnt += 1
        if cnt < 2:
            if an>ans:
                ans = an
    g = math.gcd(a[0],a[2])
    ans_list = []
    for i in range(1,int(g**0.5)+1):
        if g%i==0:
            ans_list.append(i)
    ans_list.append(g)
    for an in ans_list:
        cnt = 0
        for i in range(n):
            if a[i] % an != 0:
                cnt += 1
        if cnt < 2:
            if an>ans:
                ans = an
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
b=a[::-1]
from math import gcd
L=[0]
R=[0]
for i in range(n-1):
  L.append(gcd(L[-1],a[i]))
  R.append(gcd(R[-1],b[i]))
ans=0
R=R[::-1]
#print(L,R)
for i in range(0,n-1+1):
  tmp=gcd(L[i],R[i])
  ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
import numpy as np
import math


n = int(input())
aList = list(map(int, input().split()))
gcdListLeft = [0 for i in range(n)]
gcdListRight = [0 for i in range(n)]

tmp = aList[0]
for i in range(n):
	tmp = gcdListLeft[i] = math.gcd(tmp, aList[i])

tmp = aList[n-1]
for i in range(n-1, -1, -1):
	tmp = gcdListRight[i] = math.gcd(tmp,aList[i])

ans = gcdListRight[1]
for i in range(1,n-1):
	ans = max(ans, math.gcd(gcdListLeft[i-1], gcdListRight[i+1]))
ans = max(ans, gcdListLeft[n-2])
print(ans)

Submission status: Accepted

Solution code:
import math

n=int(input())

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

L=[0]

for i in range(n):
  L.append(math.gcd(L[i],a[i]))

R=[0]
for i in range(n):
  R.append(math.gcd(R[i],a[n-1-i]))

ans=1
for i in range(n):
  ans=max(ans,math.gcd(L[i],R[n-1-i]))

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

L,R = [0],[0]

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

print(max(gcd(L[i],R[-i-1])for i in range(N)))

Submission status: Accepted

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

ra=list(reversed(a))

left=[]
right=[]
right.append(ra[0])
left.append(a[0])

if n>2:
  k=math.gcd(a[0],a[1])
  left.append(k)
  for i in range(2,n-1):
    k=math.gcd(k,a[i])
    left.append(k)

  k=math.gcd(ra[0],ra[1])
  right.append(k)
  for i in range(2,n-1):
    k=math.gcd(k,ra[i])
    right.append(k)

  ans=[right[-1]]
  for i in range(1,n-1):
    ans.append(math.gcd(left[i-1],right[len(right)-i-1]))
  ans.append(left[-1])
  print(max(ans))
else:
  print(max(a[1],a[0]))

Submission status: Accepted

Solution code:
import math

def main():
	N = int(input())
	A = [int(a) for a in input().split(" ")]
	gcd1 = []
	gcd2 = []
	for i in range(len(A)):
		if i == 0:
			gcd1.append(A[0])
			gcd2.append(A[-1])
		else:
			gcd1.append(math.gcd(A[i], gcd1[-1]))
			gcd2.insert(0, math.gcd(A[-i-1], gcd2[0]))

	gcds = []
	for i in range(N):
		if i == 0:
			gcds.append(gcd2[1])
		elif i == N - 1:
			gcds.append(gcd1[-2])
		else:
			gcds.append(math.gcd(gcd1[i-1], gcd2[-N+i+1]))
	print(max(gcds))

main()

Submission status: Accepted

Solution code:
from math import gcd


N, *A = map(int, open(0).read().split())

acc_l = [0] * (N + 1)
acc_r = [0] * (N + 1)
for i in range(1, N + 1):
    acc_l[i] = gcd(acc_l[i - 1], A[i - 1])
    acc_r[i] = gcd(acc_r[i - 1], A[-i])
ans = 0
for i in range(N + 1):
    ans = max(ans, gcd(acc_l[i], acc_r[N - i - 1]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
*A,=map(int,input().split())

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

def cum(array, merge, unit):
    new=[unit]
    for i in range(len(array)):
        new.append(merge(new[-1], array[i]))
    return new
  
cum1 = cum(A,gcd,A[0])
cum2 = cum(A[::-1],gcd,A[-1])[::-1]

res=[]
for i in range(N):
  if i == 0:
    tmp = cum2[i+1]
  elif i == N-1:
    tmp = cum1[i]
  else:
    tmp = gcd(cum1[i],cum2[i+1])
  res.append(tmp)
  
print(max(res))

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
from math import gcd
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def Enumeration(x):
    low = []
    high = []
    for i in range(1,x):
        if i**2 >= x:
            if i**2 == x:
                low.append(i)
            break
        if x%i == 0:
            low.append(i)
            high.append(x//i)
    return high+low[::-1]

def main():
    n = int(ipt())
    p = set()
    a = [int(i) for i in ipt().split()]
    if n == 2:
        print(max(a))
        exit()
    ma = 1
    G = gcd(gcd(a[0],a[1]),a[2])
    p.add(gcd(a[0],a[1]))
    p.add(gcd(a[0],a[2]))
    p.add(gcd(a[2],a[1]))

    for i in Enumeration(G):
        nm = 0
        for ai in a[3::]:
            if ai%i != 0:
                nm += 1
                if nm == 2:
                    break
        if nm < 2:
            if ma < i:
                ma = i
            break

    for i in p:
        for j in Enumeration(i):
            f = True
            for ai in a[3::]:
                if ai%j != 0:
                    f = False
                    break
            if f:
                if ma < j:
                    ma = j
                break

    print(ma)




    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import*
n=int(input())
a=list(map(int,input().split()))
b=[a[0]]
c=[a[-1]]
for i in range(1,n):
  b+=[gcd(b[-1],a[i])]
  c+=[gcd(c[-1],a[-i-1])]
ans=0
c=c[::-1]
for i in range(n):
  if i==0:ans=max(ans,c[i+1])
  elif i==n-1:ans=max(ans,b[i-1])
  else:
    ans=max(ans,gcd(c[i+1],b[i-1]))
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import gcd
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    vec1 = [0] * (N + 1)
    vec2 = [0] * (N + 1)
    for i in range(N):
        vec1[i + 1] = gcd(vec1[i], A[i])
    for i in range(N - 1, -1, -1):
        vec2[i] = gcd(vec2[i + 1], A[i])

    ans = 0
    for i in range(N):
        g = gcd(vec1[i], vec2[i + 1])
        if ans < g:
            ans = g

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from math import gcd
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    vec1 = list(accumulate(A, func=gcd))
    vec2 = list(accumulate(reversed(A), func=gcd))

    ans = 0
    for i in range(N):
        if i == 0:
            res = vec2[-2]
        elif i == N - 1:
            res = vec1[-2]
        else:
            res = gcd(vec1[i - 1], vec2[N - i - 2])

        if ans < res:
            ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
gcd = math.gcd
n = ni()
A = lma()
gcd_l = [1]*n
gcd_l[0]=A[0]
gcd_r =[1]*n
gcd_r[-1] = A[-1]
for i in range(1,n):
    gcd_l[i] = gcd(A[i],gcd_l[i-1])
    gcd_r[-i-1] = gcd(A[-i-1],gcd_r[-i])
ans = max(gcd_l[-2],gcd_r[1])
for i in range(1,n-1):
    ggg = gcd(gcd_l[i-1],gcd_r[i+1])
    ans = max(ans,ggg)
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
a = list(map(int, input().split()))
pf = [0] + list(itertools.accumulate(a, math.gcd))
pb = [0] + list(itertools.accumulate(reversed(a), math.gcd))
pb.reverse()
ans = [0]*n
for i in range(n):
  ans[i] = math.gcd(pf[i], pb[i+1])
print(max(ans))

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
a = list(map(int, input().split()))
pf = [0]*(n+1)
pb = [0]*(n+1)
p = a[0]
for i in range(n):
  p = math.gcd(p, a[i])
  pf[i+1] = p
p = a[-1]
for i in range(-1, -n-1, -1):
  p = math.gcd(p, a[i])
  pb[i-1] = p
ans = [0]*n
for i in range(n):
  ans[i] = math.gcd(pf[i], pb[i+1])
print(max(ans))

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    a = LIST()
    l = [0]*N
    r = [0]*N
    l[0] = a[0]
    r[N-1] = a[N-1]

    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])

    ans = max(r[1], l[N-2])
    for i in range(1, N-1):
        ans = max(ans, gcd(l[i-1], r[i+1]))
    print(ans)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

#####segfunc#####
def segfunc(x, y):
    return gcd(x, y)
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def solve():
    N = INT()
    a = LIST()
    seg = SegTree(a, segfunc, ide_ele)

    ans = 1
    for i in range(N):
        seg.update(i, 0)
        ans = max(ans, seg.query(0, N))
        seg.update(i, a[i])
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
n=int(input())
a = list(map(int,input().split()))
a.sort()
lr=[0]*n
rl=[0]*n

for i in range(n):
  if i==0:
    g=a[0]
    lr[0]=g
  else:
    g=math.gcd(a[i],g)
    lr[i]=g
    
for i in range(n-1,0,-1):
  if n-1==i:
    g=a[n-1]
    rl[n-1]=g
  else:
    g=math.gcd(a[i],g)
    rl[i]=g  
hantei=0
ans=0
#print(lr)
#print(rl)
for i in range(n):
  if i==0:
    hantei=rl[1]
  elif i==n-1:
    hantei=lr[n-2]
  else:
    hantei=math.gcd(lr[i-1],rl[i+1])
  if ans<=hantei:
    ans=hantei
    
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input().rstrip())
A = list(map(int,input().rstrip().split()))
l = [A[0]]
r = [A[-1]]
for i in range(len(A)-1):
    l.append(math.gcd(A[i+1],l[i]))
    r.append(math.gcd(A[-(i+2)],r[i]))
ans = []
ans.append(r[-2])
for i in range(len(A)-2):
    ans.append(math.gcd(l[i],r[-(i+3)]))
ans.append(l[-2])
print(max(*ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table

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

D = divisors(A[0]) + divisors(A[1])
D.sort(reverse=True)
for d in D:
    cnt = 0
    for a in A:
        if a%d:
            cnt += 1
    if cnt <= 1:
        print(d)
        exit()

Submission status: Accepted

Solution code:
import math

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