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:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections,math,fractions
sys.setrecursionlimit(1000000)
INF = float("inf")

N = int(sys.stdin.readline())
A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
#3 8 9 10 11 12
left = [A[0]]*(N)
for i in range(1,N):
    left[i] = fractions.gcd(left[i-1],A[i])

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

#print(left,right)

ret = -INF
for i in range(N):
    if i-1 >= 0 and i+1 < N:
        a = fractions.gcd(left[i-1],right[i+1])
    elif i-1 >= 0:
        a = left[i-1]
    else:
        a = right[i+1]
    ret = max(ret,a)
print(ret)

Submission status: Accepted

Solution code:
# セグメント木。区間における要素の取得をO(logN)で行うことが可能である。
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)

        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]

        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res


#gcd on blackboard
#セグ木（区間gcd) verify
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
seg=SegTree(A,gcd,0)
ans=1
for i in range(-1,N):
    v=gcd(seg.query(0,i),seg.query(i+1,N))
    ans=max(v,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

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

N = ii()
A = li()

forward = [0]*(N+1)
backward = [0]*(N+1)

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

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

#print(forward)
#print(backward)
ans = 0
for i in range(N):
    #print(forward[i], forward[N-1-i], ans)
    ans = max(ans, gcd(forward[i], backward[N-1-i]))

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
from functools import reduce

def segfunc(a,b):
    if a == 0 or b == 0:
        return max(a, b)
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return segfunc(b, r)

def gcd_list(numbers):
    return reduce(segfunc, numbers)

def init(init_val):
    #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):
    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):
    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


n = ii()
#A = sorted(li())
A = li()

#####単位元######
'''
if n == 2:
    print(max(A))
    exit()
elif n == 3:
    ide_ele = max(segfunc(A[0], A[1]), segfunc(A[1], A[2]), segfunc(A[0], A[2]))
else:
    #ide_ele = max(segfunc(A[-1], A[-2]), segfunc(A[-3], A[-4]))
    ide_ele = max(segfunc(A[0], A[1]), segfunc(A[2], A[3]))
    print(segfunc(A[0], A[1]), segfunc(A[2], A[3]))
'''
ide_ele = 0
#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(A)
ans = 0

#ans = max(query(1, n), ans)
#for i in range(1, n-1):
for i in range(n):
    #print(i, query(0, i), query(i+1, n))
    ans = max(segfunc(query(0, i), query(i+1, n)), ans)
#ans = max(query(0, n-1), ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
from functools import reduce

def segfunc(a,b):
    if a == 0 or b == 0:
        return 0
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return segfunc(b, r)

def gcd_list(numbers):
    return reduce(segfunc, numbers)

def init(init_val):
    #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):
    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):
    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


n = ii()
A = sorted(li())

#####単位元######
if n == 2:
    print(max(A))
    exit()
elif n == 3:
    ide_ele = max(segfunc(A[0], A[1]), segfunc(A[1], A[2]), segfunc(A[0], A[2]))
else:
    ide_ele = max(segfunc(A[-1], A[-2]), segfunc(A[-3], A[-4]))

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

init(A)
ans = 0

#ans = max(query(1, n), ans)
#for i in range(1, n-1):
for i in range(n):
    #print(i, query(0, i), query(i+1, n))
    ans = max(segfunc(query(0, i), query(i+1, n)), ans)
#ans = max(query(0, n-1), ans)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1
    return pf_cnt


def main():
    n = int(input())
    al = list(map(int, input().split()))

    gcd_l = [1]*n
    gcd_r = [1]*n

    gcd_l[0] = al[0]
    gcd_r[-1] = al[-1]

    for i in range(1,n):
        next_l = al[i]
        gcd_l[i] = gcd(next_l, gcd_l[i-1])

        next_r = al[n-i-1]
        gcd_r[n-i-1] = gcd(next_r, gcd_r[n-i])


    ans = max(gcd_r[1], gcd_l[n-2])
    for i in range(1,n-1):
        curr_gcd = gcd(gcd_l[i-1], gcd_r[i+1])
        ans = max(ans, curr_gcd)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(sorted((map(int, readline().split()))))

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

L = [0] * (N)
R = [0] * (N)
L[0] = A[0]
R[N - 1] = A[N - 1]

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

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from fractions import gcd

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

cum_gcd = list(accumulate(As, gcd))
cum_rev_gcd = list(accumulate(reversed(As), gcd))[::-1]

