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 fractions import gcd
N = int(input())
A = list(map(int, input().split()))

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

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

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

# 端っこをぬかした条件
# A[0  ]ぬかした場合, R[ 1]
# A[N-1]ぬかした場合, L[-2]
result = max(R[1],L[-2])

# 端っこ以外をfor文で
for i in range(1, N-1):
    result = max(result, gcd(L[i-1],R[i+1]))

print(result)

Submission status: Accepted

Solution code:
# coding:utf-8
import fractions


def main():
    N = int(input())
    num = list(map(int, input().split()))

    gcd_max = 0
    gcd_list_front = []
    gcd_list_back = []

    gcd_list_front.append(num[0])
    gcd_list_back.append(num[-1])

    for i in range(1, N-1):
        gcd_list_front.append(fractions.gcd(gcd_list_front[i-1], num[i]))
        gcd_list_back.append(fractions.gcd(gcd_list_back[i-1], num[-i-1]))

    gcd_list_back.reverse()
    gcd_max = max(gcd_list_back.pop(0), gcd_list_front.pop(-1))

    for i in range(len(gcd_list_front)):
        temp_gcd = fractions.gcd(gcd_list_front[i], gcd_list_back[i])
        if temp_gcd > gcd_max:
            gcd_max = temp_gcd

    print(gcd_max)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

L = []
for i in range(len(a)):
    if i==0:
        L.append(None)
    elif i ==1:
        L.append(a[i-1])
    else:
        L.append(gcd(L[-1], a[i-1]))
        
R = []
for i in range(len(a)):
    if i==0:
        R.append(None)
    elif i ==1:
        R.append(a[-i])
    else:
        R.append(gcd(R[-1], a[-i]))
R = R[::-1]


max_val = 0
for r, l in zip(L,R):
    if r==None:
        val = l
    elif l==None:
        val = r
    else:
        val = gcd(r, l)
        
    if val > max_val:
        max_val = val
print(max_val)

Submission status: Accepted

Solution code:
# coding:utf-8
import fractions


def main():
    N = int(input())
    # N = 10 ** 5
    num = list(map(int, input().split()))
    # num = list(range(1, 10**5 + 1))
    # num.sort()
    gcd = 0
    gcd_list_front = []
    gcd_list_back = []
    gcd_list_front.append(num[0])
    gcd_list_back.append(num[-1])

    for i in range(1, N-1):
        gcd_list_front.append(fractions.gcd(gcd_list_front[i-1], num[i]))
        gcd_list_back.append(fractions.gcd(gcd_list_back[i-1], num[-i-1]))

    gcd_list_back.reverse()
    # print(gcd_list_front)
    # print(gcd_list_back)

    gcd = max(gcd_list_back[0], gcd_list_front[-1])

    for i in range(0, N-2):
        # print(gcd_list_front[i], gcd_list_back[i+1])
        temp_gcd = fractions.gcd(gcd_list_front[i], gcd_list_back[i+1])
        if temp_gcd > gcd:
            gcd = temp_gcd

    print(gcd)
    # ans = 0
    # print()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import *
n = int(input())
a = [0] + list(map(int, input().split())) + [0]
b = [0] * (n+2)
c = [0] * (n+2)

for i in range(1, n+1):
    b[i] = gcd(b[i-1], a[i])
for i in range(n,0,-1):
    c[i] = gcd(c[i+1], a[i])

ans = 1
for i in range(1, n+1):
    if ans < gcd(b[i-1], c[i+1]):
        ans = gcd(b[i-1], c[i+1])
print(ans)

Submission status: Accepted

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

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

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

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

result = max(R[1],L[-2])

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

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
A = list(map(int,input().split()))
X = [0 for i in range(n)]
Y = [0 for i in range(n)]
for i in range(1,n):
    X[i] = gcd(X[i-1],A[i-1])
for i in range(n-1)[::-1]:
    Y[i] = gcd(Y[i+1],A[i+1])
#print(X)
#print(Y)
Z = [gcd(X[i],Y[i]) for i in range(n)]
print(max(Z))

Submission status: Accepted

Solution code:
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    tmp = A[0]
    gcdA = [0] * N
    gcdB = [0] * N
    gcdA[0] = A[0]
    gcdB[N-1] = A[N-1]
    for i in range(1, N):
        gcdA[i] = gcd(A[i], gcdA[i-1])
        gcdB[N-i-1] = gcd(A[N-i-1], gcdB[N-i])
    ans = max(gcdA[N-2], gcdB[1])
    for i in range(1, N-1):
        ans = max(ans, gcd(gcdA[i-1], gcdB[i+1]))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-
 
