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:
# -*- coding: utf-8 -*-

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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def gcd_list(nums): return reduce(gcd, nums, nums[0])
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()

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

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

Submission status: Accepted

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

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

res = []
l_gcd = [0]*(n+2)
r_gcd = [0]*(n+2)
for i in range(n+1):
    if i ==0:
        l_gcd[i] = 0
        r_gcd[n-i+1] = 0
        continue
    l_gcd[i] = gcd(l_gcd[i-1], a_list[i-1])
    r_gcd[n-i] = gcd(r_gcd[n-i+1], a_list[n-i])

for i in range(n+1):
    res.append(gcd(l_gcd[i],r_gcd[i+1]))

print(max(res))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce


def main():

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

    gcds_r = [1] * N
    gcds_r[0] = A[0]
    for n in range(1, N):
        gcds_r[n] = fractions.gcd(gcds_r[n-1], A[n])

    gcds_l = [1] * N
    gcds_l[-1] = A[-1]
    for n in range(N-1)[::-1]:
        gcds_l[n] = fractions.gcd(gcds_l[n+1], A[n])

    max_gcd = 1
    for n in range(1, N-1):
        max_gcd = max(max_gcd, fractions.gcd(gcds_r[n-1], gcds_l[n+1]))

    max_gcd = max(max_gcd, gcds_l[1], gcds_r[N-2])

    print(max_gcd)  


main()

Submission status: Accepted

Solution code:
"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数

A1 , A2 , A3 ... An

gcd(A1 , A2 , A3 ... An-1) * N
= gcd * N * N
= gcd * N^2

gcd(A1 , A2 , A3 ... An-1)
gcd(A1 , A2 , A3 ... An-2 , An) = gcd(A1 , A2 , A3 ... An-2) , An
"""
def gcd(a, b):  # a>b
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

from functools import reduce
def GCD(numbers):
    if len(numbers) == 0 : return 0
    if len(numbers) == 1 : return numbers[0]
    if len(numbers) == 2 : 
        return gcd(numbers[0] , numbers[1])
    else : 
        value = GCD(numbers[:len(numbers)-1])
        result = gcd(value , numbers[len(numbers) - 1])
        return result

def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    R = [0 for i in range(N - 1)]
    L = [0 for i in range(N - 1)]
    R[0] = a_list[0]
    L[0] = a_list[-1]

    for i in range(1 , N-1) : 
        R[i] = gcd(R[i - 1] , a_list[i])
    
    for j in range(1 , N-1) : 
        L[j] = gcd(L[j - 1] , a_list[- j - 1])
    
    maxValue = 0
    for i in range(N - 2) : 
        value = gcd(R[i] , L[N - i - 3])
        if value > maxValue : maxValue = value
    print(max(maxValue , R[-1] , L[-1]))
main()

Submission status: Accepted

Solution code:
from collections import deque
def gcm(a, b):
  if a < b:
    a = a+b
    b=a-b
    a = a-b
  if b == 0:
    return a
  else:
    r = a%b
    return b if r == 0 else gcm(b, r)
N = int(input())
A = list(map(int, input().split()))
L = deque([0])
for i in range(1, N):
  L.append(gcm(L[-1],A[i-1]))
R = deque([0])
for i in reversed(range(N-1)):
  R.appendleft(gcm(R[0],A[i+1]))
ans = 0
for i in range(N):
  ans = max(ans, gcm(L[i],R[i]))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import fractions

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
# インデックスを直感で使えるように先頭にダミーを入れる
A = [0] + A

"""
L(i) := A_1, A_2, ..., A_i-1 の最大公約数
R(i) := A_i, A_i+1, ..., A_N の最大公約数
Aiを書き換えることにした場合の最大公約数をM_iとすると
M_i = gcd(L(i), R(i+1))

