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:
def GCD(x, y): 
    while(y): 
       x, y = y, x % y 
    return x

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

left[0] = a[0]
for i in range(1,n):
    left[i] = GCD(left[i-1], a[i])

right[-1] = a[-1]
for i in range(2,n+1):
    right[-i] = GCD(right[-i+1], a[-i])

max_gcd = 0
for i in range(n):
    if i == 0 and max_gcd < right[1]:
        max_gcd = right[1]
    elif i == n-1 and max_gcd < left[n-2]:
        max_gcd = left[n-2]
    if i >= 1 and i <= n-2 and max_gcd < GCD( left[i-1], right[i+1]):
        max_gcd = GCD( left[i-1], right[i+1])

print(max_gcd)

Submission status: Accepted

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

def gcd(x,y):
    if x < y:
        _ = x
        x = y
        y = _
    return gcd_(x,y)

N = int(input())
AList = list(map(int,input().split()))
Lgcd = [0] * N 
Rgcd = [0] * N

for i in range(N):
    if i == 0:
        Lgcd[i] = AList[i]
    else:
        Lgcd[i] = gcd(Lgcd[i-1],AList[i])
        
for i in range(N):
    j = N-1-i
    if i == 0:
        Rgcd[j] = AList[j]
    else:
        Rgcd[j] = gcd(Rgcd[j+1],AList[j])

max1 = 0
for i in range(N):
    if i == 0:
        gcd1 = Rgcd[1]
    elif i == N-1:
        gcd1 = Lgcd[N-2]
    else:
        gcd1 = gcd(Lgcd[i-1], Rgcd[i+1])
    if max1 < gcd1:
        max1 = gcd1

print(max1)

Submission status: Accepted

Solution code:
import fractions
N=int(input())
A=list(map(int,input().split()))
ans=0  #更新用
#端っこの処理用
l=[0]*(N+1)
r=[0]*(N+1)
for i in range(N):
  l[i+1]=(fractions.gcd(l[i],A[i]))
  r[N-i-1]=(fractions.gcd(r[N-i],A[N-1-i]))