# abc125_c
import fractions, functools, itertools
 
# input
n = int(input())
A = [int(s) for s in input().split()]
# get ans
x = A[0]
y = A[1]
def divisors(n):
     for i in range(1, n+1):
        if i*i > n:
            break
        if n%i == 0:
            yield i
            yield n//i
ds = set(divisors(x)) | set(divisors(y))
def condition(d):
    not_div = (a%d != 0 for a in A)
    not_div = (1 if b else 0 for b in not_div)
    return sum(not_div) <= 1
ans = max(filter(condition, ds))
# output
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
N=int(input())
A=list(map(int,input().split()))

L=[0,0]#why
for ai in A:
    L.append(gcd(L[-1],ai))
    #print(L)

R=[0,0]#why
for ai in A[::-1]:
    R.append(gcd(R[-1],ai))
    #print(R)
#下のやつの解明
max=0
for l,r in zip(L,reversed(R)):
    if(gcd(l,r)>max):
        max=gcd(l,r)

print(max)

Submission status: Accepted

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

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

gcds = []
for i in range(N):
    gcds.append(gcd(gcd_l[i], gcd_r[-(i+2)]))
ans = max(gcds)
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))

from itertools import accumulate

gcds = []
left_all_gcd = list(accumulate(A, gcd))
right_all_gcd = list(accumulate(A[::-1], gcd))
for i in range(len(A)):
    if i == 0:
        gcds.append(right_all_gcd[-2])
    if i == len(A)-1:
        gcds.append(left_all_gcd[-2])
    else:
        hoge = [left_all_gcd[i-1]] + [right_all_gcd[-i-1]]
        gcds.append(gcd(left_all_gcd[i-1], right_all_gcd[-i-2]))

print(max(gcds))

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math


def gcd_ab(a,b):
  a,b = sorted([a,b])
  if a == 0:
    return b
  return gcd_ab(b%a, a)

if __name__ == "__main__": 
  N = int(input())
  An = list(map(int, sys.stdin.readline().rstrip().split()))
  cum = [[0,0] for i in range(N+2)]

  for i in range(N):
    cum[i+1][0] = gcd_ab(cum[i][0], An[i])
    cum[N-i][1] = gcd_ab(cum[N-i+1][1], An[N-i-1])

  ans = [0 for i in range(N)]
  for i in range(1,N+1):
    ans[i-1] = gcd_ab(cum[i-1][0], cum[i+1][1])
  print(max(ans))

Submission status: Accepted

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

N=int(input())
A=[int(i) for i in input().split()]
X=[0 for i in range(N)]
Y=[0 for i in range(N)]
for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])
Z=[gcd(X[i],Y[i]) for i in range(N)]
print(max(Z))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]


