Problem:


Score : 300 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, written on the blackboard.

You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.

Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Sample Input 1

3
7 6 8

Sample Output 1

2

If we replace 7 with 4, the greatest common divisor of the three integers on the blackboard will be 2, which is the maximum possible value.

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
if N == 2:
    ans = max(A)
else:
    GCDF, GCDB = [0]*N, [0]*N
    GCDF[1],GCDB[-2] = A[0], A[N-1]
    for i in range(2, N):
        GCDF[i] = gcd(GCDF[i-1],A[i-1])
        GCDB[-(i+1)] = gcd(GCDB[-i], A[-i])
    GCDm = [0]*N
    GCDm[0] = GCDB[0]
    GCDm[N-1] = GCDF[N-1]
    for i in range(1, N-1):
        GCDm[i] = gcd(GCDF[i],GCDB[i])
    ans = max(GCDm)
print(ans)

Submission status: Accepted

Solution code:

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

from fractions import gcd
from itertools import accumulate

X = list(accumulate(A, gcd))
Y = list(accumulate(A[::-1], gcd))

Y.insert(0,0)
X.insert(0,0)

ans = -1
for i in range(N):
  ans = max(ans, gcd(X[i], Y[N-1-i]))

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

gcdl = [0] * n
gcdr = gcdl[:]

gcdl[0]  = a[0]
gcdr[-1] = a[-1] 

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

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

max_gcd = max(gcdl[-2], gcdr[1])

for i in range(1, n - 1):
  temp_gcd = gcd(gcdl[i - 1], gcdr[i + 1])
  if temp_gcd > max_gcd:
    max_gcd = temp_gcd

print(max_gcd)

Submission status: Accepted

