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 -*-
"""
Created on Sat Apr 27 20:57:32 2019

@author: Yamazaki Kenichi
"""

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

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

T = [[1,1,1] for i in range(N)]
T[0][0],T[0][1],T[0][2] = A[0], 0, 0
for i in range(1,N):
    T[i][0] = eg(T[i-1][0],A[i])
    T[i][1] = T[i-1][0]
    T[i][2] = max(eg(T[i-1][2],A[i]),eg(T[i-1][1],A[i]))
print(max(T[N-1]))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def gcd(a,b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)
    
n = ni()
a = list(li())
    
gcd_left = [0, a[0]]
gcd_right = [0, a[-1]]

for ai in a[1:]:
    gcd_left.append(gcd(gcd_left[-1], ai))
    
for ai in a[-2::-1]:
    gcd_right.append(gcd(gcd_right[-1], ai))
    
ans = 1

for le, ri in zip(gcd_left[:-1], gcd_right[::-1][1:]):
    if le == 0 or ri == 0:
        ans = max(ans, le, ri)
        
    else:
        ans = max(ans, gcd(le, ri))
        
print(ans)

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y!=0:
        x, y = y, x % y # x,yの大小が逆でも、入れ替わるので、OK
    return x

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

if n == 2:
    print(max(a))

elif n>=3:
    l = [-1] * n
    r = [-1] * n
    l[0] = a[0]  #一番左を左に挿入
    r[-1] = a[-1] #一番右を右に挿入
# print(l)
# print(r)

    for i in range(1, n): #左から最大公約数をn-1回計算していく
        l[i] = gcd(l[i-1], a[i]) # l[0]とa[1]の最大公約数をl[1]に挿入⇒
        # l[1]とa[2]の最大公約数をl[2]に挿入。隣同士素があったら、それ以降右側全て1
    for i in range(n-2, -1, -1): #右から最大公約数を計算していく
        r[i] = gcd(r[i+1], a[i]) # r[n-1]とa[n-2]の最大公約数をr[n-2]に挿入

        # print("l",l) # lはn-1桁のlist
        # print("r",r)

    ans = max(r[1], l[-2]) # rの左から2番目とlの右から2番目の大きい方を、ansに挿入.
        # 右端、左端は、最大公約数ではないため。(元々の数列)

    for i in range(1, n-1): #両端を切り取った中で、lは右側に寄せて、rは左側に寄せているので、
        g = gcd(l[i-1], r[i+1]) #
        ans = max(ans, g)
        # print(i, g, ans)
    print(ans)

Submission status: Accepted

Solution code:
import sys

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

N = int(sys.stdin.readline().strip())
As = list(map(int, sys.stdin.readline().strip().split()))

left = [0] * N
right = [0] * (N+1)

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

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

Submission status: Accepted

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


def gcd(a: int, b: int) -> int:
    while a % b != 0:
        r = a % b
        a = b
        b = r
    return b


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

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

print(ans)

Submission status: Accepted

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


def solve(n, a):
    l = [0] * n
    r = [0] * (n + 1)

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

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


def input_from_console():
    n = int(input())
    a = list(map(int, input().split()))
    return n, a


def main():
    n, a_list = input_from_console()
    print(solve(n, a_list))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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


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

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

    for i in range(n, 0, -1):

        if i == n:
            r[i] = 0
        else:
            r[i] = gcd(r[i+1], a[i])
    m = 0
    for i in range(n):
        # print('m', m)
        m = max(m, gcd(l[i], r[i + 1]))
    return m


def input_from_console():
    n = int(input())
    a = list(map(int, input().split()))
    return n, a


def main():
    n, a_list = input_from_console()
    print(solve(n, a_list))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
aa = list(map(int, input().split()))
front = [0]*N
back = [0]*N
front[0] = aa[0]
back[-1] = aa[-1]
for i in range(1, N):
    front[i] = gcd(front[i-1], aa[i])
    back[-1-i] = gcd(back[-i], aa[-1-i])