for j in range(N):
  ans=max(ans,fractions.gcd(l[j],r[j+1]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

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

gcd_L = [0] + list(accumulate(L, gcd))
gcd_R = list(accumulate(L[::-1], gcd))[::-1] + [0]


# [0,1,2,3,4]
# [4,3,2,1,0]
# N = 4
m_gcd = 0

for i in range( N):
	m_gcd = max(m_gcd, gcd(gcd_L[i], gcd_R[i + 1]))
print(m_gcd)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
L=[0]
R=[0]
def gcd(x,y):
    if x==0:return y
    else:return gcd(y%x,x)
for i in range(n-1):
    L.append(gcd(L[i],a[i]))
    R.append(gcd(R[i],a[-1-i]))
MAX=0
for i in range(n):
    MAX=max(MAX,gcd(L[i],R[-1-i]))
print(MAX)

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
  tem = x%y
  ans = y
  while tem != 0:
    yn = tem
    tem = y%yn
    if tem == 0:
      ans = yn
      break
    y = yn
  return ans
  
ansl = []
L = [0]*(n-1)
R = [0]*(n-1)

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

R[n-2] = A[n-1]
for i in range(n-3,-1,-1):
  R[i] = gcd(R[i+1],A[i+1])
  
for i in range(n):
  if i == 0:
    ansl.append(R[i])
  elif i == n-1:
    ansl.append(L[i-1])
  else:
    ansl.append(gcd(L[i-1],R[i]))

print(max(ansl))

Submission status: Accepted

Solution code:
import fractions

n=int(input())
a=list(map(int, input().split()))
ans=[0]*n
left=[0]*n
right=[0]*n
max_=0

for i in range(n):
  if i==0:
    left[i]=a[0]
  else:
    left[i]=fractions.gcd(left[i-1],a[i])
for i in range(n-1,-1,-1):
  if i==n-1:
    right[i]=a[n-1]
  else:
    right[i]=fractions.gcd(right[i+1],a[i])
for i in range(n):
  if i==0:
    ans=right[1]
  elif i==n-1:
    ans=left[n-2]
  else:
    ans=fractions.gcd(left[i-1],right[i+1])
  if ans>max_:
    max_=ans
    
print(max_)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Atcoder forces me to use fractions.gcd instead of math.gec because the contest accepts only python 3.4

import fractions
from functools import reduce


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


N = int(input())
A = list(map(int, input().split()))
A_set = list(set(A))
A_lib = {}
for a in A:
    if a in A_lib:
        A_lib[a] += 1
    else:
        A_lib[a] = 1

if len(A_set) == 1:
    ans = A_set[0]
else:
    ans = gcd_list(A_set)
    for i in range(len(A_set)):
        if A_lib[A_set[i]] == 1:
            ans = max(ans, gcd_list(A_set[:i] + A_set[i + 1:]))

print(ans)

Submission status: Accepted

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

rl = [0] * n
for i in range(n):
    rl[i] = fractions.gcd(L[i], R[i + 1])
print(max(rl))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

m = [0] * N
for i in range(N):
  m[i] = fractions.gcd(m1[i], m2[i + 1])

print(max(m))

Submission status: Accepted

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

import fractions
import copy
from functools import reduce

#最大公約数を求める関数
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

l = []
sorted_A = sorted(A)
ind = 0
for i in range(1, len(A)):
    if gcd_list([sorted_A[0], sorted_A[i]]) == 1:
        ind = i
        break
if ind == 0:
    ind = 1
for i in [0,ind]:
    sorted_A = sorted(A)
    del sorted_A[i]
    l.append(gcd_list(sorted_A))

print(max(l))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

m1 = [0] * (n + 1)
m2 = [0] * (n + 1)
for i in range(1, n + 1):
  m1[i] = fractions.gcd(m1[i - 1], a[i - 1])
  m2[n - i] = fractions.gcd(m2[n - i + 1], a[n - i])

m = [0] * n
for i in range(n):
  m[i] = fractions.gcd(m1[i], m2[i + 1])

print(max(m))

Submission status: Accepted

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
f = [0] * n
r = [0] * n
for i in range(n):
    if i == 0:
        f[i] = a[i]
        r[-i-1] = a[-i-1]
    else:
        f[i] = fractions.gcd(f[i-1], a[i])
        r[-i-1] = fractions.gcd(r[-i], a[-i-1])
f.insert(0, 0)
r.append(0)
ans = 0
for i in range(len(f) - 1):
    ans = max(ans, fractions.gcd(f[i], r[i+1]))
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a < b:
        a,b = b,a
    if b == 0:
        return a
    if a%b == 0:
        return b
    return gcd(b, a%b)
N = int(input())
a = list(map(int,input().split()))
g1=[0 for i in range(N)]
g2=[0 for i in range(N)]
g1[0]=a[0]
g2[N-1]=a[N-1]
for i in range(1,N):
  g1[i]=gcd(g1[i-1],a[i])
for i in range(N-2,-1,-1):
  g2[i]=gcd(g2[i+1],a[i])
ans=1
for i in range(N-2):
  a=gcd(g1[i],g2[i+2])
  ans=max(ans,a)
ans=max(ans,g1[N-2],g2[1])
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
a = list(map(int, input().split()))
l = [0] * N
r = [0] * N
m = [0] * N

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

for j in reversed(range(N)):
  if j == N - 1:
    r[j] = 0
  else:
    r[j] = gcd(r[j+1], a[j+1])
    
for k in range(N):
#  print(r[k], l[k])
  m[k] = gcd(r[k], l[k])
  
print(max(m))

Submission status: Accepted

Solution code:
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))

def gcd(x, y):
    return gcd(y, x % y) if y else x

n = getint()
a = getints()

lo = [0] * n
hi = [0] * n
lo[0] = a[0]
hi[n-1]=a[n-1]
for i in range(1, n):
    lo[i] = gcd(lo[i-1], a[i])

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

mx=0
for i in range(0,n):
    c1 = lo[i-1] if i >= 1  else hi[1]
    c2 = hi[i+1] if i < n-1 else lo[n-2]
    mx=max(mx, gcd(c1,c2))


print(mx)

Submission status: Accepted

Solution code:
import fractions

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

