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 statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)


"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


n = ip()                                     #入力整数1つ
#a,b,t= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#k = ip()                      #入力セット(整数改行あり)(1/2)
#v=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
if n==2:
    print(max(a))
else:
    ans = []
    s = [a[0]]
    for i in range(1,n):
        s.append(fractions.gcd(s[i-1],a[i]))
    r = [a[n-1]]
    for i in range(n-2,-1,-1):
        r.append(fractions.gcd(r[len(r)-1],a[i]))
    r = r[::-1]
 #   print(s,"from left")
 #   print(r,"from right")
    ans.append(r[1])
    for i in range(1,n-1):
        ans.append(fractions.gcd(s[i-1],r[i+1]))
    ans.append(s[n-2])
    print(max(ans))

Submission status: Accepted

Solution code:
def gcd(num1,num2):
    if num2==0:
        return num1
    return gcd(num2,num1%num2)
from collections import deque
n=int(input())
a=[int(i) for i in input().split()]
left_gcd=a[0]
right_gcd=a[-1]
left=deque([])
right=deque([])
for i in a:
    left_gcd=gcd(left_gcd,i)
    left.append(left_gcd)
for i in a[::-1]:
    right_gcd=gcd(right_gcd,i)
    right.append(right_gcd)
right=deque(reversed(right))
Max=max(right[1],left[-2])
for i in range(1,n-1):
    Max=max(Max,gcd(left[i-1],right[i+1]))
print(Max)

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

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

Submission status: Accepted

Solution code:
from itertools import *
import fractions

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

L = list(accumulate([0]+A, fractions.gcd))
R = list(accumulate([0]+A[::-1], fractions.gcd))

print(max(fractions.gcd(s, t) for s, t in zip(L, R[::-1][1:])))

Submission status: Accepted

Solution code:
import fractions

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

gcd_r=[0]*n
gcd_r[n-1]=a[n-1]
for i in range(n-2,-1,-1):
  gcd_r[i]=fractions.gcd(gcd_r[i+1],a[i])
#gcd_r[i]は末尾からa[i]までのgcd

gcd_l=[0]*n
gcd_l[0]=a[0]
for i in range(1,n):
  gcd_l[i]=fractions.gcd(gcd_l[i-1],a[i])
#gcd_l[i]は先頭からa[i]までのgcd

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

def main(N, A):
    L = [0]*(N+1)
    R = [0]*(N+1)
    M = [0]*(N+1)
    
    for i in range(N):
        L[i+1] = gcd(L[i], A[i])
        R[(-2-i)] = gcd(R[-1-i], A[-1-i])
    for i in range(N):
        M[i] = gcd(L[i], R[i+1])
        
    print(max(M))

if __name__ == '__main__':
    N = int(input())
    A = [int(a) for a in input().split()]
    
    main(N, A)

Submission status: Accepted

Solution code:
from itertools import*
from fractions import*
n,*a=map(int,open(0).read().split())
b=list(accumulate([0]+a,gcd))
c=list(accumulate([0]+a[::-1],gcd))
print(max(gcd(s,t)for s,t in zip(b,c[::-1][1:])))

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a ==0:
        return b
    if b==0:
        return a
    return gcd(b,a%b)
N = int(input())
A = list(map(int,input().split()))
R = [0]*(N+1)
L = [0]*(N+1)
M = [0]*(N+1)
for i in range(N):
    L[i+1]= gcd(L[i],A[i])
    R[-(i+2)] = gcd(R[-(i+1)],A[-(i+1)])
for i in range(N):
    M[i] = gcd(L[i],R[i+1])
print(max(M))

Submission status: Accepted

Solution code:
#EOFERROR
# import math
# import copy
# from functools import reduce
# n = int(input())
# a = list(map(int,input().split()))
# ans = reduce(math.gcd,a)
# if n<=2 or (min(a)==max(a)):
#     print(max(a))
# else:
#     for i in range(n):
#         _a = copy.copy(a)
#         _a.pop(i)
#         tmp = reduce(math.gcd,_a)
#         if tmp > ans:
#             print(tmp)
#             break
#         else:
#             pass

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