ans = back[1]
for i in range(2, N):
    ans = max(gcd(front[i-2], back[i]), ans)
ans = max(front[-2], ans,)
print(ans)

Submission status: Accepted

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

n=int(input())

v=[]
line=input().split()

for i in range(n):
    v.append(int(line[i]))

gcd_l=[]
gcd_r=[]

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

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

gcd_list=[]

for i in range(n):
    if i==0:
        gcd_list.append(gcd_r[n-2])
    elif i==n-1:
        gcd_list.append(gcd_l[n-2])
    else:
#        print(gcd(gcd_l[i-1],gcd_r[n-i-2]))
        gcd_list.append(gcd(gcd_l[i-1],gcd_r[n-i-2]))

#print(gcd_list)

print(max(gcd_list))

Submission status: Accepted

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

param = [[0, 0, 0]]
while True:
    if len(param) <= 0:
        break
    addr, Li, Lv = param.pop()
    if addr == 0:
        if Li == N-1:
            Rv = 0
            M = Lv
            continue            
        param += [[addr+1, Li, Lv], [0, Li+1, gcd(Lv, A[Li])]]
        continue 
    elif addr == 1:
        Rv = gcd(A[Li+1], Rv)
        M = max(M, gcd(Lv, Rv))
        continue

print(M)

Submission status: Accepted

Solution code:
from functools import reduce
import copy

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

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

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

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

ans = 0
for i in range(n):
    lr = gcd(l[i], r[i])
    ans = max(ans, lr)

print(ans)

Submission status: Accepted

Solution code:
from fractions import*
n,*a=map(int,open(0).read().split())
b=[0]
for i in a:b+=gcd(b[-1],i),
w=m=0
for i in range(n):m=max(m,gcd(w,b[-i-2]));w=gcd(w,a[~i])
print(m)

Submission status: Accepted

Solution code:
from fractions import*
n,*a=map(int,open(0).read().split())
*b,=a=a+[0]
r=range(n)
for i in r:a[i]=gcd(a[i],a[i-1]);b[-i-2]=gcd(b[-i-2],b[~i])
print(max(gcd(a[i-1],b[i+1])for i in r))

Submission status: Accepted

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

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

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

C = A.copy()
C.reverse()
for i in range(N - 1):
    C[i + 1] = gcd(C[i], C[i + 1])
C.reverse()

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

Submission status: Accepted

Solution code:
import itertools
import fractions
from functools import reduce

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

L = [0] * n
R = [0] * n

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

val = 1

for i in range(len(a)):
    ret = 0
    if i == 0:
        ret = R[i + 1]
    elif i == n - 1:
        ret = L[i - 1]
    else:
        ret = fractions.gcd(L[i - 1], R[i + 1])

    if ret > val:
       val = ret
        
print(val)

Submission status: Accepted

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


class SegmentTree():
    def __init__(self, array, m, e, size):
        self.m = m  # monoid
        self.e = e  # identity element
        self.size = size  # limit for array size
        self.n = n = len(array)  # array size
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

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

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


gcd = lambda x, y: gcd(y, x) if x < y else x if y == 0 else gcd(y, x % y)
e = 0
size = 10**6
ST = SegmentTree(A, m=gcd, e=e, size=size)

ans = 1
for i, a in enumerate(A):
    ST.modify(i, 0)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)

Submission status: Accepted

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

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

F = copy.copy(A)
B = copy.copy(A)

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

mx = max(F[N-2], B[1])
for i in range(1, N - 1):
  mx = max(mx, gcd(F[i-1], B[i+1]))
print(mx)

Submission status: Accepted

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


class SegmentTree():
    def __init__(self, array, m, e, size):
        self.m = m  # monoid
        self.e = e  # identity element
        self.size = size  # limit for array size
        n = self.n = len(array)
        dat = self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

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

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


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


e = 0
size = 10**6
ST = SegmentTree(A, m=gcd, e=e, size=size)

ans = 1
for i, a in enumerate(A):
    ST.modify(i, 0)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)

Submission status: Accepted

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

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