Solution code:
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length-1] = ls[i]
  for i in range(length-2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if a<=l and r<=b:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(n):
  ans.append(gcd(query(0,i,0,0,length),query(i+1,n,0,0,length)))
print(max(ans))

Submission status: Accepted

Solution code:
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length-1] = ls[i]
  for i in range(length-2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if l<=a and b<=r:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(n):
  update(i,0)
  ans.append(query(0,n,0,0,length))
  update(i,ls[i])
print(max(ans))

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
input()
l = list(map(int,input().split()))
gcd_l = [i for i in l]
gcd_r = [i for i in l]
for i in range(1,len(l)):
    gcd_l[i] = gcd(gcd_l[i-1],gcd_l[i])

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

ans = max(gcd_r[1],gcd_l[-2])
for i in range(1,len(l)-1):
    ans = max(ans,gcd(gcd_l[i-1],gcd_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]

g = A[0]
for a in A:
  g = gcd(g, a)
  L.append(g)

A = A[::-1]
g = A[0]
for a in A:
  g = gcd(g, a)
  R.append(g)

R = R[::-1]

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

print(ans)

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc145/tasks/abc145_e
# E - All-you-can-eat
"""
DP1[i][j] =the maximum sum of deliciousness of dishes, which are chosen from 1st- to i-th dishes,
such that he can finish them in j minutes

still WA!!!

"""


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


N = gi()
A = [0] * N
ls = [0] * N
rs = [0] * N

for i in range(N):
    A[i] = gi()

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

ans = max(ls[N - 2], rs[1])

for mid in range(1, N - 1):
    ans = max(ans, gcd(ls[mid - 1], rs[mid + 1]))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
import fractions
from functools import reduce

def gcd(*numbers):
    return abs(reduce(fractions.gcd, numbers))

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

fromLeft = [a[0]] + [None] * (n - 1)
for i in range(1, n):
    fromLeft[i] = gcd(fromLeft[i - 1], a[i])
fromRight = [None] * (n - 1) + [a[-1]]
for i in range(n - 2, -1, -1):
    fromRight[i] = gcd(fromRight[i + 1], a[i])
ret = 1
for repr in range(n):
    if repr == 0:
        curGcd = fromRight[repr + 1]
    elif repr == n - 1:
        curGcd = fromLeft[repr - 1]
    else:
        curGcd = gcd(fromLeft[repr - 1], fromRight[repr + 1])
    ret = max(ret, curGcd)
print(ret)

Submission status: Accepted

Solution code:
import os, sys, re, math, fractions

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

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

memo_L = [1] * N
memo_R = [1] * N

for i in range(N):
    if i == 0:
        memo_L[i] = A[i]
        memo_R[i] = A[N-1]
    elif i == N - 1:
        memo_L[i] = gcd(A[i], memo_L[i-1])
        memo_R[i] = gcd(A[0], memo_R[i-1])
    else:
        memo_L[i] = gcd(A[i], memo_L[i-1])
        memo_R[i] = gcd(A[N-1-i], memo_R[i-1])

memo_R.reverse()

ret = 1
for j in range(N):
    if j == 0:
        ret = max(ret, memo_R[1])
    elif j == N-1:
        ret = max(ret, memo_L[j-1])
    else:
        common_gcd = fractions.gcd(memo_L[j-1], memo_R[j+1])
        ret = max(ret, common_gcd)

print(ret)

Submission status: Accepted

Solution code:
import os, sys, re, math, fractions

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

memo_L = [1] * N
memo_R = [1] * N

for i in range(N):
    if i == 0:
        memo_L[i] = A[i]
        memo_R[i] = A[N-1]
    elif i == N - 1:
        memo_L[i] = fractions.gcd(A[i], memo_L[i-1])
        memo_R[i] = fractions.gcd(A[0], memo_R[i-1])
    else:
        memo_L[i] = fractions.gcd(A[i], memo_L[i-1])
        memo_R[i] = fractions.gcd(A[N-1-i], memo_R[i-1])

memo_R.reverse()

ret = 1
for j in range(N):
    if j == 0:
        ret = max(ret, memo_R[1])
    elif j == N-1:
        ret = max(ret, memo_L[j-1])
    else:
        common_gcd = fractions.gcd(memo_L[j-1], memo_R[j+1])
        ret = max(ret, common_gcd)

print(ret)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100001)

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

# 一人消してgcd
n = int(input())
nl = sorted(list(map(int, input().split(' '))))
rl = nl[::-1]
sumnl = [nl[0]]
sumrl = [rl[0]]
for i in range(1, len(nl)):
    sumnl.append(gcd(sumnl[-1], nl[i]))
    sumrl.append(gcd(sumrl[-1], rl[i]))
sumrl = sumrl[::-1]
if len(sumnl) == 1:
    print(sumnl[0])
else:
    print(max([sumnl[-2]] + [gcd(sumnl[i],sumrl[i+2]) for i in range(len(sumrl) - 2)] + [sumrl[1]]))

Submission status: Accepted

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

Submission status: Accepted

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


N = int(input())
A = list(map(int, input().split()))
r = 0
b = -1

for i in range(N):
    a = gcd(r, A[i]) if r != 0 else A[i]
    if a < r:
        b = i
    r = a

r3 = 0
for i in range(N):
    if i == b - 1:
        continue
    r3 = gcd(r3, A[i]) if r3 != 0 else A[i]

r4 = 0
for i in range(N):
    if i == b:
        continue
    r4 = gcd(r4, A[i]) if r4 != 0 else A[i]

d = sorted([(gcd(A[i], A[i + 1]), i) for i in range(N - 1)])
t = d[0][1]
r1 = 0
for i in range(N):
    a = A[i-1] if i == t + 1 else A[i]
    if r1 == 0:
        r1 = a
    else:
        r1 = gcd(r1, a)
r2 = 0
for i in range(N):
    a = A[i+1] if i == t else A[i]
    if r2 == 0:
        r2 = a
    else:
        r2 = gcd(r2, a)
print(max(r1, r2, r3, r4))

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

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

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

ans=rightgcd[1]
for i in range(1,n-1):
	ans=max(ans,gcd(leftgcd[i-1],rightgcd[i+1]))
print(max(ans,leftgcd[n-2]))

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

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

#print(gcdf)

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

#print(gcdb)

ans = max(gcdf[-2],gcdb[1])

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

print(ans)

Submission status: Accepted

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

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

l_ans = [0] * n
g = 0
for i in range(1, n):
    g = gcd(g, v[i-1])
    l_ans[i] = g
r_ans = [0] * n
g = 0
for i in range(1, n):
    g = gcd(g, v[n-i])
    r_ans[i] = g
r_ans.reverse()
ans = 1
for i in range(n):
    ans = max(ans, gcd(l_ans[i], r_ans[i]))
print(ans)

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = [int(x) for x in input().split()]
kouho_set = set()
kouho_set = [0] * (N + 1)
kouho_set[0] = set()
kouho_set[0].add(A[1])
nowgcd = A[0]
for i in range(1, N):
    kouho_set[i] = set()
    for j in kouho_set[i-1]:
        kouho_set[i].add(fractions.gcd(A[i], j))
    kouho_set[i].add(nowgcd)
    nowgcd = fractions.gcd(A[i], nowgcd)
# print(kouho_set)
print(max(kouho_set[N-1]))

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
min0,min1=A[0],A[1]

if min0==min1==1:
    print(1)
    exit()
if N==2:
    print(max(A))
    exit()
yakusuu0lst=[]
yakusuu1lst=[]

if min0>1:
    for i in range(1,int(min0**0.5+1)):
        if min0%i==0:
            yakusuu0lst.append(i)
            yakusuu0lst.append(min0//i)
if min1>1:
    for i in range(1,int(min1**0.5+1)):
        if min1%i==0:
            yakusuu1lst.append(i)
            yakusuu1lst.append(min1//i)
yakusuu0count=[0 for i in range(len(yakusuu0lst))]
yakusuu1count=[0 for i in range(len(yakusuu1lst))]
length0=len(yakusuu0lst)
length1=len(yakusuu1lst)

for a in A:
    for i in range(length0):
        if a%yakusuu0lst[i]==0:yakusuu0count[i]+=1
    for i in range(length1):
        if a%yakusuu1lst[i]==0:yakusuu1count[i]+=1


div=1
for i in range(length0):
    if yakusuu0count[i]>=N-1 and div<yakusuu0lst[i]:
        div=yakusuu0lst[i]

for i in range(length1):
    if yakusuu1count[i]>=N-1 and div<yakusuu1lst[i]:
        div=yakusuu1lst[i]

print(div)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import fractions
 
 
def main():
    N = int(input())
    A = list(map(int, input().split()))
 
    L_gcds = [0] * N
    L_gcd_tmp = L_gcds[0]
    for i in range(1, N):
        L_gcd_tmp = fractions.gcd(L_gcd_tmp, A[i-1])
        L_gcds[i] = L_gcd_tmp
 
    R_gcds = [0] * N
    R_gcd_tmp = R_gcds[0]
    for j in range(1, N):
        R_gcd_tmp = fractions.gcd(R_gcd_tmp, A[N-j])
        R_gcds[j] = R_gcd_tmp
    R_gcds.reverse()
 
    LR_gcds = [0] * N
    for k in range(0, N):
        LR_gcds[k] = fractions.gcd(L_gcds[k], R_gcds[k])
 
    print(max(LR_gcds))
 
main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
class SegmentTree:
    def segfunc(self,x,y):
        return gcd(x,y)

    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1] = init[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
    
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            lk = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p //= 2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n = onem()

a = l()


ans = 0
p = SegmentTree(n,a,0)
for i in range(n):
    ans = max(ans,gcd(p.query(0,i),p.query(i+1,n)))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A=sorted(list(map(int,input().split())))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
ans = []
gcdlist = [A[0]]
for i in range(1,N):
    gcdlist.append(gcd(gcdlist[i-1],A[i]))
gcdlistr = [A[-1]]
for i in range(N-2,-1,-1):
    gcdlistr.append(gcd(gcdlistr[N-i-2],A[i]))
gcdlistr.reverse()
gcdlist.insert(0,0)
gcdlist.append(0)
gcdlistr.insert(0,0)
gcdlistr.append(0)
for i in range(N):
    ans.append(gcd(gcdlist[i],gcdlistr[i+2]))
print(max(ans))

Submission status: Accepted

Solution code:
#ABC125_C

N=int(input())
A=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)

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

ans=1

if RCD[N-2]>ans:
    ans=RCD[N-2]

for i in range(1,N-1):
    if gcd(LCD[i-1],RCD[N-i-2])>ans:
        ans=gcd(LCD[i-1],RCD[N-i-2])

if LCD[N-2]>ans:
    ans=LCD[N-2]
print(ans)

Submission status: Accepted

Solution code:
import fractions
import math


def gcd(a,b):
    return fractions.gcd(a, b)

# def gcd(a,b):
#     return math.gcd(a,b)

def calculate(arr):
    # L length (N)
    L = [arr[0]]*len(arr)

    # R length (N)
    R = [arr[-1]]*len(arr)

    for i in range(len(arr)):
        if i == 0:
            continue

        L[i] = gcd(L[i-1],arr[i])


        R[len(arr) - (i + 1)] = gcd(R[len(arr) - i],arr[len(arr) - (i + 1)])

    max = 0
    for i in range(len(arr)):

        if i == 0:
            max = R[i+1]

        elif i == len(arr) - 1:
            if max < L[i-1]:
                max = L[i-1]
        else:
            if max < gcd(L[i-1],R[i+1]):
                max = gcd(L[i-1],R[i+1])

    print(max)

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

Submission status: Accepted

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

left = []
right = []
left.append(1)
right.append(1)
left.append(l[0])
right.append(l[-1])
le = l[0]
ri = l[-1]
for i in range(1,n-1):
    le = fractions.gcd(le,l[i])
    left.append(le)
    ri = fractions.gcd(ri,l[-i-1])
    right.append(ri)
m = []
for i in range(1,n-1):
    m.append(fractions.gcd(left[i],right[-i-1]))
m.append(left[-1])
m.append(right[-1])
print(max(m))

Submission status: Accepted

Solution code:

from fractions import gcd

#####segfunc######
#評価関数（という言い方であっている？）
def segfunc(x,y):
    if x==0 or y==0:
        return x+y#0ではない方を返す
    return gcd(x,y)


#初期化
def init(init_val):
    #init_valは操作する数列
    for i in range(N):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
        

#k番目の値をxに更新
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

        
#[p,q)の区間に対するクエリへの応答
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


#####単位元######
ide_ele = 0

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

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num
init(A)

#i番目の要素をのぞいた時のgcd
max_gcd=[0]*N
for i in range(N):
    gcd_l=query(0,i)
    gcd_r=query(i+1,N)
    max_gcd[i]=gcd(gcd_l,gcd_r)
print(max(max_gcd))

Submission status: Accepted

Solution code:
#ABC125C
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
l,r=[0]*(n+1),[0]*(n+1)
for i in range(n):
    l[i+1]=gcd(l[i],a[i])
for i in range(n,0,-1):
    r[i-1]=gcd(r[i],a[i-1])
ans=0
for i in range(n):
    ans=max(ans,gcd(l[i],r[i+1]))
print(ans)

Submission status: Accepted

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


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

    L_gcds = [0] * N
    L_gcd_tmp = L_gcds[0]
    for i in range(1, N):
        L_gcd_tmp = fractions.gcd(L_gcd_tmp, A[i-1])
        L_gcds[i] = L_gcd_tmp

    R_gcds = [0] * N
    R_gcd_tmp = R_gcds[0]
    for j in range(1, N):
        R_gcd_tmp = fractions.gcd(R_gcd_tmp, A[N-j])
        R_gcds[j] = R_gcd_tmp
    R_gcds.reverse()

    LR_gcds = [0] * N
    for k in range(0, N):
        LR_gcds[k] = fractions.gcd(L_gcds[k], R_gcds[k])

    print(max(LR_gcds))

main()

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)
n=int(input())
A=list(map(int,input().split()))
F=[0]*n
B=[0]*n
F[0]=A[0]
B[-1]=A[-1]
for i in range(1, n):
    F[i]=gcd(F[i-1],A[i])
    B[-i]=gcd(B[-(i-1)],A[-i])
ans=[0]*n
ans[0]=B[1]
ans[-1]=F[-2]
for i in range(1,n-1):
    ans[i]=gcd(F[i-1],B[i+1])
print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

n=int(input())
a=[int(i) for i in input().split()]
a1=[a[0]]
for i in range(1,n-1):
    a1.append(gcd(a1[-1],a[i]))
a2=[a[-1]]
for i in range(n-2,0,-1):
    a2.append(gcd(a2[-1],a[i]))
m=[]
for i in range(n-2):
    m.append(gcd(a1[i],a2[-i-2]))
m.append(a1[-1])
m.append(a2[-1])
print(max(m))
#print(a1)
#print(a2)
#print(m)

Submission status: Accepted

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

n = int(input())
a = [int(i) for i in input().split()]
ra = list(reversed(a))
ans = 0
left = [0]*(n+1)
right = [0]*(n+1)

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

right = list(reversed(right))

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

print(ans)

Submission status: Accepted

Solution code:
import fractions as f
n = int(input())
l = [-1]*(n+5)#0-i-1までの最大公約数
r = [-1]*(n+5)#i - n-1の最大公約数
l[0] ,r[n] = 0,0
a = list(map(int,input().split()))
for i in range(n):
    l[i+1] = f.gcd(l[i],a[i])
    i = n-i
    r[i-1] = f.gcd(r[i],a[i-1])
ans = -10**9
for i in range(n):
    
    ans = max(ans,f.gcd(l[i],r[i+1]))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = list(map(int, input().split()))
l_gcd = [None] * N
l_gcd[0] = l[0]


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


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

r_gcd = [None] * N
r_gcd[-1] = l[-1]

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

max_gcd = max(l_gcd[-2], r_gcd[1])

for i in range(1, N-1):
    max_gcd = max(max_gcd, gcd(l_gcd[i-1], r_gcd[i+1]))

print(max_gcd)

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 - 1 - i]))
ans = 0
for i in range(n):
    ans = max(ans,fractions.gcd(left[i],right[i + 1]))