def cul(n,x):
    l = len(x)
    b = [x[i] for i in range(l)]
    b.pop(n)
    tmp = b[0]
    for i in range(1,l-1):
        tmp = gcd(tmp,b[i])
    return tmp

import sys
p = 50
N = int(input())
if p>N : p=N
a = list(map(int,input().split()))

ans = 0

for i in range(p):
    s = cul(i,a[:p])
    if s>ans : ans=s

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
li = [ int(it) for it in input().split() ]
lil = [0]*N
lir = [0]*N

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
  
lil[0]=li[0]
lir[N-1]=li[N-1]
for i in range(N-1):
  lil[i+1]=gcd(li[i+1],lil[i])
for i in range(N-1,0,-1):
  lir[i-1]=gcd(li[i-1],lir[i])
s = -1
for i in range(N):
  if (i==0):
    gc = lir[1]
  elif (i==N-1):
    gc = lil[N-2]
  else:
    gc = gcd(lil[i-1],lir[i+1])
  s = max(s, gc )
print (s)

Submission status: Accepted

Solution code:
def gcd(a,b):
    while a%b!=0:
        a,b = b,a%b
    return b
n = int(input())
a = list(map(int,input().split()))
right,left = [0]*n,[0]*n
left[0],right[n-1] = a[0],a[n-1]
for i in range(1,n):
    left[i] = gcd(left[i-1],a[i])
for i in range(n-2,-1,-1):
    right[i] = gcd(right[i+1],a[i])
ans = max(left[-2],right[1])
for i in range(1,n-1):
    ans = max(ans,gcd(right[i+1],left[i-1]))
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

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

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

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

print(max(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions


if __name__ == '__main__':
  N = int(input())
  A = list(map(int, input().split()))

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

  ans = []
  for i in range(N):
      ans.append(fractions.gcd(gcdl[i], gcdr[i+1]))
  print(max(ans))

Submission status: Accepted

Solution code:
def gcd(a,b):
    while a%b!=0:
        a,b=b,a%b
    return b
N=int(input())
A=list(map(int,input().split()))
if N==1:
    print(10**9)
    exit()
go=[0]*N
go[0]=A[0]
back=[0]*N
back[N-1]=A[N-1]
for i in range(1,N):
    go[i]=gcd(go[i-1],A[i])
for i in range(N-2,-1,-1):
    back[i]=gcd(back[i+1],A[i])
ans=max(go[-2],back[1])
for i in range(1,N-1):
    now=gcd(go[i-1],back[i+1])
    ans=max(now,ans)
print(ans)

Submission status: Accepted

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

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

r = [0 for _ in range(n+1)]
l = [0 for _ in range(n+1)]

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

m = [0 for _ in range(n)]

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

print(max(m))

Submission status: Accepted

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


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

gcd_l = [0] * N

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

gcd_r = [0] * N

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

gcd_lr = [0] * N

for i in range(N):
    if i == 0:
        gcd_lr[i] = gcd_r[i + 1]
    elif 1 <= i <= N - 2:
        gcd_lr[i] = gcd(gcd_l[i - 1], gcd_r[i + 1])
    elif i == N - 1:
        gcd_lr[i] = gcd_l[i - 1]

print(max(gcd_lr))

Submission status: Accepted

Solution code:

# 最大公約数を求める
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

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

# 累積GCDの計算(A1, A2, ... Ai-1の最大公約数)
left_gcd=[a_array[0]] # 
a=a_array[0] # 最初のループはgcd(a_array[0], a_array[1])になる
for i in range(1, n-1):
    a=gcd(a,a_array[i])
    left_gcd.append(a)

# 累積GCDの計算(Ai, Ai+1, ... ANの最大公約数)
right_gcd=[a_array[-1]]
b=a_array[-1] # 最初のループはgcd(a_array[-1], a_array[-2])になる
for i in range(n-2,0,-1):
    b=gcd(b,a_array[i])
    right_gcd.append(b)

# i番目の数値以外の最大公約数を格納
ans_gcd=[right_gcd[n-2],left_gcd[n-2]]

for i in range(n-2):
    ans_gcd.append(gcd(left_gcd[i],right_gcd[n-i-3]))

print(max(ans_gcd))

Submission status: Accepted

Solution code:
# ヒントみて作った回答
def gcd(a, b):
    maxi = max(a,b)
    mini = min(a,b)
    if mini==0:
        return maxi
    else:
        return gcd(mini, maxi%mini)

n = int(input())
a = list(map(int, input().split()))
L = [0] 
R = [0] 
for i in range(n):
    L.append(gcd(a[i], L[i]))
    R.append(gcd(a[n-i-1], R[i]))
R.reverse()

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

Submission status: Accepted

Solution code:
def gcd(a, b):
    
    if a == b:
        return a
    
    small = large = 0
    if a > b:
        small = b
        large = a
    else:
        small = a
        large = b
    
    while True:
        
        d, m = divmod(large, small)
        if m == 0:
            return small
        else:
            large = small
            small = m
    
    
    

def get_next_int():
    return int(float(input()))
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])