class SegmentTree():
    def __init__(self, array, m, e, size):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        m : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
        """
        self.m = m
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):  # set value at position p (0-indexed)
        m, n, dat = self.m, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = m(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        m, e, n, dat = self.m, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = m(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = m(res, dat[r])
            l >>= 1
            r >>= 1
        return res


gcd = lambda x, y: gcd(y, x) if x < y else gcd(y, x % y) if y else x
e = 0
size = N
ST = SegmentTree(A, m=gcd, e=e, size=size)
ans = 1
for i, a in enumerate(A):
    ST.modify(i, 0)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]


class SegmentTree():
    def __init__(self, array, m, e, size):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        m : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
        """
        self.m = m
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):  # set value at position p (0-indexed)
        m, n, dat = self.m, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = m(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        m, e, n, dat = self.m, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = m(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = m(res, dat[r])
            l >>= 1
            r >>= 1
        return res


gcd = lambda x, y: gcd(y, x) if x < y else x if y == 0 else gcd(y, x % y)
e = 0
size = N
ST = SegmentTree(A, m=gcd, e=e, size=size)
ans = 1
for i, a in enumerate(A):
    ST.modify(i, 0)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)

Submission status: Accepted

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


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

left = A.copy()
right = A.copy()

for i in range(1, N):
    left[i] = gcd(left[i-1], left[i])

for i in reversed(range(0, N-1)):
    right[i] = gcd(right[i+1], right[i])

ans = max(right[1], left[-2])

for i in range(1, N-1):
    ans = max(ans, gcd(left[i-1], right[i+1]))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc125_c
import fractions, functools, itertools

# input
n = int(input())
A = [int(s) for s in input().split()]
# get ans
gcd = fractions.gcd
L = list(itertools.accumulate(A, gcd))
R = list(itertools.accumulate(A[::-1], gcd))
R = R[::-1]
L.append(0)
R.append(0)
gs = [gcd(L[i-1], R[i+1]) for i in range(n)]
ans = max(gs)
# output
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
l = [0]
r = [0]*n

first = a[0]
for i in a:
    first = gcd(first,i)
    l.append(first)
    
last = a[-1]
for i in range(len(r))[::-1]:
    last = gcd(last,a[i])
    r[i] = last
    
r.append(0)
ans = 0
    
for i in range(len(a)):
    a = l[i]
    b = r[i+1]
    temp = gcd(a,b)
    ans = max(ans,temp)
    
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    a, b = min(a, b), max(a, b)
    while b % a != 0:
        a, b = b % a, a
    return a


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

# s = [-1, *a[:-1]]
# t = [*a[1:], -1]
s = [-1] * n
t = [-1] * n
for x in range(0, n - 1):
    s[x + 1] = a[x]
for x in range(1, n):
    t[x - 1] = a[x]

for x in range(1, n - 1):
    s[x + 1] = gcd(s[x + 1], s[x])
for x in range(n - 2, 0, -1):
    t[x - 1] = gcd(t[x - 1], t[x])

ans = -float('inf')
for x, y in zip(s, t):
    if x == -1:
        ans = max(ans, y)
    elif y == -1:
        ans = max(ans, x)
    else:
        ans = max(ans, gcd(x, y))
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from fractions import gcd
import functools
l=[(t.append(gcd(t[i-1],a[i])),t)[1] for t in [[a[0]]] for i in range(1, n)][0]
r=[(t.append(gcd(t[i-1],a[n-1-i])),t)[1] for t in [[a[n-1]]] for i in range(1, n)][0][::-1]
print(functools.reduce(lambda x,y:max(x,y),[gcd(l[i-1]if 0<i else r[i+1],r[i+1]if i<n-1 else l[i-1])for i in range(n)]))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from fractions import gcd
import functools
l=[(hoge.append(gcd(hoge[i-1],a[i])),hoge)[1] for hoge in [[a[0]]] for i in range(1, n)][0]
r=[(hoge.append(gcd(hoge[i-1],a[n-1-i])),hoge)[1] for hoge in [[a[n-1]]] for i in range(1, n)][0][::-1]
print(functools.reduce(lambda x,y:max(x,y),[gcd(l[i-1]if 0<i else r[i+1],r[i+1]if i<n-1 else l[i-1])for i in range(n)]))

Submission status: Accepted

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

def ngcd(li):
    temp=gcd(li[0], li[1])
    if len(li)-3 >=0:
        for i in range(2, len(li)):
            temp=gcd(temp, li[i])
    return temp


n=int(input())
a=[int(i) for i in input().split()]

l=[]
l.append(0)
for i in range(len(a)):
  l.append(gcd(l[i], a[i]))
r=[]
r.append(0)
for i in range(len(a)):
  r.append(gcd(r[i], a[n-i-1]))
#print(l)
#print(r)

ans=[]
for i in range(len(a)):
  ans.append(gcd(l[i], r[n-i-1]))

print(max(ans))

Submission status: Accepted

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

from fractions import gcd

l = [(hoge.append(gcd(hoge[i - 1], a[i])),hoge)[1] for hoge in [[a[0]]]for i in range(1, n)][0]


# l = [a[0]]
# for i in range(1, n):
#     l.append(gcd(l[i - 1], a[i]))
r = [a[n - 1]]
for i in range(1, n):
    r.append(gcd(r[i - 1], a[n - 1 - i]))
r.reverse()
from functools import reduce

print (reduce(lambda x,y:max(x,y),[gcd(l[i-1]if 0<i else r[i+1],r[i+1] if i<n-1 else l[i-1])for i in range(n)]))

Submission status: Accepted

Solution code:
import fractions

gcd = fractions.gcd
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
ryuho = 0

if n == 2:
  print(max(a[0],a[1]))
  exit()

ans = gcd(a[0],a[1])
ryuho = a[2]

if ans < gcd(a[1],a[2]):
  ans = gcd(a[1],a[2])
  ryuho = a[0]

if ans < gcd(a[0],a[2]):
  ans = gcd(a[0],a[2])
  ryuho = a[1]

if n == 3:
  print(ans)
  exit()

for i in range(3,n):
  temp1 = gcd(ans,a[i])
  temp2 = gcd(ans,ryuho)
  if temp1 > temp2:
    ans = temp1
  else:
    ans = temp2
    ryuho = a[i]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))