print(ans)

Submission status: Accepted

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

N = int(input())
A = sorted(list(map(int,input().split())))
amin = A[0]
ind = 0
for i in range(1,N):
    a = gcd(amin,A[i])
    if a<amin:
        ind = i
        amin = a
a0 = A[1]
for i in range(2,N):
    a0 = gcd(a0,A[i])
a1 = A[0]
for i in range(2,N):
    a1 = gcd(a1,A[i])
a = A[0]
for i in range(1,N):
    if i != ind:
        a = gcd(a,A[i])
print(max(a0,a1,a))

Submission status: Accepted

Solution code:
from fractions import gcd


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

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

print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b > a:
        tmp = a
        a = b
        b =tmp
    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)]
for i in range(0,N):
    L[i + 1] = gcd(L[i], A[i])
    
R = [0 for i in range(N+1)]
for i in range(N,0,-1):
    R[i-1] = gcd(R[i],A[i-1]) 

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

print(max(ans))

Submission status: Accepted

Solution code:
import sys
from math import sqrt
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    divisor=set()
    for x in range(1,int(sqrt(A[0]))+1):
        if A[0]%x==0:
            divisor.add(x)
            divisor.add(A[0]//x)
    for x in range(1,int(sqrt(A[1]))+1):
        if A[1]%x==0:
            divisor.add(x)
            divisor.add(A[1]//x)
    
    def solve(mid):
        f=False
        for x in A:
            if x%mid:
                if f:
                    return False
                else:
                    f=True
        return True
    
    ans=0
    for d in divisor:
        if solve(d):
            ans=max(ans,d)
    print(ans)
    

if __name__ == '__main__':
    main()

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

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

print(max(M))

Submission status: Accepted

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


def segfunc(x,y):
    return math.gcd(x,y)

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成

init(lst1)
ans = 0
for i in range(n):
    #iをまたいでgcdをsearchしていくことで、iを任意の整数に変えたことになる
    ans = max(ans,math.gcd(query(0,i),query(i+1,n)))
print(ans)

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()))
A.append(0)
A.insert(0,0)
B=[0]
C=[0]
for i in range(n+1):
  B.append(gcd(B[-1],A[i+1]))
  C.append(gcd(C[-1],A[n-i]))