left=[0 for i in range(n)]
right=[0 for i in range(n)]
left[0] = a[0]
right[-1] = a[-1]
for i in range(n-2):
    left[i+1] = fractions.gcd(left[i],a[i+1])
    right[-i-2] = fractions.gcd(right[-i-1],a[-i-2])

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

print(max(gcds))

Submission status: Accepted

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

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

right_gcd = [0]*(n)
left_gcd = [0]*(n)
right_gcd[n-1] = a[n-1]
left_gcd[0] = a[0]

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

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

except_gcd = [0]*n
for i in range(n):
    if i == 0:
        except_gcd[i] = right_gcd[1]
    elif i == n-1:
        except_gcd[i] = left_gcd[n-2]
    else:
        except_gcd[i] = gcd(left_gcd[i-1],right_gcd[i+1])

print(max(except_gcd))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = [0] + list(map(int, input().split()))

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

    return b

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

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

ret = []
for i in range(1, N+1):
    ret.append(gcd(L[i], R[i+1]))

print(max(ret))

Submission status: Accepted

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


def gcd(a, b):
    if a > b:
        a, b = b, a

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


L = [0 for _ in range(N + 2)]
R = [0 for _ in range(N + 2)]

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

# print(L)
# print(R)

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

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy
from array import array

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

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

def get_prefix_gcd_list(Adeque):
    prefix_gcd = array('i', [0]*N)
    # marker
    prefix_gcd[0] = 0
    # the first itself is gcd
    prefix_gcd[1] = Adeque.popleft()
    for i in range(2,N):
        a = Adeque.popleft()
        prefix_gcd[i] = gcd(prefix_gcd[i-1], a)
        pass
    return prefix_gcd
        
    
# PREFIX_GCD[i]...i より前の要素のGCD
PREFIX_GCD = get_prefix_gcd_list(deque(copy(A)))

# PREFIX_GCD[i]...i より後の要素のGCD
POSTFIX_GCD=list(reversed(get_prefix_gcd_list(deque(reversed(A)))))

gcd_max=1

for i in range(N):
    pre = PREFIX_GCD[i]
    pos = POSTFIX_GCD[i]
    if pre == 0:
        _gcd = pos
    elif pos == 0:
        _gcd = pre
    else:
        _gcd = gcd(pre,pos)
    gcd_max = max(gcd_max, _gcd)
        
print(gcd_max)

Submission status: Accepted

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

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

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

m = []
for i in range(n):
    m.append(gcd(m_r[i], m_l[-i-1]))
print(max(m))

Submission status: Accepted

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

def GCD(a: int, b: int) -> int:
    return a if b == 0 else 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 = r[::-1]

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

print(ans)

Submission status: Accepted

Solution code:
#nn
from fractions import gcd 
n = int(input())
a = list(map(int, input().split()))
ans = 1
left = [0]
right = [0]

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

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

Submission status: Accepted

Solution code:
import fractions

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

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

r_gcd = [0]
for i in range(n):
    r_gcd.append(fractions.gcd(r_gcd[-1], a[-(i+1)]))
r_gcd.reverse()
# print(r_gcd)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import functools
# from math import gcd
from fractions import gcd

# def gcd(x,y):
#     if x<y:
#         x,y=y,x
#     #x>y
#     if y==0:
#         return x
#     if x%y==0:
#         return y
#     else:
#         return gcd(y,x%y)
 
def solve(N: int, A: "List[int]"):
    L = [0] * (N)
    R = [0] * (N)
 
    for i in range(1, N):
        L[i] = gcd(L[i-1], A[i-1])
    for i in reversed(range(0,N-1)):
        R[i] = gcd(R[i+1], A[i+1])
 
    # print(L)
    # print(R)
 
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(L[i], R[i]))
 
    print(ans)
 
    return
 
 
# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import functools
# from math import gcd
# from fractions import gcd

def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
 
def solve(N: int, A: "List[int]"):
    L = [0] * (N)
    R = [0] * (N)
 
    for i in range(1, N):
        L[i] = gcd(L[i-1], A[i-1])
    for i in reversed(range(0,N-1)):
        R[i] = gcd(R[i+1], A[i+1])
 
    # print(L)
    # print(R)
 
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(L[i], R[i]))
 
    print(ans)
 
    return
 
 
# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

else:
        l=[a[0]]
        r=[a[n-1]]
        for i in range(1,n):
                l.append(fractions.gcd(l[-1],a[i-1]))
        for i in range(n-1,0,-1):
                        r.append(fractions.gcd(r[-1],a[i]))
        r=r[::-1]
        l[0]=r[0]
        r[n-1]=l[n-1]
        ans=0
        for k in range(n):
                g=fractions.gcd(l[k],r[k])
                if g>=ans:
                        ans=g
        print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import numpy as np
n = int(input())
a = list(map(int, input().split()))
l = np.zeros(n)
r = np.zeros(n+1)
r[n] = 0
for i in range(n):
    if i == 0:
        l[0] = 0
    else:
        l[i] = gcd(l[i-1],a[i-1])
for j in range(n-1, -1, -1):
        r[j] = gcd(r[j+1],a[j])
m = 0
for i in range(n):
    m = max(gcd(l[i],r[i+1]),m)
print(int(m))

Submission status: Accepted

Solution code:
import math
N = int(input())
a_ls = [int(i) for i in input().split()]


def gcd(ls):
    ls = [i for i in ls if i > 0]
    while True:
        _min = min(ls)
        ls = [i % _min for i in ls if i % _min != 0]
        if len(ls) == 0:
            return _min
        ls.append(_min)

l_ls = [0]
r_ls = [0]
for i in range(N):
    l_ls.append(gcd([l_ls[i], a_ls[i]]))
    r_ls.append(gcd([r_ls[i], a_ls[-i-1]]))
r_ls = r_ls[::-1]
sum_ls = [gcd([l_ls[i], r_ls[i+1]]) for i in range(N)]
print(max(sum_ls))

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('- {} -> {}'.format(name, val), file=sys.stderr)
            return None
"""
書き換えたあとの最大公約数の最大値を求める
書き換える値の最適解は、最小値を最大値に書き換えること
例えば、1,6,3があるとき、1を3に書き換えることで最大公約数が3になる
しかし、7 6 8の場合、最小の6ではなく7を書き換えることが最適となる
結局全部の数について書き換えたときの最大値を求めるしか無いか
そうするとO(N**2)になってしまう
全体の最大公約数はgcd(gcd(gcd(1,2), 3),4)
1つ書き換えるは、消すと同義
逆でやる？
全部のgcdを求めて、そこから途中結果を保存しておく
7 6 8 なら
None 1 1と
None 2 1
Noneと2なので2

"""
def main(N, A):
    tmp = A[0]
    tmp_list = [A[-1], A[0]]

    for i in range(N-1):
        tmp = fractions.gcd(tmp, A[i+1])
        tmp_list.append(tmp)

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

    debug(tmp_list, locals())
    debug(reversed_tmp_list, locals())

    answers = []
    for i in range(N):
        #  if i == 0:
        #      answers.append(reversed_tmp_list[-(i+2)])
        #      continue
        #  if i == N - 2:
        #      answers.append(tmp_list[i])
            #  continue
        tmp = fractions.gcd(tmp_list[i], reversed_tmp_list[-(i+2)])
        answers.append(tmp)
    debug(answers, locals())
    return max(answers)


if __name__ == "__main__":
    if 'LOCAL' in os.environ:
        values = [
                [
                    4,
                    [2, 4, 6, 8],
                    2
                    ],
                [
                    2,
                    [100000, 100000],
                    100000
                    ],
                [
                    3,
                    [12, 6, 12],
                    12
                    ],
                [2, [1, 1000000], 1000000],
                [2, [1, 1], 1],

                [8, list(map(int, '746130 1385670 4849845 881790 3233230 1939938 570570 510510'.split())), 19]
                ]
        for i in values:
            print('A', i[1])
            res = main(i[0], i[1])
            print('res: {res}, exp: {exp}'.format(res=res, exp=i[2]))
            assert res == i[2]
    else:
        N = _I()
        A = LI()
        print(main(N, A))

Submission status: Accepted

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

Submission status: Accepted

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

import fractions as frc