left = []
l = arr[0]
right = []
r = arr[-1]
ans = 0
left = [0 for _ in range(n)]
right =  [0 for _ in range(n)]

def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x
for i in range(n):
    l = gcd(l,arr[i])
    left[i]= l
    r = gcd(r,arr[-(i+1)])
    right[-(i+1)] = r
for i in range(n):
    if i-1 <0:
        a = arr[-1]
    else:
        a = left[i-1]
    if i+1>n-1:
        b = arr[0]
    else:
        b = right[i+1]
    # print('remove:',i,'Left:',a,'Right:',b)
    ans = max(gcd(a,b),ans)
# print(left)
# print(right)
if n == 2:
    print(max(arr))
else:
    print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
N=int(input())
A=list(map(int,input().split()))

L=[0,0]
for ai in A:
    L.append(gcd(L[-1],ai))
    #print(L)

R=[0,0]
for ai in A[::-1]:
    R.append(gcd(R[-1],ai))
    #print(R)

print(max(gcd(l,r) for l,r in zip(L,reversed(R))))

Submission status: Accepted

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

from fractions import gcd

l = [a[0]]
for i in range(1, n):
    l.append(gcd(l[i - 1], a[i]))
r = [a[n - 1]]
for i in range(1, n):
    r.append(gcd(r[i - 1], a[n - 1 - i]))
r.reverse()
from functools import reduce

print (reduce(lambda x,y:max(x,y),[gcd(l[i-1]if 0<i else r[i+1],r[i+1] if i<n-1 else l[i-1])for i in range(n)]))

Submission status: Accepted

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

from fractions import gcd

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

tr = [a[n - 1]]
for i in range(1, n):
    tr.append(gcd(tr[i - 1], a[n - 1 - i]))
tr.reverse()

ans = 1
for i in range(n):
    tmp = 1
    l = tl[i - 1] if 0 < i else tr[i + 1]
    r = tr[i + 1] if i < n - 1 else tl[i - 1]
    ans = max(ans, gcd(l, r))
print(ans)

Submission status: Accepted

Solution code:
import fractions # for python 3.4.3

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

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(fractions.gcd(gcd_l[i], A[i]))
    gcd_r.append(fractions.gcd(gcd_r[i], A[-(i+1)]))
    #print(gcd_l)
    #print(gcd_r)
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

Submission status: Accepted

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

from fractions import gcd

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

tr = [a[n - 1]]
for i in range(1, n):
    tr.append(gcd(tr[i - 1], a[n - 1 - i]))
tr.reverse()

ans = 1
for i in range(n):
    tmp = 1
    if i == 0: tmp = tr[i + 1]
    elif i == n - 1: tmp = tl[i - 1]
    else: tmp = gcd(tl[i - 1], tr[i + 1])
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [0] + list(map(int, input().split())) + [0]
gcdl, gcdr = [0] + [None] * N + [0], [0] + [None] * N + [0]
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
for i in range(1, N + 1):
    gcdl[i] = gcd(gcdl[i - 1], A[i])
    gcdr[N + 1 - i] = gcd(gcdr[N + 2 - i], A[N + 1 - i])
ans = 1
for i in range(1, N + 1):
    tmp = gcd(gcdl[i - 1], gcdr[i + 1])
    if tmp > ans:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

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

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

L = [0]
R = [0]

for i in range(n):
    L.append(gcd(L[i], A[i]))
    R.append(gcd(R[i], A[n-1-i]))
R.reverse()

result = []

for i in range(n):
    result.append(gcd(L[i], R[i+1])) 

print(max(result))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import fractions
from functools import reduce
N = int(input())
A = [int(i) for i in input().split()]



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

for j in reversed(range(N-1)):
    R[j] = fractions.gcd(A[j],R[j+1])

L.append(0)
L.insert(0,0)
R.append(0)
R.insert(0,0)

ans = 1
for i in range(N):
    # print(L[i],R[i+2])
    ans = max(ans,fractions.gcd(L[i],R[i+2]))

print(ans)







"""
嘘解法
def gcd(nums):
    return reduce(fractions.gcd,nums)

ans = 1
A.sort()
gcd1 = gcd(A)
for i in range(N):
    A[i] //= gcd1

ans *= gcd1

gcd2 = A[0]
for i in range(1,N):
    gcd2 = fractions.gcd(gcd2,A[i])
    if gcd2 == 1:
        key = i
        break

a = copy.deepcopy(A)
a.remove(A[0])
b = copy.deepcopy(A)
b.remove(A[key])

ans *= max(gcd(a),gcd(b))
print(ans)
"""