res = [0] * N
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, 0, -1):
    r[i-1] = gcd(r[i], A[i-1])

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

print(max(res))

Submission status: Accepted

Solution code:
from sys import exit
def gcd(a,b):#greatest common divisor
    if (a<b):
        a,b = b,a
    while(b>0):
        a,b = b ,a%b
    return a
N = int(input())
A = [int(n) for n in input().split()]
straight = [0]*N
straight[0] = gcd(A[0],A[0])
for i in range(1,len(A)):
    straight[i] = gcd(straight[i-1], A[i])

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

back = back[::-1]
# print(straight)
# print(back)
ans = straight[-2]
for i in range(N-2):
    ans = max(ans, gcd(straight[i], back[i+2]))
    # print(straight[i],back[i+2])
    # print(gcd(straight[i], back[i+2]))
ans = max(ans, back[1])
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
def get_result(L, N):
    Gl = [0]*N
    Gr = [0]*N
    Gl[0] = L[0]
    Gr[N-1] = L[N-1]
    for i in range(1, N):
        Gl[i] = gcd(Gl[i-1], L[i])
    for j in range(N-2, -1, -1):
        Gr[j] = gcd(Gr[j+1], L[j])
    #print(Gl, Gr)
    full_gcd = Gr[0]
    result = full_gcd
    for i in range(N):
        if i == 0:
            x = Gr[1]
        elif i == N-1:
            x = Gl[N-2]
        else:
            x = gcd(Gl[i-1], Gr[i+1])
        if x > full_gcd:
            result = max(result, x)
    return result



N = int(input())
L = [int(s) for s in input().split(" ")]
result = get_result(L, N)
print(result )

Submission status: Accepted

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


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


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

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

print(ans)

Submission status: Accepted

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


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


class SegmentTree():
    def m(self, v1, v2):  # ***monoid***
        return gcd(v1, v2)

    def __init__(self, array):
        m = self.m
        e = self.e = 0  # ***identity element***
        size = self.size = 10**5  # ***limit for array size***
        n = self.n = len(array)
        dat = self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

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

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


ST = SegmentTree(A)
ans = 0
for i, a in enumerate(A):
    ST.modify(i, ST.e)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = [A[0]]
    R = [A[-1]]
    for i in range(1, N - 1):
        L.append(gcd(L[-1], A[i]))
    for j in range(N - 2, 0, -1):
        R.append(gcd(R[-1], A[j]))
    ans = R[-1]
    for k in range(1, N - 1):
        ans = max(ans, gcd(L[k - 1], R[N - 2 - k]))
    print(max(ans, L[-1]))
    
main()

Submission status: Accepted

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    L = [A[0]]
    R = [A[-1]]
    for i in range(1, N - 1):
        L.append(gcd(L[-1], A[i]))
    for j in range(N - 2, 0, -1):
        R.append(gcd(R[-1], A[j]))
    ans = R[-1]
    for k in range(1, N - 1):
        ans = max(ans, gcd(L[k - 1], R[N - 2 - k]))
    print(max(ans, L[-1]))
    
main()

Submission status: Accepted

Solution code:
from fractions import*
N,*A=map(int,open(0).read().split())
B=[0]
a=range(N)
for x in a:B+=[gcd(B[-1],A[x])]
w=M=0
for x in a[::-1]:M=max(M,gcd(w,B[x]));w=gcd(w,A[x])
print(M)

Submission status: Accepted

Solution code:
from fractions import*
N,*A=map(int,open(0).read().split())
w,B=0,[0]
a=range(N)
for x in a[:]:B+=[gcd(B[-1],A[x])]
w=M=0
for x in a[::-1]:M,w=max(M,gcd(w,B[x])),gcd(w,A[x])
print(M)

Submission status: Accepted

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

def gcd(x, y):
    if x == 0 or y == 0:
        return max(x, y)
    return gcd(y, x % y) if y!=0 else x

w = 0
B = [w]
for x in range(N-1, 0, -1):
    B += [gcd(B[-1], A[x])]

