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 operator import itemgetter
from functools import reduce
import fractions as f
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
rev_a = list(reversed(a))
ans = 0
accumulation_gcd = [0] * n
rev_accumulation_gcd = [0] * n
accumulation_gcd[0] = a[0]
rev_accumulation_gcd[0] = rev_a[0]

for i in range(1, n):
    accumulation_gcd[i] = f.gcd(a[i], accumulation_gcd[i-1])
    rev_accumulation_gcd[i] = f.gcd(rev_a[i], rev_accumulation_gcd[i-1])

rev_accumulation_gcd.reverse()


for i in range(n):
    if i == 0:
        ans = max(ans, rev_accumulation_gcd[1])
    elif i == (n - 1):
        ans = max(ans, accumulation_gcd[n-2])
    else:
        ans = max(ans, f.gcd(accumulation_gcd[i-1], rev_accumulation_gcd[i+1]))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)


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

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

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)


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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
LA=list(map(int,input().split()))
ans=[]

def gcd(m,n):
    if m==0 or n==0:
        return m+n
    while n:
        m,n=n,m%n
    return m

La=[0]
Lb=[0]

for n in range(N-1):
    La.append(gcd(La[n],LA[n]))
    Lb.append(gcd(Lb[n],LA[-(n+1)]))

for n in range(N):
    ans.append(gcd(La[n],Lb[-(n+1)]))
        
print(max(ans))

Submission status: Accepted

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

N = int(input())
A = [int(_) for _ in input().split()]
LGCD = [A[0]]
RGCD = [A[-1]]

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

ans = max(LGCD[-1], RGCD[-1])
for i in range(N-2):
    tmp = gcd(LGCD[i], RGCD[-(i+2)])
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
import math
from fractions import gcd
from functools import reduce
def gcds(*numbers):
    return reduce(gcd, numbers)

def resolve():
    N = int(input())
    As = list(map(int, input().split(" ")))
    
    left = [0] * (N + 1)
    right = [0] * (N + 1)
    for i in range(N):
        left[i + 1] = (gcd(left[i],As[i]))
        right[N - 1 - i] = (gcd(right[(N - 1) - i + 1], As[(N - 1) - i]))

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

if '__main__' == __name__:
    print(resolve())

Submission status: Accepted

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


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

"順方向累積GCD"
forward_gcd = [0]

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

"逆方向累積GCD"
reverse_gcd = [0]
for i in range(N-1, -1, -1):
    reverse_gcd.append(gcd(reverse_gcd[-1], A[i]))

reverse_gcd.reverse()

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

print(ans)

Submission status: Accepted

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


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

"順方向累積GCD"
forward_gcd = [0]

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

"逆方向累積GCD"
reverse_gcd = [0]
for i in range(N-1, -1, -1):
    reverse_gcd.append(gcd(reverse_gcd[-1], A[i]))

reverse_gcd.reverse()

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

# gcd_list = [gcd(forward_gcd[i], reverse_gcd[i+1]) for ]

print(ans)

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]

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

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

print(ans)

Submission status: Accepted

Solution code:

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A_reverse = list(reversed(A))
    left = [0]
    right = [0]
    answer = []
    for n in range(N):
        left.append(gcd(left[n], A[n]))
        right.append(gcd(right[n], A_reverse[n]))
    del left[N]
    del right[N]
    right.reverse()
    for n in range(N):
        answer.append(gcd(left[n], right[n]))
    print(max(answer))


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def gcd(x, y, *val):
    val = sorted([x, y], reverse=True) + list(val)
    count = len(val)

    if count == 2:
        if val[1] == 0:
            return val[0]

        mod = val[0] % val[1]
        if mod == 0:
            return val[1]
        elif mod == 1:
            return 1
        else:
            return gcd(val[1], mod)
    else:
        if count % 2 == 1:
            val.append(val[-1])

        return gcd(*[gcd(val[i], val[i + 1]) for i in range(0, count, 2)])
        

def main():
    sinputl = sys.stdin.readline

    num = int(sinputl().strip())
    input = [int(x) for x in sinputl().split()]

    gcd_max = 1
    input_mem = []

    if num == 2:
        print(max(input))
        return

    gcd_left = [0]
    gcd_right = [0]

    for i in range(num - 1):
        gcd_left.append(gcd(input[i], gcd_left[i]))
        gcd_right.append(gcd(input[-1 - i], gcd_right[i]))

    gcd_right.reverse()
    gcd_list = []

    for i in range(num):
        gcd_list.append(gcd(gcd_left[i], gcd_right[i]))

    print(max(gcd_list))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import fractions