Submission status: Accepted

Solution code:
import sys,fractions
input=sys.stdin.readline
N=int(input())
num = list(map(int,input().split()))
g = fractions.gcd
left=[0]*(N+1)
right=[0]*(N+1)
for i in range(N):
  j = N-i-1#初期値=4
  left[i+1] = g(left[i],num[i])
  right[j] = g(right[j+1],num[j])
ans=0
for k in range(N):
  ans = max(ans,g(left[k],right[k+1]))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n==2:
    print(max(a[0],a[1]))
    exit()
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
gl = [0]*n
gl[0] = a[0]
gr = [0]*n
gr[-1] = a[-1]

for i in range(1,n):
    gl[i] = gcd(max(gl[i-1],a[i]),min(gl[i-1],a[i]))
for i in range(n-2,-1,-1):
    gr[i] = gcd(max(gr[i+1],a[i]),min(gr[i+1],a[i]))
ans = max(gr[1],gl[-2])
for i in range(1,n-1):
    g = gcd(max(gl[i-1],gr[i+1]),min(gl[i-1],gr[i+1]))
    ans = max(ans,g)
print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
 
N = int(input())
A = list(map(int, input().split()))

L = [0, 0]
for ai in A:
    L.append(gcd(L[-1], ai))

R = [0, 0]
for ai in A[::-1]:
    R.append(gcd(R[-1], ai))
 
print(max(gcd(l, r) for l, r in zip(L, reversed(R))))

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
A = read_ints()

from fractions import gcd
# 累積GCDを使って解く
# 累積の概念は広く使えるxor,min,max,積等...
# 差ではなく左右から挟み込んで演算という概念をしっかりと身につけよう

left = []
right = []
tmp_fo = 0
tmp_re = 0
for fo, re in zip(A, A[::-1]):
    tmp_fo = gcd(tmp_fo, fo)
    tmp_re = gcd(tmp_re, re)
    left.append(tmp_fo)
    right.append(tmp_re)

right = right[::-1]

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

ans = max(ans, right[1], left[-2])