def main():
    n = get_next_int()
    numbers = get_next_ints()
    
    current = numbers[0]
    candidates = {numbers[1]}
    
    for number in numbers[1:]:
        
        next_candidates = {}
        for candidate in candidates:
            next_candidates[gcd(candidate, number)] = 1
        candidates = next_candidates
        #print(candidates.keys())
        candidates[current] = 1
        current = gcd(current, number)    
    
    print(max(candidates.keys()))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())
a = list(map(int,input().split()))
l = [0]
r = [0]
for i in range(n):
    l.append(gcd(l[i],a[i]))
for i in range(n):
    r.append(gcd(r[i],a[-i-1]))
r.reverse()
ans = 0
for i in range(n):
    if ans < gcd(l[i],r[i+1]):
        ans = gcd(l[i],r[i+1])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
import sys
from functools import reduce 
""""
import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
# 約数を高速で列挙するコード
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
"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

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


# 最大公約数を吐く
def gcd_euclid(a, b):
    if a > b:
        a, b = b, a 
    if a==0:
        return b
    return gcd_euclid(b%a, a)

def main():
    A.sort()
    res = 0
    for i in range(1,N+1):
        L[i] = gcd_euclid(L[i-1], A[i-1])
    for i in range(N-1, 0, -1):
        R[i] = gcd_euclid(R[i+1], A[i])
    
    for i in range(N):
        gcd_now = gcd_euclid(L[i], R[i+1])
        res = max(res, gcd_now)
    print(res)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

# coding: utf-8

# In[1]:

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


# In[2]:

#import copy
#import numpy as np
try:
    from fractions import gcd
except:
    from math import gcd


# In[ ]:

# 左からn個の最大公約数を求める O(n)
# 右からn個の最大公約数を求める O(n)
# n個目を抜いた最大公約数は n-1個目までの公約数とn+1個目からの公約数との公約数


# In[3]:

lg = [1]*(N)
rg = [1]*(N)
#ans = 0


# In[4]:

#print(lg)
#print(rg)
#print(A)


# In[ ]:

lg[0] = A[1]
rg[0] = A[N-2]
lg[1] = A[0]
rg[1] = A[N-1]

for i in range(1, N-1):
    #print(i)
    lg[i+1] = gcd(lg[i], A[i])
    #print(lg[i], A[i])
    rg[i+1] = gcd(rg[i], A[N-1-i])
    #print(rg[N-1-i], A[N-1-i])
#print(lg, rg)

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


# In[6]:

#print(ans)

Submission status: Accepted

Solution code:

# coding: utf-8

# In[1]:

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


# In[2]:

#import copy
#import numpy as np
try:
    from fractions import gcd
except:
    from math import gcd


# In[ ]:

# 左からn個の最大公約数を求める O(n)
# 右からn個の最大公約数を求める O(n)
# n個目を抜いた最大公約数は n-1個目までの公約数とn+1個目からの公約数との公約数


# In[3]:

lg = [1]*(N)
rg = [1]*(N)
ans = 0


# In[4]:

#print(lg)
#print(rg)
#print(A)


# In[ ]:

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

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


# In[6]:

#print(ans)

Submission status: Accepted

Solution code:

# coding: utf-8

# In[1]:

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


# In[2]:

#import copy
#import numpy as np
try:
    from fractions import gcd
except:
    from math import gcd


# In[ ]:

# 左からn個の最大公約数を求める O(n)
# 右からn個の最大公約数を求める O(n)
# n個目を抜いた最大公約数は n-1個目までの公約数とn+1個目からの公約数との公約数


# In[3]:

lg = [1]*(N)
rg = [1]*(N)
ans = 0


# In[4]:

#print(lg)
#print(rg)
#print(A)


# In[5]:

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

for i in range(N):
    #print(i, lg[i], rg[N-i-1])
    tmp = gcd(lg[i], rg[N-i-1])
    #print(tmp)
    if ans < tmp:
        ans = tmp
    #print(ans)


# In[6]:

print(ans)


# In[ ]:

"""
[42 54 69 92 12 23]のとき
 1 [54 69 92 12 23]の最大公約数
 2 [42 69 92 12 23]
 3 [42 54 92 12 23]
 4 [42 54 69 12 23]