w = 0
M = 0
for x in range(N):
    M = max(M, gcd(w, B.pop()))
    w = gcd(w, A[x])

print(M)

Submission status: Accepted

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

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

gcd_forward = [numbers[0]]
for i in range(1, N - 1):
  gcd_all = gcd(gcd_forward[-1], numbers[i])
  gcd_forward.append(gcd_all)

gcd_backward = [numbers[-1]]
for i in range(N - 2, 0, -1):
  gcd_all = gcd(gcd_backward[-1], numbers[i])
  gcd_backward.append(gcd_all)

gcd_max = 1
for i in range(N):
  gcd_temp = 1
  if (i == 0):
    gcd_temp = gcd_backward[-1]
  elif (i == N - 1):
    gcd_temp = gcd_forward[-1]
  else:
    gcd_temp = gcd(gcd_forward[i - 1], gcd_backward[N - 2 - i])
  gcd_max = max(gcd_max, gcd_temp)
  
print(gcd_max)

Submission status: Accepted

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

def gcd(x, y):
    if x == 0 or y == 0:
        return max(x, y)
    return gcd(y, x % y) if y!=0 else x

def F(init, add):
    w = [0]
    for i in range(init, init + add * N, add):
        w += [gcd(w[-1], A[i])]
    return w[:-1]

print(max(map(lambda x,y:gcd(x,y), F(0, 1), F(N-1, -1)[::-1])))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import Counter
import collections
INF = float("inf")


def factorial(n):
    # 試し割りによる素因数分解
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


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


def GCDs(*a):
    # リストで入力しないよう注意。
    if len(a) == 0:
        return -1  # エラー

    if len(a) == 1:
        return a[0]

    res = a[0]
    for i in range(1, len(a)):
        res = GCD(res, a[i])
    return res


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def solve(N: int, A: "List[int]"):

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

    buf = []
    for i in range(N):
        buf.append(GCD(asc[i], desc[N-i-1]))
    print(max(buf))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
### C

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

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

left = [0] * (N+1)
right = [0] *(N+1)

for i in range(N):
    left[i+1] = gcd(A[i], left[i])
for i in reversed(range(N)):
    right[i] = gcd(A[i], right[i+1])
    
res = 0
for i in range(N):
    l = left[i]
    r = right[i+1]
    res = max(gcd(l, r), res)

print(res)

Submission status: Accepted

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

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

param = [[0, 0, 0]]
addr = 0
while True:
    if len(param) <= 0:
        break
    addr, Li, Lv = param.pop()
    if addr == 0:
        if Li == N-1:
            Rv = 0
            M, isCall = Lv, False
            continue            
        param += [[1, Li, Lv], [0, Li+1, gcd(Lv, A[Li])]]
        isCall = True
        continue 
    elif addr == 1:
        Rv = gcd(A[Li+1], Rv)
        M, isCall = max(M, gcd(Lv, Rv)), False
        continue

print(M)

Submission status: Accepted