print(ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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


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

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

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

ans = max([gcd(x, y) for x, y in zip(L, R[1:])])
print(ans)

Submission status: Accepted

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

def factorize(x):
    """xの素因数分解を表す辞書 {素因数: 指数}"""
    f = {}
    d = 2
    while x > 1:
        c = 0
        while x % d == 0:
            c += 1
            x //= d
        if c > 0:
            f[d] = c
        d += 1 if d == 2 else 2
        if d * d > x > d:
            f[x] = 1
            break
    return f

def factorizeWithSet(x, D):
    f = {}
    for d in D:
        c = 0
        while x % d == 0:
            c += 1
            x //= d
        if c > 0:
            f[d] = c
    return f

def dropmin(ls):
    """[min(ls[:i] + ls[i + 1:]) for i in range(len(ls))]"""
    # l = [min(ls[:i]) for i in range(len(ls))]
    l = [float('inf')] * N
    for i in range(1, N):
        l[i] = min(l[i - 1], ls[i - 1])
    # r = [min(ls[i + 1:]) for i in range(len(ls))]
    r = [float('inf')] * N
    for i in range(N - 2, -1, -1):
        r[i] = min(r[i + 1], ls[i + 1])
    return [min(a, b) for a, b in zip(l, r)]

def prod(ls):
    p = 1
    for x in ls:
        p *= x
    return p

# 各A_iの素因数
A = list(A)
F = [factorize(a) for a in A[:2]]

# 素因数の集合 (2要素に出現しない素因数は無視)
D =  set(F[0].keys())
D.update(F[1].keys())

E = set()
for d in D:
    c = 0
    for a in A:
        if a % d != 0:
            c += 1
            if c >= 2:
                E.add(d)
                break
D -= E

F = [factorizeWithSet(a, D) for a in A]

# Dの要素 d -> i -> dがA_iに含まれる個数
X = {d: [f[d] if d in f else 0 for f in F] for d in D}

# Dの要素 d → A_iを削除したときのdの個数の最小値のリスト
X = {d: dropmin(X[d]) for d in D}

S = [prod(d ** X[d][i] for d in D) for i in range(N)]
print(max(S))

Submission status: Accepted

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

def gcd(m, n):
  x = max(m, n)
  y = min(m, n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x % y
      x = y
      y = z
    else:
      return z

L, R = {}, {}
for i in range(N):
  if i == 0:
    L[0] = A[0]
    R[N-(i+1)] = A[N-(i+1)]
  else:
    L[i] = gcd(L[i-1], A[i])
    R[N-(i+1)] = gcd(R[N-i], A[N-(i+1)])

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a_l =[int(i) for i in input().split()]

left=[0]
right=[0]

for i in range(1,n+1):
    left.append(gcd(left[i-1],a_l[i-1]))
    right.append(gcd(right[i-1],a_l[n-i]))
right=right[::-1]

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

Submission status: Accepted

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

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

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

right_gcd = [A[N-1]]
b = A[N-1]
for k in range(N-2, 0, -1):
  b = gcd(b, A[k])
  right_gcd.append(b)

ans_gcd = [right_gcd[N-2], left_gcd[N-2]]

for p in range(N-2):
  ans_gcd.append(gcd(left_gcd[p], right_gcd[N-p-3]))

print(max(ans_gcd))

Submission status: Accepted

Solution code:
from fractions import gcd

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

L = [0]
R = [0]
for i in range(n):
  #左からの累積
  L.append(gcd(L[i],a[i]))
  #右からの累積
  R.append(gcd(R[i],a[-(i+1)]))

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=LIST()

# 予め左右から累積GCDを取っておく
L=[0]*(N+2)
for i in range(N):
    L[i+1]=gcd(L[i], A[i])
R=[0]*(N+2)
for i in range(N-1, -1, -1):
    R[i+1]=gcd(R[i+2], A[i])

# 1箇所除いてどうなるかを全部試しても、各回GCD1回ずつで済む
ans=0
for i in range(N):
    ans=max(ans, gcd(L[i], R[i+2]))
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)
 
N = (int(input()))
A = [int(i) for i in input().split()]

A1 = [0] * (N)
A2 = [0] * (N)
A3 = [0] * (N)
A1[0] = A[0]
A2[N-1] = A[N-1]

for i in range(N):
  if i==0 : continue
  A1[i] = gcd(A1[i-1],A[i])
  A2[N-1-i] = gcd(A2[N-i],A[N-1-i])
  
for i in range(N):
  if i==0 : A3[i] = A2[i+1] ; continue
  if i==N-1 : A3[i] = A1[i-1] ; continue
  A3[i] = gcd(A1[i-1],A2[i+1])

print(max(A3))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import itertools
try:
    from math import gcd
except ImportError:
    from fractions import gcd


class Cumulative(object):

    def __init__(self, seq, op):
        self.cumul_array = [0]
        self.cumul_array.extend(itertools.accumulate(seq, op))


def solve(n, xs):
    left_cumul = Cumulative(xs, gcd)
    right_cumul = Cumulative(reversed(xs), gcd)
    res = 1
    for i in range(n):
        left_gcd = left_cumul.cumul_array[i]
        right_gcd = right_cumul.cumul_array[n - i - 1]
        cand = gcd(left_gcd, right_gcd)
        if cand > res:
            res = cand
    return res


def main():
    n = int(input())
    xs = [int(x) for x in input().split()]
    res = solve(n, xs)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def gcd(x, y):
	if y == 0:
		return x
	r = x % y
	while r != 0:
		x = y
		y = r
		r = x % y
	return y

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

l = [0] * (n + 2)
r = [0] * (n + 2)

for i in range(1, n + 1):
	l[i] = gcd(l[i - 1], a[i - 1])

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

ans = 1
for i in range(1, n + 1):
	ans = max(ans, gcd(l[i - 1], r[i + 1]))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
d1 = []
d2 = []
d1.append(a[0])
d2.append(a[-1])

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


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

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

d2 = d2[::-1]
d1 = [0] + d1
d2.append(0)
num = 0
for i in range(n):
    num = max(num, gcd(d1[i], d2[i]))
print(num)

Submission status: Accepted

Solution code:
from fractions import *
n = int(input())
a = [0]+list(map(int, input().split()))+[0]
b = [0]*(n+2)
c = [0]*(n+2)
for i in range(1, n+1):
	b[i] = gcd(b[i-1], a[i])
for i in range(n, 0, -1):
	c[i] = gcd(c[i+1], a[i])

ans=1
for i in range(1, n+1):
    x1 = b[i-1]
    x2 = c[i+1]
    ans=max(ans, gcd(x1, x2))

print(ans)