"""

Submission status: Accepted

Solution code:

# coding: utf-8

# In[1]:

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


# In[2]:

#import copy
#import numpy as np
try:
    from fractions import gcd
except:
    from math import gcd


# In[ ]:

# 左からn個の最大公約数を求める O(n)
# 右からn個の最大公約数を求める O(n)
# n個目を抜いた最大公約数は n-1個目までの公約数とn+1個目からの公約数との公約数


# In[3]:

lg = [1]*(N)
rg = [1]*(N)
ans = 0


# In[4]:

#print(lg)
#print(rg)
#print(A)


# In[5]:

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

for i in range(N):
    #print(i, lg[i], rg[N-i-1])
    tmp = gcd(lg[i], rg[N-i-1])
    #print(tmp)
    if ans < tmp:
        ans = tmp
    #print(ans)


# In[6]:

print(ans)


# In[ ]:

"""
[42 54 69 92 12 23]のとき
 1 [54 69 92 12 23]の最大公約数
 2 [42 69 92 12 23]
 3 [42 54 92 12 23]
 4 [42 54 69 12 23]

"""

Submission status: Accepted

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

def gcd(x, y):
  return gcd(y, x%y) if y else x

l, r = [], []

for i in range(n):
  l.append(gcd(l[i-1], a[i-1]) if i else 0)
  r.append(gcd(r[i-1], a[n-i]) if i else 0)
print(max([gcd(l[i], r[n-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):
	while b:
		a, b = b, a % b
	return a

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

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

ans = 0

for i in range(n):
    ans = max(ans, gcd(L[i], R[i]))

print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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

N = int(input())
A = [int(_) for _ in input().split()]
p1 = [0] * N
p2 = [0] * N

p1[0] = A[0]
p2[-1] = A[-1]

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

m = max(p1[-2], p2[1])

if N > 2:
	for i in range(1, N-1):
		m = max(m, gcd(p1[i-1], p2[i+1]))

print(m)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
ans = 0
lgcd = [0]*n
rgcd = [0]*n
lgcd[0] = li[0]
rgcd[-1] = li[-1]

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

for i in range(n-1):
    lgcd[i+1] = gcd(lgcd[i],li[i+1])
    rgcd[-i-2] = gcd(rgcd[-i-1],li[-(i+2)])

gcd_list = [gcd(lgcd[i],rgcd[i+2]) for i in range(n-2)]

gcd_list.append(lgcd[-2])
gcd_list.append(rgcd[1])

print(max(gcd_list))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))

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

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

rl = [0]*n
rl[n-1] = al[n-1]
for i in range(n-2,-1,-1):
    rl[i] = gcd(al[i],rl[i+1])

res = -1

for i in range(n):
    if i==0:
        res = max(res, rl[1])
    elif i==n-1:
        res = max(res, ll[n-2])
    else:
        res = max(res, gcd(ll[i-1],rl[i+1]))

print(res)

Submission status: Accepted

Solution code:
import sys

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

n=int(input())
al=input().split()
al_i = [int(s) for s in al]

if (n == 2):
   print(max(al_i[0],al_i[1]))
   sys.exit()

fg = [0] * n
bg = [0] * n

for x in range(n):
   if (x == 0):
       fg[0] = al_i[0]
       y = 1
   else:
      while y <= x:
         fg[y] = gcd(fg[y-1], al_i[y])
         y += 1

for x in range(n):
   if (x == 0):
      bg[0] = al_i[n-1]
      y = 1
   else:
      while y <= x:
         bg[y] = gcd(bg[y-1], al_i[n-1-y])
         y += 1

m = 0
gm = 0

for x in range(n):
   if (x == 0):
      g = bg[n-2]
   elif (x == n-1):
      g = fg[n-2]
   else:
      g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)

Submission status: Accepted

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

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

fg = [0] * n
bg = [0] * n

fg[0] = al[0]
bg[0] = al[n-1]

for x in range(1,n):
    fg[x] = gcd(fg[x-1], al[x])
    bg[x] = gcd(bg[x-1], al[n-1-x])

gm = max(bg[n-2], fg[n-2])

for x in range(1,n-1):
   g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)

Submission status: Accepted

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


class SegmentTree():
    def __init__(self, array, f, e, size):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
        """
        self.f = f
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

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

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