y=[0]*n
z=[0]*n

cd=x[0]
for i in range(n):
	cd=frc.gcd(cd,x[i])
	y[i]=cd

#print(y)

cd=x[n-1]
for i in range(n-1,-1,-1):
	cd=frc.gcd(cd,x[i])
	z[i]=cd

#print(z)

res=[0]*n
for i in range(n):
	if i==0:
		res[0]=z[1]
	else:
		if i==n-1:
			res[n-1]=y[n-2]
		else:
			res[i]=frc.gcd(y[i-1],z[i+1])

#print(res)

print(max(res))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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] = (fractions.gcd(left[i],a[i]))
    right[n-i-1] = (fractions.gcd(right[n-i],a[n-i-1]))

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

Submission status: Accepted

Solution code:
#-*- using:utf-8 -*-
def euclidean(a,b):
    if b == 0:
        return a
    else:
        return  euclidean(b,a%b)

def gcd(a,b):
#    print("gcd %d %d" %(a,b))
    n = 0
    if a == b:
        return a
    elif a > b:
        n = euclidean(a,b)

    elif a < b:
        n = euclidean(b,a)

    else:
        pass

    return n

def blackboard(n,a):
    candidate = 0
    maxnum = 0
    b = list(map(int,a))

    left = [0] * (n+1)
    right = [0] * (n+1)
    for i in range(n):
        left[i+1] = gcd(left[i],b[i])
        right[i+1] = gcd(right[i],b[n - i -1])

    for i in range(n):
        candidate = gcd(left[i],right[n-i-1])
        if candidate > maxnum:
            maxnum = candidate

    return maxnum


if __name__ == '__main__':
    n = raw_input()
    a = raw_input().split()
    m = int(n)
    print("%d" %(blackboard(m,a)))

Submission status: Accepted

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