from functools import reduce
n = int(input())
a = list(map(int,input().split()))
gcds = 0
r = [0]
l = [0]
for N in range(n):
	r.append(fractions.gcd(r[N],a[N]))
	l.append(fractions.gcd(l[N],a[n - N - 1]))
for i in range(n):
	gcds = max(gcds,(fractions.gcd(r[i],l[n - i - 1])))
print(gcds)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
n=int(input())
a=list(map(int,input().split()))
a=[0]+a+[0]
l=[0]*(n+2)
r=[0]*(n+2)
for i in range(1,n+1):
    l[i]=fractions.gcd(l[i-1],a[i])
for i in range(n,0,-1):
    r[i]=fractions.gcd(r[i+1],a[i])
print(max(fractions.gcd(l[i-1],r[i+1]) 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]*(N+2)
R = [0]*(N+2)
ans = 0
for i in range(N):
	L[i+1] = (gcd(L[i],A[i]))
	R[N-i] = (gcd(R[N-i+1],A[N-1-i]))
for i in range(N):
	ans = max(ans,(gcd(L[i], R[i+2])))
print(ans)

Submission status: Accepted

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


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


L = []
R = []

L.append(0)
R.append(0)

for i in range(N - 1):
    L.append(gcd(L[i], As[i]))
    R.append(gcd(R[i], As[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:
def gcd(a, b):
    bigger = max(a, b)
    smaller = min(a, b)
    while smaller != 0:
        bigger, smaller = smaller, bigger % smaller
    return bigger


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

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

gcds = [gcd_l.pop(), gcd_r.pop(0)]
for l, r in zip(gcd_l, gcd_r):
    gcds.append(gcd(l, r))
print(max(gcds))

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)

ll = []
lr = []

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

ans = 0
for i in range(n):
    ans = max(ans, gcd(ll[i], lr[n - 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)

ll = []
lr = []

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

ll.insert(0, lr[n - 2])
lr.insert(0, ll[n - 1])

ans = 0
for i in range(n):
    t = gcd(ll[i], lr[n - i - 1])
    if t > ans:
        ans = t

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
left,right=[0],[0]
[(left.append(gcd(left[i],A[i])),right.append(gcd(right[i],A[N-i-1]))) for i in range(N-1)]
right.reverse()
print(max([gcd(a,b) for a,b in zip(left,right)]))

Submission status: Accepted

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

for iii in range(len(a)):
  end=a[len(a)-iii-1]
  front=a[iii]
  if iii==0:
    elist.append(end)
    flist.append(front)
  else:
  	elist.append(gcd(end,elist[-1]))
  	flist.append(gcd(front,flist[-1]))

ans=0
for iii in range(len(elist)-2):
  ans=max(ans,gcd(flist[iii],elist[len(elist)-iii-3]))

ans=max(flist[-2],ans)
ans=max(elist[-2],ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y) #再帰定義
	
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

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

M = []  
for i in range(N):
  M.append(gcd(L[i], R[i]))
print(max(M))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
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])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

max_m = 0
for i in range(N):
    m = gcd(L[i], R[i+1])
    if max_m < m:
        max_m = m
print(max_m)

Submission status: Accepted

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

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

g_l = [1 for i in range(N)]
g_r = [1 for i in range(N)]

g_l[0] = A[0]
g_r[-1] = A[-1]

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

ans = max(g_r[1], g_l[-2])
for i in range(1, N-1):
    ans = max(ans, gcd(g_l[i-1], g_r[i+1]))

print(ans)

Submission status: Accepted

Solution code:
def euclid(a, b):
    mod = a % b
    if mod != 0:
        b = euclid(b, mod)
    return b
N = int(input())
A = [int(a) for a in input().split()]
gcd_lis = [A[0]]
gcd = A[0]
for a in A[1:]:
    gcd = euclid(gcd, a)
    gcd_lis.append(gcd)
inv_gcd_lis = [A[-1]]
gcd = A[-1]
for a in A[::-1][1:]:
    gcd = euclid(gcd, a)
    inv_gcd_lis.append(gcd)
inv_gcd_lis = inv_gcd_lis[::-1]
maximam = 0
for index in range(N):
    if index == 0:
        gcd = inv_gcd_lis[1]
    elif index == N - 1:
        gcd = gcd_lis[N-2]
    else:
        gcd = euclid(gcd_lis[index - 1], inv_gcd_lis[index + 1])
    maximam = max(gcd, maximam)
print(maximam)

Submission status: Accepted

Solution code:
# ABC125C - GCD on Blackboard
# Accumulative GCD
from fractions import gcd

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

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

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

Submission status: Accepted

Solution code:
# ABC125C - GCD on Blackboard
# Accumulative GCD
import sys
input = sys.stdin.readline

from fractions import gcd

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
	
def main():
	N = int(input())
	A = list(map(int, input().split(" ")))
	
	L = []
	for i, val in enumerate(A):
		if i == 0:
			L.append(val)
			continue
		tmp = gcd(val, L[i-1])
		L.append(tmp)
		
	R = []
	for i, val in enumerate(reversed(A)):
		if i == 0:
			R.append(val)
			continue
		tmp = gcd(val, R[i-1])
		R.append(tmp)
		
	ans = 0
	for i, val in enumerate(A):
		if i == 0:
			tmp = R[len(A)-2]
		elif i == len(A)-1:
			tmp = L[len(A)-2]
		else:
			tmp = gcd(L[i-1], R[len(A)-i-2])
			
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

def gcd(x, y):
    #print('gcd({0},{1})'.format(x,y))
    if (y==0):
        return x
    else:
        return gcd(y, x%y)

def gcd_left(i):
    #print('gcd_left({0})'.format(i))

    if i<=-1:
        return 0
    else:
        if l[i]:
            return gcd(gcd_left(i-1), a[i])
        else:
            l[i] = gcd( gcd_left(i-1), gcd_right(i+1))


def gcd_right(i):
    #print('gcd_left({0})'.format(i))
    
    if i>=n:
        return 0
    else:
        return gcd( a[i], gcd_right(i+1))

def gcd_left_update(ls, i):
    #print('gcd_left({0})'.format(i))

    if i<0:
        return 0
    elif i==0:
        return a[i]
    else:        
        return gcd(ls[i-1], a[i])


def gcd_right_update(ls, i):
    #print('gcd_right({0})'.format(i))
    
    if i>=n:
        return 0
    elif i==n-1:
        return a[i]
    else:
        return gcd( a[i], ls[i+1])

def gcd_excepts(i):
    #print('gcd_excepts({0})'.format(i))
    return gcd( gcd_left(i-1), gcd_right(i+1))

def gcd_excepts2(i):
    #print('gcd_excepts2({0})'.format(i))
    left = 0
    right = 0
    if i-1<0:
        left = 0
    else:
        left = l[i-1]
    
    if i+1>=n:
        right = 0
    else:
        right = r[i+1]
        
    return gcd( left, right )

l = [None for i in range(n)]
for i in range(n):
    l[i] = gcd_left_update(l,i)

r = [None for i in range(n)]
for i in reversed(range(n)):
    r [i] = gcd_right_update(r,i)
    
m = [gcd_excepts2(i) for i in range(n)]

print(max(m))

Submission status: Accepted

Solution code:
from  fractions import gcd
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
ans=1
for i in range(N-1):
    R.append(gcd(R[-1], A[-1-i]))
    L.append(gcd(L[-1], A[i]))
print(max(gcd(l,r)for l,r in zip(L,R[::-1])))

Submission status: Accepted

Solution code:
import math
import fractions


# i番目の要素をxに変更する
def update(i, x, list_len, seg):
    # リストのi番目の要素がsegの何番目なのかを求める
    # リスト長4で1番目の要素はsegtree中では4+1-1=4番目
    i = list_len + i - 1
    seg[i] = x
    while i > 0:
        i = math.floor((i-1)/2)  # 上のノード
        # 子ノードを元に更新（GCD,MAX,MIN）
        seg[i] = fractions.gcd(seg[2*i + 1], seg[2*i + 2])
    # 頂点を返す
    # print(seg)
    return seg[0]


n = int(input())
a = list(map(int, input().split()))
segtree = [0] * (2*len(a) - 1)  # segtreeは2n-1個
for i in range(n):
    update(i, a[i], n, segtree)

maxi = 0
for i in range(n):
    maxi = max(maxi, update(i, 0, n, segtree))
    update(i, a[i], n, segtree)

print(maxi)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

R = [0]
for i in range(n-1, -1, -1):
    R.append(gcd(R[(n-1)-i],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:
from fractions import gcd

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

ret1 = [0] * (N+2)
ret2 = [0] * (N+2)

for i in range(N):
    ret1[i+1] = gcd(ret1[i], A[i])
for i in range(N-1,-1,-1):
    ret2[i+1] = gcd(ret2[i+2], A[i])
    
#print(ret1)
#print(ret2)

ans = 0
for i in range(N):
    X = gcd(ret1[i], ret2[i+2])
    if X > ans:
        ans = X
        
print(ans)

Submission status: Accepted

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

lans = 0
llst = [0] * (N + 1)
rans = 0
rlst = [0] * (N + 1)

for i in range(N):
    lans = fractions.gcd(lans, aLst[i])
    llst[i + 1] = lans

for i in range(N - 1, -1, -1):
    rans = fractions.gcd(rans, aLst[i])
    rlst[i] = rans

ansMax = 0
for i in range(N):
    ansMax = max(ansMax, fractions.gcd(llst[i], rlst[i + 1]))

print(ansMax)

Submission status: Accepted

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

L = [0]
for i in range(N):
    L.append(gcd(L[i],A[i]))
    
R = [0]
for i in range(N-1,-1,-1):
    R.append(gcd(R[-(i-N+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:
from fractions import gcd

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



# L[0] = 0
# L[i] (i=1, ..., N)にはA_1, ..., A_iの最大公約数が格納されている

L = []
L.append(0)

for i in range(N):
    L.append(gcd(L[i], A[i]))

#  for i in range(N+1):
    #  print(L[i])


# R[N+1] = 0
# R[i] (i=N, N-1, ..., 1)にはA_i, ..., A_Nの最大公約数が格納されている

R = [0] * (N+2)
# R = [0, 0, 0, ... , 0] (0がN+2個)

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

#  for i in range(N+1, -1, -1):
    #  print(R[i])



# M[i] (i=0, ..., N-1)にはA_(i+1)を除いた整数の最大公約数が格納されている

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

print(max(M))

Submission status: Accepted

Solution code:
import fractions
import copy
n = int(input())
a = list(map(int, input().split()))
a_r = copy.copy(a)
a_r.reverse()
cumsum_gcd = [0]
cumsum_gcd_r = [0]
for i in range(n-1):
    cumsum_gcd.append(fractions.gcd(cumsum_gcd[i], a[i]))
    cumsum_gcd_r.append(fractions.gcd(cumsum_gcd_r[i], a_r[i]))
cumsum_gcd_r.reverse()
ans = []
for i in range(n):
    ans.append(fractions.gcd(cumsum_gcd[i], cumsum_gcd_r[i]))
print(max(ans))

Submission status: Accepted

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


def gcd(a, b):
    if a < b: return gcd(b, a)
    elif b > 0: return gcd(b, a % b)
    else:
        return a

L = [0,a[0]]
R = [0,a[-1]]

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

Submission status: Accepted

Solution code:
import sys
# import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
# from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
# from itertools import permutations, combinations, product, accumulate, groupby
# from bisect import bisect_left, bisect_right, insort_left, insort_right
# from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
# dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()
a = wi()

value = [] # ノードの値を持つ配列
N = 0 # 葉の数

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

def update(i, x):
    # i番目の葉の値をxに変える
    i += N - 1  # i番目の葉のノード番号
    value[i] = x
    while i > 0:
        i = (i - 1) / 2  # ノード i の親ノードの番号に変える
        value[i] = min(value[i * 2 + 1], value[i * 2 + 2])  # 左右の子の min を計算しなおす


#define INF 2147483647 // 2^31-1
INF = float("INF")
def query(a, b, k, l, r) :
    # [a, b) の区間に対するクエリについて
    # ノード k （区間 [l, r) 担当）が答える
    if r <= a or b <= l:
        # 区間が被らない場合は INF を返す
        return 0
    if a <= l and r <= b:
        # ノード k の担当範囲がクエリ区間 [a, b) に完全に含まれる
        return value[k]
    else:
        # 一部だけ範囲が被る場合は左右の子に委託する
        c1 = query(a, b, 2 * k + 1, l, (l + r) // 2)  # 左の子に値を聞く
        c2 = query(a, b, 2 * k + 2, (l + r) // 2, r)  # 右の子に値を聞く
        # 左右の子の値の min を取る
        return gcd(c1, c2)



value = [] # ノードの値を持つ配列
N = 0  # 葉の数

#if __name__ == '__main__':
N = 1
while N < n:
    N *= 2  # 葉の数を計算（n以上の最小の2冪数）

value = [0] * (2 * N - 1)
for i in reversed(range(2 * N - 1)):
    if N - 1 <= i < 2 * N - 1:
        if N - 1 <= i < N - 1 + n:
            value[i] = a[i - (N - 1)]
        else:
            value[i] = 0
    else:
        value[i] = gcd(value[2 * i + 1], value[2 * i + 2])

for i in range(n):#query(,,0,0,N)
    if i == 0:
        ansli.append(query(1, n, 0, 0, N))
    elif i == n - 1:
        ansli.append(query(0, n - 1, 0, 0, N))
    else:
        ansli.append(gcd(query(0, i, 0, 0, N), query(i + 1, n, 0, 0, N)))
print(max(ansli))

Submission status: Accepted

Solution code:
import sys
# import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
# from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
# from itertools import permutations, combinations, product, accumulate, groupby
# from bisect import bisect_left, bisect_right, insort_left, insort_right
# from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
# inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
# dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

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

l_gcd = [a[0]]#左から
r_gcd = [a[-1]]#右から
kl = a[0]
kr = a[-1]
for i in range(n - 2):
    kl = gcd(kl, a[i + 1])
    l_gcd.append(kl)
    kr = gcd(kr, a[-(i + 2)])
    r_gcd.append(kr)

ansli = []
for i in range(n):
    if i == 0:
        ansli.append(r_gcd[-1])
    elif i == n - 1:
        ansli.append(l_gcd[-1])
    else:
        ansli.append(gcd(l_gcd[i - 1], r_gcd[-(i + 1)]))

print(max(ansli))

Submission status: Accepted

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

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

def gcd(a, b):
    if a < b: return gcd(b, a)
    elif b > 0: return gcd(b, a % b)
    else:
        return a

l2r = [0] * N
tmp = 0
for i in range(N):
    l2r[i] = tmp
    tmp = gcd(tmp, A[i])

r2l = [0] * N
tmp = 0
for i in range(1, N + 1):
    r2l[-i] = tmp
    tmp = gcd(tmp, A[-i])
    
ans = 1
for i in range(N):
    tmp = gcd(l2r[i], r2l[i])
    if ans < tmp: ans = tmp

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

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

b = list(accumulate([0] + a, gcd))
c = list(accumulate([0] + a[::-1], gcd))
l = list(gcd(s, t) for s, t in zip(b[:-1], c[::-1][1:]))
print(max(l))

Submission status: Accepted

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

def gcd(x,y):
    c = x%y
    if c == 0:
        return y
    else:
        return gcd(y,c)
    
left = [0] * N
right = [0] * N
left[0] = A[0]
right[N-1] = A[N-1]

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

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

Submission status: Accepted

Solution code:
import numpy as np
from fractions import gcd

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


L = np.zeros(N, dtype=int)
R = np.zeros(N, dtype=int)

L[0] = A[0]


# L[i] .. A[0], A[1], A[i] の最大公約数
R[N-1] = A[N-1]
# R[i] .. A[-1], A[-2], .. A[(-(i+1)] の最大公約数
# R[i] .. A[N-1], A[N-2], .. A[(N-i-1)] の最大公約数

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

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

def it(i):
    if i == 0:
        return R[1]
    if i == N-1:
        return L[N-2]
    return gcd(L[i-1], R[i+1])

# print(A)
# print(L)
# print(R)

print(max(it(i) for i in range(N)))

Submission status: Accepted

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

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[N-1-i]))
r = r[::-1]
ans=0
for i in range(N):
	temp=gcd(l[i],r[i+1])
	ans=max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd as GCD

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

# GCD_LtoR[i] = GCD(A0, A1, ... , A(i-1))
GCD_LtoR = [None] * N
# GCD_LtoR[i] = GCD(Ai, A(i+1), ... , AN)
GCD_RtoL = [None] * N

GCD_LtoR[0] = A[0]
for i in range(1, N):
    GCD_LtoR[i] = GCD(A[i], GCD_LtoR[i-1])

GCD_RtoL[N-1] = A[N-1]
for i in range(N-2, -1, -1):
    GCD_RtoL[i] = GCD(A[i], GCD_RtoL[i+1])

GCD_max = GCD_RtoL[1]
for i in range(0, N-1):
    # Aに含まれるAi以外の要素のGCDを計算する
    GCD_ex_i = GCD(GCD_LtoR[i-1], GCD_RtoL[i+1])
    GCD_max = max(GCD_ex_i, GCD_max)
GCD_max = max(GCD_LtoR[N-2], GCD_max)
print(GCD_max)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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_new = R[::-1]
ans = 0
for i in range(N):
    temp = gcd(L[i], R_new[i+1])
    ans = max(ans,temp)
    
print(ans)

Submission status: Accepted

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

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[N-1-i]))

R = R[::-1]
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
try :
    from math import gcd
except ImportError :
    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[N-1-i]))

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


print(max(M))

Submission status: Accepted

Solution code:
from functools import reduce


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


def lcm(a, b):
    return a * b // gcd(a, b)


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

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

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

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

print(reduce(max, m))