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

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

ans = 0
for i in range(1, N + 1): # 抜かすやつのindex
    if i == 1:
        ans = max(ans, gcd_from_right[N - i])
    elif i == N:
        ans = max(ans, gcd_from_left[i - 1])
    else:
        ans = max(ans, gcd(gcd_from_left[i - 1], gcd_from_right[N - i]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

my_gcd = reduce(gcd, A)
A = [a // my_gcd for a in A]

flag = False
my_gcd_2 = 0
my_gcd_3 = 0

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)

    return divisors

for i in range(N):
    a = A[i]
    if my_gcd_2 == 0:
        my_gcd_2 = a
    else:
        if gcd(my_gcd_2, a) == 1:
            if flag is False:
                if i == 1:
                    my_gcd_3 = a
                else:
                    divisors = make_divisors(a)
                    for d in divisors[::-1]:
                        if len([j for j in A[:i] if j % d]) == 1:
                            my_gcd_3 = d
                            break
                flag = True
                continue
            else:
                my_gcd_2 = -1
        if my_gcd_3 and gcd(my_gcd_3, a) == 1:
            my_gcd_3 = -1
        if my_gcd_2:
            my_gcd_2 = gcd(my_gcd_2, a)
        if my_gcd_3:
            my_gcd_3 = gcd(my_gcd_3, a)

else:
    ans_1 = my_gcd * my_gcd_2
    ans_2 = my_gcd * my_gcd_3
    print(max(ans_1, ans_2, my_gcd))

Submission status: Accepted

Solution code:
import fractions
def GCD(a, b):
    if a * b == 0:
        return a + b
    return fractions.gcd(a, b)

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
A = nl()
assert len(A) == N


def solve():
    al = [None] * N
    ar = [None] * N
    al[0] = A[0]
    ar[-1] = A[-1]
    for i in range(1, N):
        al[i] = gcd(al[i - 1], A[i])
        ar[N - 1 - i] = gcd(ar[N - i], A[N - 1 - i])
    gmax = max(al[-2], ar[1])
    gmi = 0 if gmax == ar[1] else N - 1
    for i in range(1, N - 1):
        g = gcd(al[i - 1], ar[i + 1])
        if gmax < g:
            gmax = g
            gmi = i
    return gmax


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from fractions import gcd

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

m = 0

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

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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(reverse=True)
    return divisors
#print(make_divisors(10))
n=I()
lis=sorted(LI())
u=make_divisors(lis[0])

for j in range(len(u)):
    br=u[j]
    count=0
    #print(br)
    for i in range(n):
        if lis[i]%br!=0:
            count+=1
    if count<=1:
        ans1=br
        break
#print(ans1)

v=make_divisors(lis[1])

for j in range(len(v)):
    bre=v[j]
    counti=0
    #print(bre)
    for i in range(n):
        if lis[i]%bre!=0:
            counti+=1
    if counti<=1:
        ans2=bre
        break
#print(ans2)
print(max(ans1,ans2))

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    left = [A[0]]
    right = [A[-1]]
    for i in range(1, N - 1):
        left.append(gcd(left[-1], A[i]))
        right.append(gcd(right[-1], A[N - i - 1]))
    answer = max(left[-1], right[-1])
    for i in range(N - 2):
        g = gcd(left[i], right[N - 3 - i])
        if answer < g:
            answer = g
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    # i番目から左の全ての要素のGCD
    gcd_from_left = [None] * N
    gcd_from_left[0] = A[0]
    # i番目から右の全ての要素のGCD
    gcd_from_right = [None] * N
    gcd_from_right[-1] = A[-1]

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

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

    gcd_from_right.sort()

    # 要素iを取り除いたときの最大公約数
    ans = max(gcd_from_left[-2], gcd_from_right[1])
    for i in range(1, N - 1):
        tmp = gcd(gcd_from_right[i + 1], gcd_from_left[i - 1])
        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    gcd_before_dp = [L[0]] * n   # dp[i] = L[0] ... L[i] たちの gcd
    gcd_after_dp = [L[-1]] * n    # dp[i] = L[i] ... L[n-1] たちの gcd
    
    g = L[0]
    for i in range(1, n):
        g = gcd(g, L[i])
        gcd_before_dp[i] = g
    g = L[-1]
    for i in range(n-2, -1, -1):
        g = gcd(g, L[i])
        gcd_after_dp[i] = g

    ans = 0
    for i in range(n):
        # L[i] をスキップする。L[0]...L[i-1] の gcd と L[i+1]...L[n-1] の gcd がわかれば OK
        if i == 0:
            ans = max(ans, gcd_after_dp[i+1])
        elif i == n - 1:
            ans = max(ans, gcd_before_dp[i-1])
        else:
            ans = max(ans, gcd(gcd_before_dp[i-1], gcd_after_dp[i+1]))
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

from fractions import gcd
import math

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

mx = 0
for i in range(n):
    cd = gcd(llis[i],rlis[n-i-1])
    mx = max(mx,cd)

print(mx)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
from fractions import gcd

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    dp = [[0,0] for _ in range(N-1)]
    dp[0] = [A[0],A[1]]
    for i in range(1,N-1):
        dp[i][0] = gcd(dp[i-1][0],A[i])
        dp[i][1] = max(gcd(dp[i-1][0],A[i+1]),gcd(dp[i-1][1],A[i+1]))
    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions  import gcd


n=int(input())
a=list(map(int,input().split()))
inf = 0
num_min =2**(n-1).bit_length()
dat=[inf]*(2*num_min-1)

#初期化
for i in range(n):
    dat[i+num_min-1]=a[i]
for i in range(num_min-2,-1,-1):
    dat[i]=gcd(dat[2*i+1],dat[2*i+2])

#親のノード(n-1)//2
#子のノード2n+1,2n+2

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

def update(i,x):
    i+=n-1
    dat[i]=x
    while i>0:
        i=(i-1)//2
        dat[i]=segfunc(dat[2*i+1],dat[2*i+2])
def query(a,b): #半開区間、[a,b)の最小値
    if b<=a:
        return inf
    res=inf
    a += num_min-1
    b += num_min-2
    while b-a>1:
        if a&1==0:
            res = segfunc(res,dat[a])
        if b&1==1:
            res = segfunc(res,dat[b])
            b-=1
        a=a//2
        b=(b-1)//2
    if a==b:
        res = segfunc(res,dat[a])
    else:
        res=segfunc(segfunc(res,dat[a]),dat[b])
    return res

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

Submission status: Accepted

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

DP_first = [0] * N
DP_last = [0] * N

DP_first[0] = A[0]
DP_last[0] = A[-1]

for i in range(1, N):
    DP_first[i] = fractions.gcd(DP_first[i-1], A[i])
    DP_last[i] = fractions.gcd(DP_last[i-1], A[-1-i])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

def main():
    n = int(input())
    a = sorted(int(i) for i in input().split())
    a0 = a[0]
    if a0 == 1:
        print(reduce(gcd, a[1:]))
        return
    c = []
    for i in range(2, int(a0**0.5) + 1):
        while a0 % i == 0:
            c.append(i)
            a0 //= i
    if a0 != 1:
        c.append(a0)
    d = [0] * len(c)
    for ai in a[1:]:
        for i, ci in enumerate(c):
            if ai % ci == 0:
                ai //= ci
            else:
                d[i] += 1
    e = []
    g = 1
    for k, v in zip(c, d):
        if v == 0:
            g *= k
        elif v == 1:
            e.append(k)
    f = [1] * (n - 1)
    for i, ai in enumerate(a[1:]):
        for ei in e:
            if ai % ei == 0:
                ai //= ei
            else:
                f[i] *= ei
    print(max(g * max(f), reduce(gcd, a[1:])))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import random
from operator import itemgetter
import sys
sys.setrecursionlimit(1000000)
ans=0

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

def gcd_all(l):
    rt=l.pop()
    for i in l:
        rt=gcd(i,rt)
    return rt
    
n=int(input())

g=[]

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

ans=0
d=a[-1]
m=a[-1]
mi=-1
k1=[]
flg=0
for i in range(n):
    gg=gcd(a[i],d)
    if gg<m:
        m=gg
        mi=i
ans=max(ans,gcd_all(a[:mi]+(a[mi+1:] if mi+1<n else [])))

d=a[0]
m=a[0]
mi=0
k1=[]
flg=0
for i in range(n):
    gg=gcd(a[i],d)
    if gg<m:
        m=gg
        mi=i
ans=max(ans,gcd_all(a[:mi]+(a[mi+1:] if mi+1<n else [])))

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def init(init_val):
    for i in range(n):
        seg[i+num-1] = init_val[i]
    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 I
    p += num-1
    q += num-2
    res = I
    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


I = 0
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n = int(readline())
a = [int(i) for i in readline().split()]
num = 2**(n-1).bit_length()
seg=[I]*2*num
init(a)
ans = 1
for i in range(n):
  ans = max(ans,gcd(query(0,i),query(i+1,n)))
  
print(ans)

Submission status: Accepted

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

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

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

# print(GCD_l, GCD_r)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
A = LI()
# L = list(accumulate(A, gcd))
# R = list(accumulate(reversed(A), gcd))
tmpl = 0
tmpr = 0
L = []
R = []
for i in range(n):
    tmpl = gcd(tmpl, A[i])
    tmpr = gcd(tmpr, A[-1-i])
    L.append(tmpl)
    R.append(tmpr)

R = list(reversed(R))
# print(L)
# print(R)

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:
import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    """
    「中間の値に関してうんぬん　→　その値の左右の区間から計算」
    は定石と思っていい気がする。

    言われてみればA[i]を除いたGCDはgcd(A[:i])とgcd(A[i+1:])から求まるわなあ
    素因数分解してとか考える以前の話だった。。。
    """

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

gcd_from_left = [0]*N # 自分のindexは含まないようなもの
gcd_from_right = [0]*N

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

ans = 0

for a,b in zip(gcd_from_left, gcd_from_right):
  x = gcd(a,b)
  if ans < x:
    ans = x
    
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)
#print(gcd_l_li)
#print(gcd_r_li)

ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  # かきかえる整数が右端のときと左端のとき
for target in range(1, n-1):
    ans = max(ans, gcd(gcd_l_li[target-1], gcd_r_li[n-2-target]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

B = [0] * (N - 1)
C = [0] * (N - 1)

for n in range(N - 1):
    if n == 0:
        B[0] = A[0]
        C[N - 2] = A[N - 1]
    else:
        B[n] = gcd(B[n - 1], A[n])
        C[N - n - 2] = gcd(A[N - n - 1], C[N - n - 1])

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

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate
N = int(input())
A = tuple(map(int, input().split()))
to_right = [0] + list(accumulate(A, gcd))[:-1]
to_left = list(reversed(list(accumulate(reversed(A), gcd))))[1:] + [0]
print(max(gcd(r, l) for r, l in zip(to_right, to_left)))

Submission status: Accepted

Solution code:
from subprocess import *
call(('pypy3','-c',"""
import sys
def input(): return sys.stdin.readline().rstrip()
# 単位元とseg_funcを設定する
from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele=0 #単位元
        self.num=2**(self.n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        #return a+b #0
        #return a*b #1
        return gcd(a,b) #0
        #return max(a,b) #-1か-10**10 (十分小さいもの)
        #return min(a,b) #10**10 (十分大きいもの)
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): #O(logN)
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    ans=0
    seg_a=seg(A)
    for i in range(n):
        ans=max(ans,gcd(seg_a.query(0,i),seg_a.query(i+1,n)))
    print(ans)
if __name__=='__main__':
    main()
"""))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

gcd_L = [A[0]]
gcd_R = [A[N - 1]]

for i in range(1, N):
    new_gcd_l = gcd(gcd_L[-1], A[i])
    gcd_L.append(new_gcd_l)
    new_gcd_r = gcd(gcd_R[-1], A[N - i - 1])
    gcd_R.append(new_gcd_r)
    
best = gcd_L[N - 1]
for i in range(N):
    if i > 0:
        if i == N - 1:
            a = gcd_L[i - 1]
            if best < a:
                best = a
        else:
            l = gcd_L[i - 1]
            r = gcd_R[N - 2 - i]
            gcd_without_i = gcd(l, r)
            if gcd_without_i > best:
                best = gcd_without_i
    else:
        a = gcd_R[N - 2]
        if a > best:
            best = a

print(best)

Submission status: Accepted

Solution code:
import fractions

N = int(input())
*A, = map(int, input().split())
L = [0]*N
R = [0]*N

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math
from fractions import gcd
import operator
from functools import reduce
from itertools import accumulate

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = defaultdict(int)
    for p in primes:
        if x % p == 0:
            n = 0
            while x % p == 0:
                x //= p
                n += 1
            factors[p] = n
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    sl = list(accumulate(A, gcd))
    sr = list(reversed(list(accumulate(reversed(A), gcd))))
    max_gcd = sl[-1]
    for i in range(N):
        # gcdの単位元は0
        v = 0
        if i > 0:
            v = gcd(v, sl[i-1])
        if i < N-1:
            v = gcd(v, sr[i+1])
        max_gcd = max(max_gcd, v)
    return max_gcd


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

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
R = [0]*n
for i in range(n-1):
    R [i+1] = gcd(R[i], A[i])
    L[i+1] = gcd(L[i], A[-i-1])
print(max(gcd(R[i], L[-i-1]) for i in range(n)))

Submission status: Accepted

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

def gcd(a,b):
  aa=max(a,b)
  bb=min(a,b)
  return gcd(bb,aa%bb) if bb else aa
  

left=[]
right=[]
for i in range(0,n):
  j=n-i-1
  if left:
    hahaha=gcd(left[i-1],a[i])
    left.append(hahaha)
  else:
    left.append(a[i])
  if right:
    hahaha=gcd(right[i-1],a[j])
    right.append(hahaha)
  else:
    right.append(a[j])
    
keep=0
for i in range(0,n):
  if i==0:
    temp=right[-2]
  elif i==n-1:
    temp=left[-2]
  else:
    temp=gcd(left[i-1],right[n-i-2])
  if temp>keep:
    keep=temp

print(keep)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
#たね：gcdは交換法則がなりたち、どこからでも計算していい
#だけど、逆演算ができない 
#(gcd(x,4)==2　を満たすxは2以上の偶数ならなんでもよく
#つまり一つに定まらない）
#そのかわり、"最後の一個以外"を計算してしまうことはできる

#初見殺しじゃねーか
from fractions import gcd
def resolve():
    N,=pin()
    A=tupin()
    lgcd,rgcd=[0]*(N),[0]*(N)
    ltemp,tempr=A[0],A[-1]
    for g in range(N):
        ltemp=gcd(ltemp,A[g])
        lgcd[g]=ltemp
        #print(tempr,A[N-g-1])
        tempr=gcd(tempr,A[N-g-1])
        
        rgcd[N-g-1]=tempr
    #print(lgcd,A,rgcd)
    ans=1
    for i in range((N)):
        a,t=0,0
        if i==0:
            t=rgcd[1]
        elif i==N-1:
            t=lgcd[N-2]
        else:
            t=gcd(lgcd[i-1],rgcd[i+1])
        ans=max(ans,t)
    print(ans)
#%%submit!
resolve()

Submission status: Accepted

Solution code:
from fractions import gcd

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

left = [0]*n
right = [0]*n

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

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

Submission status: Accepted

Solution code:
from fractions import gcd  # use math.gcd with python 3.5~


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    L, R = [0 for _ in range(N)], [0 for _ in range(N)]
    L[0], R[N - 1] = A[0], A[N - 1]
    for i in range(1, N):
        L[i] = gcd(L[i - 1], A[i])
    for j in range(N - 2, -1, -1):
        R[j] = gcd(R[j + 1], A[j])
    max_gcd = 0
    for i in range(N):
        if i == 0:
            g = R[1]
        elif i == N - 1:
            g = L[N - 2]
        else:
            g = gcd(L[i - 1], R[i + 1])
        max_gcd = max([g, max_gcd])
    print(max_gcd)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

L=[0]*n
R=[0]*n
L[0]=A[0]
R[n-1]=A[n-1]
res=0

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
aaa = list(map(int, input().split()))
p = aaa[0]
f = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    f.append(p)
aaa.reverse()
p = aaa[0]
b = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    b.append(p)
b.reverse()

f = [b[0]] + f
b = b + [f[-1]]

print(max(gcd(p, q) for p, q in zip(f, b)))

Submission status: Accepted

Solution code:
def gcd(a,b):
    return gcd(b, a%b) if b else a
N = int(input())
a = list(map(int,input().split()))
gcdl = [a[0]]
gcdr = [a[N-1]]
for i in range(1,N-1):
    gcdl.append(gcd(gcdl[i-1],a[i]))
    gcdr.append(gcd(gcdr[i-1],a[N-i-1]))
import numpy as np
ans = np.maximum(gcdl[N-2],gcdr[N-2])
gcdl.pop()
gcdr.pop()
gcdr.sort()
for i in range(N-2):
    if ans < gcd(gcdl[i],gcdr[i]):
        ans = gcd(gcdl[i],gcdr[i])
print(ans)