A.sort()
yakusu_0 = []
i = 1
while i <= A[0]**0.5:
	if A[0] % i == 0:
		yakusu_0.append(i)
		yakusu_0.append(A[0]//i)
	i += 1

one = set()
yakusu_0.sort()
max_y = 1
for j in range(len(yakusu_0)-1, -1, -1):
	num = 0
	for i in A:
		if i % yakusu_0[j] != 0:
			num += 1
		if num >= 2:
			break
	if num <= 1:
		max_y = yakusu_0[j]
		break

A = A[1:]
yakusu_0 = []
i = 1
while i <= A[0]**0.5:
	if A[0] % i == 0:
		yakusu_0.append(i)
		yakusu_0.append(A[0]//i)
	i += 1

one = set()
yakusu_0.sort()
max_z = 1
for j in range(len(yakusu_0)-1, -1, -1):
	num = 0
	for i in A:
		if i % yakusu_0[j] != 0:
			num += 1
			break
	if num == 0:
		max_z = yakusu_0[j]
		break

print(max(max_y, max_z))

Submission status: Accepted

Solution code:
# 2019/07/31

from fractions import gcd

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

g1=[0]*n
g2=[0]*n
g1[0]=a[0]
g2[-1]=a[-1]


i=1
j=n-2
while i<n and j>-1:
    g1[i]=gcd(g1[i-1],a[i])
    g2[j]=gcd(g2[j+1],a[j])
    i+=1;j-=1

ans=[0]*n
ans[0]=g2[1]
ans[-1]=g1[-2]

for i in range(1,n-1):
    ans[i]=gcd(g2[i+1],g1[i-1])

print(max(ans))

Submission status: Accepted

Solution code:
import fractions
import itertools
import collections

n = int(input().split()[0])
a_list = list(map(int, input().split()))
sorted_list = sorted(a_list)
min_a, second_min_a = sorted_list[0], sorted_list[1]

def koyakusu(x):
    i = 1
    koyaku_list = []
    while i * i <= x:
        if x % i == 0:
            koyaku_list.append(i)
            koyaku_list.append(x//i)
        i += 1

    koyaku_list = list(set(koyaku_list))
    return koyaku_list

kouho_list = []
# print('{}: {}'.format(min_a, koyakusu(min_a)))
kouho_list += koyakusu(min_a)

# print('{}: {}'.format(second_min_a, koyakusu(second_min_a)))
kouho_list += koyakusu(second_min_a)
kouho_list = list(set(kouho_list))
# print(kouho_list)
ans_kouho_list = []

for kouho in kouho_list:
    x_list = [x for x in a_list if x % kouho == 0]
    # print('kouho {} ({})'.format(kouho, len(x_list)))
    if len(x_list) >= n-1:
        ans_kouho_list.append(kouho)
# print(ans_kouho_list)
ans = max(ans_kouho_list)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from fractions import gcd
n=int(input())
a=list(map(int,input().split()));g=a[-1]
b=deque([a[0]])
for num in reversed(a[1:]):
	g=gcd(g,num)
	b.appendleft(g)
m=b[0];gg=a[0]
for i,j in enumerate(a[:n-1]):
	gg=gcd(gg,j)
	m=max(m,gcd(gg,b[i+1]))
print(m)

Submission status: Accepted

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

def GCD(x,y):
    while y != 0:
        x,y = y,x%y
    return x

l,r = [0],[0]
for i in range(N-1):
    l.append(GCD(l[-1],A[i]))
    r.append(GCD(r[-1],A[N-i-1]))

ans = 0
for i in range(N):
    ans = max(ans,GCD(l[i],r[N-i-1]))
print(ans)

Submission status: Accepted

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


def gcd(x,y):
    m1 = min(x,y)
    m2 = max(x,y)
    if m1 == 0:
        return m2
    else:
        return gcd(m2%m1,m1)

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

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

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
def calcgcd(a, b):
  if a > b:
    a, b = b, a
  while a > 0:
    a, b = b%a, a
  return b
gcdsl = [0]*(N+1)
for i in range(N):
  a = gcdsl[i]
  b = As[i]
  gcdsl[i+1] = calcgcd(a, b)
#print(gcdsl)
gcdsr = [0]*(N+1)
for i in reversed(range(N)):
  a = gcdsr[i+1]
  b = As[i]
  gcdsr[i] = calcgcd(a, b)
#print(gcdsr)
gcds = [0]*N
for i in range(N):
  a = gcdsl[i]
  b = gcdsr[i+1]
  gcds[i] = calcgcd(a, b)
#print(gcds)
print(max(gcds))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0 for i in range (n+2)]
c=[0 for i in range (n+2)]
i=1
def g(a,b):
	if(b==0):
		return a
	else:
		return g(b,a%b)
while(i<=n):
	b[i]=g(b[i-1],a[i-1])
	c[n+1-i]=g(c[n+2-i],a[n+1-i-1])
	i+=1

i=1
d=[]
while(i<=n):
	d.append(g(b[i-1],c[i+1]))
	i+=1
d.sort()
print(d[n-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, t = LI()
    print(b * (t // a))
    return

#B
def B():
    n = II()
    v = LI()
    c = LI()
    ans = 0
    for i in range(n):
        if v[i] > c[i]:
            ans += v[i] - c[i]
    print(ans)
    return

#C
def C():
    def gcd(a, b):
        if b > a: a, b = b, a
        while b:
            a, b = b, a % b
        return a
    n = II()
    a = LI()
    dp1 = [None] * (n - 1)
    dp1[0] = a[0]
    dp2 = [None] * (n - 1)
    dp2[-1] = a[-1]
    for i in range(1, n - 1):
        dp1[i] = gcd(dp1[i - 1], a[i])
        dp2[-i - 1] = gcd(dp2[-i], a[-i - 1])
    ans = 0
    dp1.insert(0, dp2[0])
    dp2.append(dp1[-1])
    for i in range(n):
        ans = max(ans, gcd(dp1[i], dp2[i]))
    print(ans)
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd

def solve(N: int, A: "List[int]"):
    L = [A[0]]
    R = [A[-1]]
    for i in range(1, N):
        L.append(gcd(L[-1], A[i]))
        R.append(gcd(R[-1], A[N-1-i]))
    mx = 0
    for i in range(N):
        if i == 0:
            m = R[N-2]
        elif i == N-1:
            m = L[N-2]
        else:
            m = gcd(L[i-1], R[N-i-2])
        if mx < m:
            mx = m
    print(mx)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()