gcd = lambda x, y: gcd(y, x) if x < y else gcd(y, x % y) if y else x
e = 0
size = N
ST = SegmentTree(A, f=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:
# 最大公約数
def gcd(a, b):
    if a > b:
        return gcd(b, a)
    else:
        if a == 0:
            return b
        else:
            return gcd(b % a, a)


n = int(input())
a = list(map(int, input().split()))  # -> li = [1,2,3,...n]
lg = []
lg.append(0)
rg = []
rg.append(0)
for i in range(n):
    lg.append(gcd(lg[-1], a[i]))
    rg.append(gcd(rg[-1], a[n-i-1]))
# print(lg)
# print(rg)
m = 0
for i in range(n):
    g = gcd(lg[i], rg[n-1-i])
    if g > m:
        m = g
print(m)

Submission status: Accepted

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

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

x = []
for i in range(N):
    x.append(fractions.gcd(gcd_L[i], gcd_R[i+1]))
print(max(x))

Submission status: Accepted

Solution code:
import fractions
import numpy as np


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

left_gcd_array = np.array([0] * n)
left_gcd_array[0] = a[0]

right_gcd_array = np.array([0] * n)
right_gcd_array[n - 1] = a[n - 1]

for i in range(1, n):
    left_gcd_array[i] = fractions.gcd(a[i], left_gcd_array[i - 1])
    right_gcd_array[n - 1 - i] = fractions.gcd(a[n - 1 - i], right_gcd_array[n - i])

print(max([left_gcd_array[n - 2]] +
          [fractions.gcd(left_gcd_array[i], right_gcd_array[i + 2]) for i in range(0, n - 2)] +
          [right_gcd_array[1]]))


if __name__ == '__main__':
    pass

Submission status: Accepted

Solution code:
import fractions

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

gcd_left_list = [0]*N
gcd = alist[0]
for i in range(1,N):
  gcd = fractions.gcd(gcd,alist[i-1])
  gcd_left_list[i] = gcd

gcd_right_list = [0]*N
gcd = alist[N-1]
for i in reversed(range(0,N-1)):
  gcd = fractions.gcd(gcd,alist[i+1])
  gcd_right_list[i] = gcd

#print(alist)
#print(gcd_left_list)
#print(gcd_right_list)
    
max_gcd = max(gcd_right_list[0], gcd_left_list[N-1])
for i in range(1,N-1):
  gcd = fractions.gcd(gcd_left_list[i],gcd_right_list[i])
  if gcd > max_gcd:
    max_gcd = gcd

print(max_gcd)

Submission status: Accepted

Solution code:
import fractions
n=int(input())
lis=list(map(int,input().split()))
li=[lis[0]]
l=[lis[n-1]]
for i in range (0,n-1):
  li.append(fractions.gcd(li[i],lis[i+1]))
  l.append(fractions.gcd(l[i],lis[n-i-2]))
ans_li=[]
for i in range(0,n-2):
  ans_li.append(fractions.gcd(li[i],l[n-3-i]))
ans_li.insert(0,li[n-2])
ans_li.append(l[n-2])
ans_li.sort()           
ans_li.reverse()
print(ans_li[0])

Submission status: Accepted

Solution code:
from fractions import gcd
 
n,*a = map(int, open(0).read().split())
 
rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))
 