Solution code:
# @profile
def main():
    import math

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

    # N=5
    # a = [12,15,18,36,42]

    # N = 10**5
    # a = [1]*N

    # N=11
    # a = [56,58,82,46,67,36,98,68,24,46,52]

    #a,bの最大公約数
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    # 一番近い大きい側の2の累乗の数が，segtreeの葉の数になる．
    N_ADJUST = 2**int(math.ceil(math.log(N)/math.log(2)))
    # segtreeのサイズはN_ADJUSTを葉とする木のノード数．
    ST_SIZE = N_ADJUST*2-1
    # binopに合わせて単位元として決める．maxならINT_MAX(問題文の制限)
    INT_IDENTITY = 0
    li = [INT_IDENTITY]*ST_SIZE
    # li_initは，葉の配列．
    # 節点kが [l,r) にbinopという演算で結びついている．
    def init_segtree(li, k, l, r, binop, li_init):
        if r-l==1:
            li[k] = INT_IDENTITY if l >= len(li_init) else li_init[l]
        elif r-l>1:
            k_l, k_r = k*2+1, k*2+2
            init_segtree(li, k_l, l, (l+r)//2, binop, li_init)
            init_segtree(li, k_r, (l+r)//2, r, binop, li_init)
            li[k] = binop(li[k_l],li[k_r])

    init_segtree(li,0,0,N_ADJUST,gcd,a)

    # print(li)
    # 下からupdateする．
    def update_segtree(li,k,binop):
        if k > 0:
            k_2 = (k-1)//2
            k_l = k_2*2+1
            k_r = k_l+1
            li[k_2] = binop(li[k_l],li[k_r])
            update_segtree(li,k_2,binop)

    val = []
    for i in range(N_ADJUST-1,N_ADJUST+N-1):
        tmp = li[i]
        li[i] = 0
        update_segtree(li,i,gcd)
        # print(i, li)
        val.append(li[0])
        li[i] = tmp
        update_segtree(li,i,gcd)

    print(max(val))

main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
 
 
def gcd(x,y):
    while y:
        x,y = y, x % y
    return x
    
gcd_left = [0]
gcd_rigth = [0]
gcd_list = []

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

for i in range(n):
    v = gcd(gcd_left[i], gcd_rigth[n-1-i])
    gcd_list.append(v)

print(max(gcd_list))

Submission status: Accepted

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

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

left = [0] * (n+1)
for i, item in enumerate(a):
    left[i+1] = gcd( left[i], item )

right = [0] * (n+1)

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

ans = -1

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

N=int(input())
A=[i for i in map(int,input().split())]

ans=[]
L={}
L[0]=0
R={}
R[N+1]=0
R[N+2]=0

def gcd2(x,a):
    if x==0:
        return a
    else:
        return gcd(x,a)

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

for i in range(N):
    ans.append(gcd2(L[i],R[i+2]))
print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
l = [0]*N
r = [0]*N
gcds = [0]*N
def gcd(a,b):
    if (a < b):
        a,b = b,a
    if (b == 0):
        return a
    return gcd(b, a%b)

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

for i in range(N):
    if i == 0:
        gcds.append(gcd(0,r[i+1]))
    elif i == N-1:
        gcds.append(gcd(0,l[i-1]))
    else:
        gcds.append(gcd(l[i-1],r[i+1]))
print(max(gcds))

Submission status: Accepted

Solution code:
#3.7.3 -> import math
from fractions import gcd

# [0,--list--,0]
N = int(input())
A = [0]+list(map(int,input().split()))+[0]
L = [0]*(N+2)
R = [0]*(N+2)
#0,A[1]->L[i-1],A[i]->L[N-1],A[N]
for i in range(1,N+1):
    L[i] =gcd(L[i-1],A[i])
#0,A[N]->R[i+1],A[i]->R[2],A[1]
for i in range(N,0,-1):
    R[i] = gcd(R[i+1],A[i])
#A[i]を含めないL,Rのgcdをすべて並べてmaxをとる
print(max(gcd(L[i-1],R[i+1]) for i in range(1,N+1)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

print(max(result))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# import math
import fractions
import numpy as np
from itertools import accumulate, chain, islice, starmap
N = int(input())
numbers = list(map(int, input().split()))
# numbers = [2, 4, 8, 8]
# N = len(numbers)


def calculate_maximum_subgcd_with_np_ufunc(numbers):
    gcd = np.frompyfunc(fractions.gcd, 2, 1)
    cumgcds = gcd.accumulate(numbers, dtype=np.object).astype(np.int)
    sub_cumgcds = np.roll(cumgcds, 1)
    sub_cumgcds[0] = 0
    reverse_cumgcds = gcd.accumulate(
        numbers[::-1], dtype=np.object).astype(np.int)
    sub_reverse_cumgcds = np.roll(reverse_cumgcds, 1)
    sub_reverse_cumgcds[0] = 0
    return np.max(gcd(sub_cumgcds, sub_reverse_cumgcds[::-1]))


def calculate_maximum_subgcd_with_func(numbers):
    operation = fractions.gcd
    cumgcds = accumulate(numbers, operation)
    sub_cumgcds = islice(chain([0], cumgcds), len(numbers))
    reverse_cumgcds = accumulate(numbers[::-1], operation)
    sub_reverse_cumgcds = islice(chain([0], reverse_cumgcds), len(numbers))
    sub_gcds = starmap(operation, zip(sub_cumgcds, list(sub_reverse_cumgcds)[::-1]))
    return max(sub_gcds)


calculate_maximum_subgcd = calculate_maximum_subgcd_with_np_ufunc
# calculate_maximum_subgcd = calculate_maximum_subgcd_with_func

print(calculate_maximum_subgcd(numbers))

Submission status: Accepted

Solution code:
# import math
import fractions
import numpy as np
from itertools import accumulate, chain, islice, starmap
N = int(input())
numbers = list(map(int, input().split()))
# numbers = [2, 4, 8, 8]
# N = len(numbers)


def calculate_maximum_subgcd_with_np_ufunc(numbers):
    gcd = np.frompyfunc(fractions.gcd, 2, 1)
    cumgcds = gcd.accumulate(numbers, dtype=np.object).astype(np.int)
    sub_cumgcds = np.roll(cumgcds, 1)
    sub_cumgcds[0] = 0
    reverse_cumgcds = gcd.accumulate(
        numbers[::-1], dtype=np.object).astype(np.int)
    sub_reverse_cumgcds = np.roll(reverse_cumgcds, 1)
    sub_reverse_cumgcds[0] = 0
    return np.max(gcd(sub_cumgcds, sub_reverse_cumgcds[::-1]))


def calculate_maximum_subgcd_with_func(numbers):
    operation = fractions.gcd
    cumgcds = accumulate(numbers, operation)
    sub_cumgcds = islice(chain([0], cumgcds), len(numbers))
    reverse_cumgcds = accumulate(numbers[::-1], operation)
    sub_reverse_cumgcds = islice(chain([0], reverse_cumgcds), len(numbers))
    sub_gcds = starmap(operation, zip(sub_cumgcds, list(sub_reverse_cumgcds)[::-1]))
    return max(sub_gcds)


# calculate_maximum_subgcd = calculate_maximum_subgcd_with_np_ufunc
calculate_maximum_subgcd = calculate_maximum_subgcd_with_func

print(calculate_maximum_subgcd(numbers))

Submission status: Accepted

Solution code:
def gcd_(a,b):
    if a<b:    a,b=b,a
    if b==0:    return a
    return gcd_(b,a%b)
  
def gcd(l):
    ans=l[0]
    for i in l:
        ans=gcd_(ans,i)
    return ans


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

gcd_list=[A[0]]
rev_gcd_list=[A[-1]]

for i in range(1,N):
    gcd_list.append(gcd([gcd_list[-1],A[i]]))
    rev_gcd_list.append(gcd([rev_gcd_list[-1],A[-i-1]]))
rev_gcd_list=rev_gcd_list[::-1]

ans=max(gcd_list[N-2],rev_gcd_list[1])
for i in range(1,N-1):
    ans=max(ans,gcd([gcd_list[i-1],rev_gcd_list[i+1]]))
print(ans)

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    def build() :
        for k in range(N0-2,-1,-1) :
            data[k]=gcd(data[2*k+1],data[2*k+2]) 
            
    def update(k,x):
        k+=N0-1
        data[k]=x
        while k+1:
            k=~-k//2
            data[k]=gcd(data[2*k+1],data[2*k+2])
    def query(l,r):
        L,R=l+N0,r+N0
        s=0
        while L<R:
            if R&1:
                R-=1
                s=gcd(s,data[R-1])
            if L&1:
                s=gcd(s,data[L-1])
                L+=1
            L>>=1
            R>>=1
        return s
    n,*a=map(int,open(0).read().split())
    N0=2**(n-1).bit_length()
    data=[0]*2*N0
    for i in range(n):
        data[i + N0 - 1] = a[i]
    build()
    print(max(gcd(query(0,i),query(i+1,n))for i in range(n)))
if __name__=='__main__':
    main()