max_gcd = max(cum_gcd[-2], cum_rev_gcd[1])
for without in range(1, N-1):
    max_gcd = max(max_gcd, gcd(cum_gcd[without-1], cum_rev_gcd[without+1]))

print(max_gcd)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()

from fractions import gcd

L = [0]*N  # L[i] = A[0]からA[i]までの最大公約数
R = [0]*N  # R[i] = A[i]からA[N-1]までの最大公約数

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

a = max(L[N-2],R[1])

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

Submission status: Accepted

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


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


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

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

ans = max(L[-2], R[1])
# i番目を使わない
for i in range(1, n-1):
    x = gcd(L[i-1], R[i+1])
    if ans < x:
        ans = x
print(ans)

Submission status: Accepted

Solution code:
# Segment Tree
class Segment:
    def __init__(self, N, init_val):
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.dat = [identity_element]*(2*self.N0)
        # 値を代入
        for i in range(N):
            self.dat[i+self.N0-1]=init_val[i]    
        # 構築
        for i in range(self.N0-2,-1,-1) :
            self.dat[i]=segfunc(self.dat[2*i+1],self.dat[2*i+2]) 

    # k番目の要素の値をxに変更
    def update(self, k, x):
        k += self.N0-1
        self.dat[k] = x
        while k >= 0:
            k = (k-1)//2
            self.dat[k] = segfunc(self.dat[2*k+1], self.dat[2*k+2])

    # 区間[l, r)のsegfuncを求める
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = identity_element
        # 区間を列挙しながらsegfuncを求める
        while L < R:
            if R & 1:
                R -= 1
                s = segfunc(s, self.dat[R-1])
            if L & 1:
                s = segfunc(s, self.dat[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

# segfunc : min, +, *, xor, gcd
# identity_element : 単位元(min:inf, 和:0, 積:1, xor:0, gcd:0)

from fractions import gcd
def segfunc(x,y):
    return gcd(x,y) # 変える
identity_element = 0 # 変える

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

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

Submission status: Accepted

Solution code:
# Segment Tree
class Segment:
    def __init__(self, N, init_val):
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.dat = [identity_element]*(2*self.N0)
        # 値を代入
        for i in range(N):
            self.dat[i+self.N0-1]=init_val[i]    
        # 構築
        for i in range(self.N0-2,-1,-1) :
            self.dat[i]=segfunc(self.dat[2*i+1],self.dat[2*i+2]) 

    # k番目の要素の値をxに変更
    def update(self, k, x):
        k += self.N0-1
        self.dat[k] = x
        while k >= 0:
            k = (k-1)//2
            self.dat[k] = segfunc(self.dat[2*k+1], self.dat[2*k+2])

    # 区間[l, r)のsegfuncを求める
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = identity_element
        # 区間を列挙しながらsegfuncを求める
        while L < R:
            if R & 1:
                R -= 1
                s = segfunc(s, self.dat[R-1])
            if L & 1:
                s = segfunc(s, self.dat[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

# segfunc : min, +, *, xor, gcd
# identity_element : 単位元(min:inf, 和:0, 積:1, xor:0, gcd:0)

from fractions import gcd
def segfunc(x,y):
    return gcd(x,y) # 変える
identity_element = 0 # 変える

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

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

Submission status: Accepted

Solution code:
# Segment Tree
class Segment:
    def __init__(self, N, init_val):
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.dat = [identity_element]*(2*self.N0)
        # 値を代入
        for i in range(N):
            self.dat[i+self.N0-1]=init_val[i]    
        # 構築
        for i in range(self.N0-2,-1,-1) :
            self.dat[i]=segfunc(self.dat[2*i+1],self.dat[2*i+2]) 

    # k番目の要素の値をxに変更
    def update(self, k, x):
        k += self.N0-1
        self.dat[k] = x
        while k >= 0:
            k = (k-1)//2
            self.dat[k] = segfunc(self.dat[2*k+1], self.dat[2*k+2])

    # 区間[l, r)のsegfuncを求める
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = identity_element
        # 区間を列挙しながらsegfuncを求める
        while L < R:
            if R & 1:
                R -= 1
                s = segfunc(s, self.dat[R-1])
            if L & 1:
                s = segfunc(s, self.dat[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

# segfunc : min, +, *, xor, gcd
# identity_element : 単位元(min:inf, 和:0, 積:1, xor:0, gcd:0)

from fractions import gcd
def segfunc(x,y):
    return gcd(x,y) # 変える
identity_element = 0 # 変える

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
sf = [a[0]] * n
for i in range(1, n):
    sf[i] = gcd(sf[i - 1], a[i])
sb = [a[n - 1]] * n
for i in range(n - 2, -1, -1):
    sb[i] = gcd(sb[i + 1], a[i])
ans = 1
for i in range(n):
    if i == 0:
        ans = max(ans, sb[1])
    elif i == n - 1:
        ans = max(ans, sf[n - 2])
    else:
        ans = max(ans, gcd(sf[i - 1], sb[i + 1]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions
input = lambda: sys.stdin.readline().rstrip()

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


def solve():

    gcd_f = [0] * N
    gcd_b = [0] * N

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

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

    ans = gcd_f[-2]
    ans = max(ans, gcd_b[-2])

    # print(gcd_f)
    # print(gcd_b)

    for i in range(N - 2):
        t = fractions.gcd(gcd_f[i], gcd_b[-3 - i])
        #print(gcd_f[i], gcd_b[- 3 - i])
        ans = max(ans, t)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

import fractions

L = [A[0]]
R = [A[-1]]

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

R.reverse()


ans = 0

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
def gcd(x, y):
    x, y = max(x, y), min(x, y)
    while y:
        x, y = y, x % y
    return x
for i in range(n):
    if i == 0:
        l[0] = a[0]
    else:
        l[i] = gcd(l[i-1], a[i])
    j = n - 1 - i
    if j == n - 1:
        r[n-1] = a[n-1]
    else:
        r[j] = gcd(r[j+1], a[j])
m = [0 for _ in range(n)]
for i in range(n):
    if i == 0:
        m[0] = r[1]
    elif i == n - 1:
        m[n-1] = l[n-2]
    else:
        m[i] = gcd(l[i-1], r[i+1])
print(max(m))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


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


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))

    l = [0] * (n - 1)
    r = [0] * (n - 1)
    l[0] = a[0]
    r[-1] = a[-1]

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

    ans = 0
    for i in range(n):
        if i == 0:
            ans = max(ans, r[i])
        elif i == n - 1:
            ans = max(ans, l[i - 1])
        else:
            ans = max(ans, gcd(l[i - 1], r[i]))

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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

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

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

ans = right_gcd[n-1]
for i in range(n):
    ans = max(ans,gcd(left_gcd[i],right_gcd[n-1-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

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


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

ans = right_gcd[n-1]
for i in range(n):
    ans = max(ans,gcd(left_gcd[i],right_gcd[n-1-i]))

print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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

# i番目を書き換えたgcdでは左からi-1番目までと、
# 右からi+1番目までのgcdのgcd

l = [0 for _ in range(N+1)]
tmp = 0
for i in range(N):
	tmp = gcd(tmp, A[i])
	l[i+1] = tmp

r = [0 for _ in range(N+1)]
A = A[::-1]
tmp = 0
for i in range(N):
	tmp = gcd(tmp, A[i])
	r[N-i-1] = tmp
 
m = [gcd(l[i], r[i+1]) for i in range(N)]
print(max(m))

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
al=[]
ar=[]
tmp=a[0]
al.append(a[0])
for ai in a[1:]:
  tmp=gcd(ai,tmp)
  al.append(tmp)
ar.append(a[-1])
tmp=a[-1]
for ai in a[:-1][::-1]:
  tmp=gcd(ai,tmp)
  ar.append(tmp)
ans=ar[n-2]
for i in range(n-1):
  ans=max(ans,gcd(al[i],ar[n-i-3]))
ans=max(ans,al[n-2])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
from collections import defaultdict
d=defaultdict(int)
op=set(make_divisors(a[0])+make_divisors(a[1]))
next_op=set()
for i in range(n):
    for opi in op:
        if a[i]%opi==0:
            d[opi]+=1
        if d[opi]>=i:
            next_op.add(opi)
    op=next_op
    next_op=set()
print(max(op))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

n = int(input())
a = list(map(int, input().split()))
b = a[::-1]

left = [0, a[0]]
right = [0, b[0]]
l = a[0]
r = b[0]
for i in range(1, n):
    l = fractions.gcd(l, a[i])
    r = fractions.gcd(r, b[i])
    left.append(l)
    right.append(r)

gcd_max = 0
for i in range(n+1):
    gcd_tmp = fractions.gcd(left[i], right[n-i-1])
    if gcd_tmp > gcd_max:
        gcd_max = gcd_tmp

print(gcd_max)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
aa = tuple(map(int, input().split()))

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

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

ans = 1
for i in range(n):
    if i == 0:
        x = gcdr[1]
    elif i == n - 1:
        x = gcdl[n - 2]
    else:
        x = gcd(gcdl[i - 1], gcdr[i + 1])
    ans = max(ans, x)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd as m_gcd

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


def gcd(a, b):
    if a == 0 or b == 0:
        return max(a, b)
    return m_gcd(a, b)


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

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

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

print(max(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

from fractions import gcd

def solve():
    N = II()
    A = LI()

    # 左から累積和的gcd
    L = [1] * N
    L[0] = A[0]
    for i in range(1, N):
        L[i] = gcd(A[i], L[i-1])

    # 右から累積和的gcd
    R = [1] * N
    R[-1] = A[-1]
    for i in range(N-2, -1, -1):
        R[i] = gcd(A[i], R[i+1])

    # print(L)
    # print(R)
    ans = 1
    for i, a in enumerate(A):
        l = i - 1
        r = i + 1
        if l < 0:
            ans = max(ans, R[r])
        elif r >= N:
            ans = max(ans, L[l])
        else:
            ans = max(ans, gcd(L[l], R[r]))
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
"""
あるn以外の最大公約数が, 最大になる組み合わせ
7 6 8 -> gcd(7,6)=1, gcd(6,8)=2 gcd(7,8)=1
12 15 18 -> gcd(12,15)=3, gcd(15,18)=3, gcd(12, 18)=6
1 2 4 6 -> 2,4,6のやつがでかい
"""
l = [0 for _ in range(n+1)]
tmp = 0
for i in range(n):
	tmp = gcd(tmp, a[i])
	l[i+1] = tmp
r = [0 for _ in range(n+1)]
a = a[::-1]
tmp = 0
for i in range(n):
	tmp = gcd(tmp, a[i])
	r[n-i-1] = tmp

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

Submission status: Accepted

Solution code:
import sys
# from math import gcd
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
pref,suf = [0]*(n+2),[0]*(n+2)
pref[1] = a[0]
for i in range(2,n+1):
    pref[i] = gcd(pref[i-1],a[i-1])
suf[n] = a[n-1]
for i in range(n-1,0,-1):
    suf[i] = gcd(suf[i+1],a[i-1])
ans = max(suf[2],pref[n-1])
for i in range(2,n):
    ans = max(ans,gcd(pref[i-1],suf[i+1]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N = NI()
    A = NLI()
    LA = [1] * N
    RA = [1] * N
    for i in range(N):
        if i == 0:
            LA[0] = A[0]
            RA[N-1] = A[N-1]
            continue
        LA[i] = gcd(LA[i-1], A[i])
        RA[N-i-1] = gcd(RA[N-i], A[N-i-1])
    ans = 0
    for i in range(N):
        if i == 0:
            ans = RA[1]
            continue
        if i == N-1:
            ans = max(ans, LA[N-2])
            continue
        ans = max(ans, gcd(LA[i-1], RA[i+1]))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc125/tasks/abc125_c

def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline

    def init(init_val):
        #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]=gcd(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = gcd(seg[k*2+1],seg[k*2+2])
        
    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 = gcd(res,seg[p])
            if q&1 == 1:
                res = gcd(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = gcd(res,seg[p])
        else:
            res = gcd(gcd(res,seg[p]),seg[q])
        return res

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

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

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

    ans = -1
    for i in range(n):
        ans = max(ans,gcd(query(0,i),query(i+1,n)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import deque
n = int(input())
a = list(map(int, input().split()))
l = [0]
r = deque([0])
g = []
for i in range(n):
    l.append(gcd(l[i], a[i]))
    r.appendleft(gcd(r[-(i + 1)], a[-(i + 1)]))
r = list(r)

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

Submission status: Accepted

Solution code:
from fractions import gcd
#####segfunc#####
def segfunc(x, y):
    return gcd(x,y)
#################

#####ide_ele#####
ide_ele =0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
        
n=int(input())
a=list(map(int, input().split()))

seg=SegTree(a,segfunc,ide_ele)
ans=-1
for i in range(n):
    ans=max(ans, gcd(seg.query(0,i), seg.query(i+1,n)))
print(ans)