ただし L(0)=0, R(N+1)=0
"""

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

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


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

M = []

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

print(max(M))

Submission status: Accepted

Solution code:
N = int(input())
al = [int(a) for a in input().split()]
      
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

l = [0]*N
r = [0]*N

# 左から右
for i in range(N-1):
    if i == 0:
        a = al[i]
        l[i+1] = a
    if i >= 1:
        a = gcd(a, al[i])
        l[i+1] = a

# 右から左
for i in range(N-1):
    if i == 0:
        a = al[-i-1]
        r[-i-2] = a
    if i >= 1:
        a = gcd(a, al[-i-1])
        r[-i-2] = a

# 最大公約数リスト
ansl = [0]*N
for i in range(N):
    if i == 0:
        ansl[i] = r[i]
    elif i == N-1:
        ansl[i] = l[i]
    else:
        ansl[i] = gcd(r[i], l[i])
print(max(ansl))

Submission status: Accepted

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

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 range(n-1, -1, -1):
    r[i] = gcd(r[i+1],a[i])

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

Submission status: Accepted

Solution code:

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


import sys
if n == 2:
    print(max(a))
    sys.exit()


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


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

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

max_gcd = gcd_right[n-2]
for i in range(1, n-1):
    max_gcd = max(max_gcd, gcd(gcd_left[i-1], gcd_right[n - 2 - i]))
max_gcd = max(max_gcd, gcd_left[n-2])

print(max_gcd)

Submission status: Accepted

Solution code:
import fractions

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

L = [0]
R = [0]

gl = 0
gr = 0
for i in range(N):
    gl = fractions.gcd(gl,l[i])
    L.append(gl)
    gr = fractions.gcd(gr,l[N-1-i])
    R.append(gr)

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

print(max(M))

Submission status: Accepted

Solution code:
import fractions as math

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

ret = 0

l1 = []
l2 = []

t = math.gcd(a[0], a[0])
l1.append(t)

for i in range(1, n):
  t = math.gcd(t, a[i])
  l1.append(t)

t = math.gcd(a[-1], a[-1])
l2.append(t)

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

ret = 0
for i in range(n):
  t = 0
  if i == 0:
    t = l2[-2]
  elif i == n-1:
    t = l1[-2]
  else:
    t = math.gcd(l1[i-1], l2[n-i-2])
  if ret < t:
    ret = t

print(ret)

Submission status: Accepted

Solution code:
"""
python3 main.py < input.txt
"""
import math
import itertools as it
import heapq

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

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

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

Submission status: Accepted

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

if len(A)==2:
    print(max(A))
    exit()

def gcd(a,b):
    if a<b: a,b=b,a
    if a%b==0: return b
    return gcd(b,a%b)
    
g=A[0]
L=[g]
for a in A[1:-1]:
    g=gcd(g,a)
    L.append(g)
    
g=A[-1]
R=[g]
for a in A[1:-1][::-1]:
    g=gcd(g,a)
    R.append(g)

ans=max(L[-1],R[-1])
for l,r in zip(L[:-1],R[:-1][::-1]):
    ans=max(ans,gcd(l,r))
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b==0:
        return max(a,b)
    else:
        if a%b == 0:
            return(b)
        else:
            return gcd(b,a%b)
n = int(input())
a = list(map(int,input().split()))
l=[0 for i in range(n)]
r=[0 for i in range(n)]
e=[0 for i in range(n)]
for i in range(1,n):
    l[i]=gcd(l[i-1],a[i-1])
    r[i]=gcd(r[i-1],a[n-i])
for i in range(n):
    e[i] = gcd(l[i],r[n-1-i])
print(max(e))

Submission status: Accepted

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


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

ans = 1
if n == 2:
    print(max(a))
else:
    l = [0] * (n + 1)
    r = [0] * (n + 1)
    for i in range(1, n):
        l[i] = gcd(l[i - 1], a[i - 1])
        r[n - i] = gcd(r[n - i + 1], a[-i])
    for i in range(n):
        m = gcd(l[i], r[i + 1])
        ans = max(ans, m)
    print(ans)

Submission status: Accepted

Solution code:
def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  while y!=0:
    x,y=y,x%y
  return x

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

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

for i in range(n):
  b.append(gcd(l[i],r[n-1-i]))
  
print(max(b))

Submission status: Accepted

Solution code:
import fractions
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


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


def cumgcd(it):
    """
    累積 gcd
    :param collections.Iterable it:
    :return:
    """
    ret = []
    gcd = 0
    for a in it:
        gcd = fractions.gcd(gcd, a)
        ret.append(gcd)
    return ret


N = inp()
A = inl()

cum_L = cumgcd(A)
cum_r = list(reversed(cumgcd(reversed(A))))

ans = max(cum_L[-2], cum_r[1])
for i in range(1, N - 1):
    ans = max(ans, fractions.gcd(cum_L[i - 1], cum_r[i + 1]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

l = [0 for i in range(n+1)]
r = [0 for i in range(n+1)]

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

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

m = [0 for i in range(n)]

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

print(max(m))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def Lgcd(i):
    if i == 0:
        return 0
    if i == 1:
        return a_s[0]
    if i in Lmemo:
        return Lmemo[i]
    re = gcd(Lgcd(i - 1), a_s[i - 1])
    Lmemo[i] = re
    return re


def Rgcd(i):
    if i == n - 1:
        return 0
    if i == n - 2:
        return a_s[-1]
    if i in Rmemo:
        return Rmemo[i]
    re = gcd(Rgcd(i + 1), a_s[i + 1])
    Rmemo[i] = re
    return re


def gcd(a, b):
    if a * b == 0:
        return a + b
    while 1:
        a, b = b, a % b
        if b == 0:
            return a


Lmemo = {}
Rmemo = {}
n = int(input())
a_s = list(map(int, input().split()))
mx = 0
for i in range(n):
    g = gcd(Lgcd(i),Rgcd(i))
    if g > mx:
        mx = g
print(mx)

Submission status: Accepted

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


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

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

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

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

print(max(m))

Submission status: Accepted

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


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


B = [0 for i in range(N+2)]
C = [0 for i in range(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])
print(max(gcd(B[i-1], C[i+1]) for i in range(1, N+1)))

Submission status: Accepted

Solution code:
import fractions # python 3.4.3
# import copy
from functools import reduce

N=int(input())

A=list(map(int,input().split()))
# A.sort()

# n個目までの最小公約数
dp=[0 for _ in range(N+1)]
dpRev=[0 for _ in range(N+1)]

def gcd(a,b):
	if a == 0: 
		return b
	elif b == 0: 
		return a
	# print(a,b)
	return reduce(fractions.gcd, (a,b))

dp[0]=0
for n in range(0,N):
	dp[n+1]=gcd(dp[n],A[n])

dpRev[N]=0
for n in range(N-1,-1,-1):
	dpRev[n]=gcd(A[n],dpRev[n+1])

# print(dp)
# print(dpRev)


ans=0
for n in range(N):
	ans = max( ans, gcd(dp[n],dpRev[n+1]) )


print(ans)

Submission status: Accepted

Solution code:
# math.gcd is introduced in python 3.5
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

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

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

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

print(max(G))

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 = []

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

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

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

print(max(M))

Submission status: Accepted

Solution code:
from functools import reduce

result = 0

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

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(max(gcd(X[i], Y[i]) for i in range(n)))

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()))
#a=1
init=1
#maxa=99999999999999999999999999
#maxa=A[1]
B1=[]
for i in A:
    if init==1:
        a=i
        init=0
        B1.append(a)
    else:
        a=gcd(a,i)
        B1.append(a)

init=1
B2=[]
for i in A[::-1]:
    if init==1:
        a=i
        init=0
        B2.append(a)
    else:
        a=gcd(a,i)
        B2.append(a)

#print(B1)
#print(B2)
result=0
for i in range(n):
    if i==0:
        if result<B2[n-2]:
            result=B2[n-2]
    elif i==n-1:
        if result<B1[n-2]:
            result=B1[n-2]
    else:
        if result<gcd(B1[i-1],B2[n-i-2]):
            result=gcd(B1[i-1],B2[n-i-2])

print(result)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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

if N == 2:
    print(max(A))
    sys.exit(0)

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(1, N):
    L[i] = gcd(L[i-1], A[i])
    R[-i-1] = gcd(R[-i], A[-i-1])

# print(L)
# print(R)

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

print(max_gcd)
#min_g = max(G1[-1], G2[1])
#min_g2 = [math.gcd(G1[i], G2[i+1]) for i in range(N-2)]

Submission status: Accepted

Solution code:
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] * (N + 1)
R = [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 = 1
for i in range(N):
    ans = max(ans, gcd(L[i], R[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()))

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

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

print(max(M))

Submission status: Accepted

Solution code:
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] * (N + 1)
R = [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 = 1
for i in range(N):
    ans = max(ans, gcd(L[i], R[i+1]))

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

ans = 0

l = [0]
r = [0]

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

ans = 0

for i in range(n):
    ans = max(ans, fractions.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):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b

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

print(max(can))

Submission status: Accepted

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

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

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

# GCDの結合則を利用する
# 左端、右端からの累積GCDを求めておくと、Aiを取り除いた場合のGCDがすぐに計算できる。
# つまり、
# L(i): n=0,...,iまでのGCD 
# R(i): n=i,...,N-1までのGCD
# このとき、Aiを除いた全体のGCDは、GCD(L(i-1), R(i+1))で計算できる。

L = [0] * N
R = [0] * N

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

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

Submission status: Accepted

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


N = int(input())
A = list(map(int, input().split()))
R = [0 for i in range(N - 1)]
L = [0 for i in range(N - 1)]
R[0] = A[0]
L[0] = A[-1]
for i in range(1, N - 1):
    R[i] = gcd(R[i - 1], A[i])
for j in range(1, N - 1):
    L[j] = gcd(L[j - 1], A[-1 - j])
    # print(L[j])
t = 0
for i in range(N - 2):
    # print(R[i], L[N - 3 - i])
    t = max(t, gcd(R[i], L[N - 3 - i]))
print(max(t, R[-1], L[-1]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
def divisors(n):
    div = set()
    A = 1
    while A*A <= n:
        if n%A == 0:
            if A*A == n:
                div.add(A)
            else:
                B = n//A
                div.add(A)
                div.add(B)
        A += 1
    return div
div = list(divisors(A[0]) | divisors(A[1]))
div.sort(reverse=True)
for x in div:
    count = 0
    for a in A:
        if a%x != 0:
            count += 1
        if count > 1:
            break
    if count <= 1:
        print(x)
        break

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int ,input().split()))
l = [a[0]]
r = [a[-1]]
def gcd(a, b):
    while a % b:
        a, b = b, a % b
    return b

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

print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
def divisors(n):
    div = set()
    A = 1
    while A*A <= n:
        if n%A == 0:
            if A*A == n:
                div.add(A)
            else:
                B = n//A
                div.add(A)
                div.add(B)
        A += 1
    return div
div = list(divisors(A[0]) | divisors(A[1]))
m = 0
for x in div:
    count = 0
    for a in A:
        if a%x != 0:
            count += 1
        if count > 1:
            break
    if count <= 1:
        m = max(m, x)
print(m)

Submission status: Accepted

Solution code:
from fractions import gcd

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

fort = [nums[0], gcd(nums[0], nums[1])]
back = [nums[N-1], gcd(nums[N-1], nums[N-2])]
ans = []

for i in range(N-2):
    fort.append(gcd(fort[i+1], nums[i+2]))
                
for i in range(N-2):
    back.append(gcd(back[i+1], nums[N-(i+3)]))
    
for i in range(1, N-1):
    ans.append(gcd(fort[i-1], back[N-2-i]))

ans.append(fort[N-2])
ans.append(back[N-2])

print(max(ans))

Submission status: Accepted

Solution code:
import numpy as np
from fractions import gcd
from functools import reduce

n = int(input())

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
def find(inte):
    re = []
    for i in range(1,int(inte**0.5)+1):
        if inte%i==0:
            re.append(i)
            if i != inte/i:
                re.append(int(inte/i))
    return set(re)
if n==2:
    print(A[1])
else:
    a1 = find(A[0])
    a2 = find(A[1])
    a3 = find(A[2])
    t1 = a1 & a2
    t2 = a2 & a3
    t3 = a1 & a3
    cond = t1 | t2 |t3
    maxi = 0
    for con in cond:
        count = 0
        flag = True
        for a in A:
            if a%con != 0:
                count +=1
            if count >= 2:
                
                flag = False
                break
        if flag and maxi < con:
            maxi = con
    print(maxi)

Submission status: Accepted

Solution code:
from fractions import gcd

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

def divs(p):
	div=set()
	for n in range(1, int(p**0.5)+1):
		if p % n == 0:
			div.add(n)
			div.add(p // n)
	return div


for d in sorted(divs(A[0]) | divs(A[1]), reverse=True):
	if sum([0 if a % d == 0 else 1 for a in A]) < 2:
		break

print(d)

Submission status: Accepted

Solution code:
import fractions


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

def gcd(x_,y_):
	x = max(x_, y_)
	y = min(x_, y_)
	if y==0:
		return x
	if x%y == 0:
		return y
	return gcd(y, x%y)

L = [0]*n
R = [0]*n
L[0] = a[0]
R[-1] = a[-1]

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

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

Submission status: Accepted

Solution code:
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)

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:
def gcd(a,b):
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

def gcd_l(A):
    if len(A) == 1:
        return A[0]
    x = gcd(A[0], A[1])
    if len(A) == 2:
        return x
    for i in range(2, len(A)):
        x = gcd(x, A[i])
    return x

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

B = []
C = []
x = A[0]
y = A[-1]
for i in range(N):
    x = gcd(x, A[i])
    B.append(x)
    y = gcd(y, A[N-1-i])
    C.append(y)
    
ans = 1

for i in range(1, N-1):
    ans = max(ans, gcd(B[i-1], C[N-2-i]))

ans = max(ans, B[N-2], C[N-2])

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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())
Alist = list(map(int, input().split()))
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b <= 0:
        return a
    else:
        return gcd(b, a%b)
left = [0, Alist[0]]
right = [Alist[-1]]
for i in range(N-1):
    left += [gcd(Alist[i+1], left[-1])]
    right += [gcd(Alist[N-i-2], right[-1])]
right = right[::-1] + [0]
print(max([gcd(left[i], right[i+1]) for i in range(N)]))

Submission status: Accepted

Solution code:
from sys import stdin

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

n = int(stdin.readline().rstrip())
an = list(map(int, input().split()))

left = []
right = []

for i in range(n):
  if(i==0):
    before = an[i]
  else:
    before = gcd(before, an[i])
  left.append(before)

for i in range(n):
  if(i==0):
    before = an[n-1-i]
  else:
    before = gcd(before, an[n-1-i])
  right.append(before)

max = 0
for i in range(n):
  if(i==0):
    before = right[n-2];
  elif(i==(n-1)):
    before = left[n-2];
  else:
    before = gcd(left[i-1],right[n-2-i])
  if(max < before ):
    max = before

print(max)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

from fractions import gcd

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, A):
    L = [A[0]]
  
    for a in A[1:]:
        L.append(gcd(L[-1], a))
        
    R = [-1] * N
    R[-1] = A[-1]
    for i in range(N-2, -1, -1):
        R[i] = gcd(R[i+1], A[i])
    
    ans = 0
    for i in range(N):
        if i == 0:
            ans = max(ans, R[i+1])
        elif i == N-1:
            ans = max(ans, L[i-1])
        else:
            ans = max(ans, gcd(L[i-1], R[i+1]))
    return ans
    


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


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

ans = 0
for i in range(1, N-1):
    a = gcd(forwards[i-1], backwards[i+1])
    if a > ans:
        ans = a

if N > 2:
    ans = max([ans, forwards[-2], backwards[1]])
elif N == 2:
    ans = max(A)
else:
    ans = A[0]

print(ans)

Submission status: Accepted

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

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

noskip = gcd(a[0], a[1])
skipped = max(gcd(a[0], a[2]), gcd(a[1], a[2]))

for i in range(2, n):
    skipped = max(gcd(skipped, a[i]), noskip)
    noskip = gcd(noskip, a[i])

print(max(noskip, skipped))

Submission status: Accepted

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

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

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

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

M = list()
for i in xrange(N):
    M.append(gcd(L[i], R[i+1]))

print max(M)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

B=list(reversed(B))

print(max([A[N-2], B[1]] + [gcd(A[i-1], B[i+1]) for i in range(1,N-1)]))