print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
front = [0]
back = [0]
for i in range(len(A)):
    front.append(gcd(A[i], front[i]))
    back.append(gcd(A[len(A) - i - 1], back[i]))
ans = 0
for i in range(len(A)):
    ans = max(gcd(front[i], back[len(A) - i - 1]), ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
"""解説
GCD, DP, 累積和

「一つを選んで好きな数字に変えられる」とあるが、今回のケースでは「その数字を消す」と同じ。

すべてのGCDを試す

4 6 7 8 10 12 14

という数列が与えられたとき、

・4を消して、ほかの数字のGCDを計算

6 7 8 10 12 14

・6を消して、ほかの数字のGCDを計算

4 7 8 10 12 14

・7を消して、……

というのを全列挙するが、N=10**5なので、O(N**2)では計算が間に合わない。

なのでこれをもう少し高速でやりたい。

GCDは計算順序を問わない性質を利用する。

たとえば、8を消した場合

4 6 7 8 10 12 14
| 左 |× |   右  |

・左のGCD
・右のGCD
を計算し、GCD(左のGCD, 右のGCD)をやってもよい。

・左のGCDを考える
GCD(4) = L[1]
GCD(4 6) = L[2] = GCD(L[1], 6)
GCD(4 6 7) = L[3] = GCD(L[2], 7)
GCD(4 6 7 8) = L[4] = GCD(L[3], 8)
GCD(4 6 7 8 10) = L[5] = GCD(L[4], 10)

みたいな感じで計算できる。

・右のGCDについても同様に計算してやる。

この前計算ができたら、あとは累積和のように、どの数字を削除したときがGCDが最大になるのかを計算する。

"""
import copy

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

    def gcd(x, y):
        """ 最大公約数を求める """
        # x > y にしたい
        if y > x:
            x, y = y, x
        if y == 0:
            return x
        return gcd(x%y, y)

    # L[i] := A[i]が消されたときの左側のGCD
    L = [0]*(N+1)
    L[1] = A[0]
    for i in range(2, N):
        L[i] = gcd(L[i-1], A[i-1])

    # R[i] := A[i]が消されたときの右側のGCD
    R = [0]*(N+1)
    R[N-1] = 0
    R[N-2] = A[N-1]
    for i in range(N-3, -1, -1):
        R[i] = gcd(R[i+1], A[i+1])
    
    # 任意の数字を消したときの最大のGCDを求める
    ans = 0
    for i in range(N):
        tmp = gcd(L[i], R[i])
        ans = max(ans, tmp)

    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from fractions import gcd


def main(input_1, input_2):
    left = [0] * (input_1+1)
    for i in range(input_1):
        left[i+1] = gcd(left[i], input_2[i])

    right = [0] * (input_1 + 1)
    i = input_1 - 1
    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])
        i -= 1

    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])

    res = 0
    for i in range(input_1):
        l = left[i]
        r = right[i+1]
        gcd_val = gcd(l, r)
        if gcd_val > res:
            res = gcd_val

    return res


if __name__ == "__main__":
    input_1 = int(input())
    input_2 = list(map(int, input().split()))
    print(main(input_1, input_2))

Submission status: Accepted

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

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)

n = int(input())
a = list(map(int, input().split()))
rs, ls = [0], [0]
for i in range(n-1):
    rs.append(gcd(rs[i], a[i]))
    ls.append(gcd(ls[i], a[-i-1]))
gcd_list = [gcd(r,l) for r, l in zip(rs, ls[::-1])]
print(max(gcd_list))

Submission status: Accepted

Solution code:
import numpy as np

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

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

l = [0]*n
r = [0]*n

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

tmp = list(range(0,n-1))
tmp.reverse()
for i in tmp:
    r[i]=gcd(r[i+1],s[i+1])
    
m = list([])

for i in range(n):
    m.append(gcd(l[i],r[i]))

print(max(m))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

gcd_list = [gcd(r,l) for r, l in zip(rs, ls[::-1])]
print(max(gcd_list))