ans=1
for i in range(n):
  c=gcd(B[i],C[n-i-1])
  if c>ans:
    ans=c
print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

def gcd(A,B):
    if B>A:
        A,B = B,A

    if(A%B==0):
        return B
    else:
        return gcd(B,A%B)

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
b,c = [], []
bb,cc = a[0], a[-1]

for i in range(n):
  bb, cc = gcd(bb, a[i]), gcd(cc, a[-i-1])
  b.append(bb)
  c.append(cc)

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

Submission status: Accepted

Solution code:
import fractions
import functools


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

# a_0 ~ a_i の 最大公約数
l_gcd = [0]
l_append = l_gcd.append
# a_i ~ a_n-1 の最大公約数
r_gcd = []
r_append = r_gcd.append

for i, a_i in enumerate(a):
    if i == 0:
        l_append(a_i)
    else:
        l_append(fractions.gcd(a_i, l_gcd[i]))

for i, a_i in enumerate(reversed(a)):
    if i == 0:
        r_append(a_i)
    else:
        r_append(fractions.gcd(a_i, r_gcd[i-1]))
r_gcd.reverse()
r_append(0)

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

Submission status: Accepted

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

import fractions
if N==2:
  print(max(A))
else:
  L=[0]*(N)
  R=[0]*(N)
  L[0]=A[0]
  R[N-1]=A[N-1]
  for i in range(1,N):
    L[i]=fractions.gcd(L[i-1],A[i])
  for i in range(1,N):
    R[N-1-i]=fractions.gcd(R[N-i],A[N-1-i])
  ans=0
  for i in range(1,N-1):
    x=fractions.gcd(L[i-1],R[i+1])
    ans=max(ans,x)

  print(max(ans,L[N-2],R[1]))

Submission status: Accepted

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

import fractions
if N==2:
  print(max(A))
else:
  L=[0]*(N)
  R=[0]*(N)
  L[0]=A[0]
  R[N-1]=A[N-1]
  for i in range(1,N):
    L[i]=fractions.gcd(L[i-1],A[i])
  for i in range(N-1,0,-1):
    R[i-1]=fractions.gcd(R[i],A[i-1])
  ans=0
  for i in range(1,N-1):
    x=fractions.gcd(L[i-1],R[i+1])
    ans=max(ans,x)

  print(max(ans,L[N-2],R[1]))

Submission status: Accepted

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

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

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

#print(s,u)

ans = max(u[-2],s[-2])
for i in range(1,n-1):
    #print(s[i-1],u[-2-i])
    now = gcd(s[i-1],u[-2-i])
    ans = max(ans,now)
print(ans)