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:
import fractions                                                                                                                                             
                                                                                                                                                             
if __name__ == '__main__':                                                                                                                                   
    N = int(input())                                                                                                                                         
    A = list(map(int,input().split()))                                                                                                                       
                                                                                                                                                             
    L = [0] * N                                                                                                                                              
    R = [0] * N                                                                                                                                              
                                                                                                                                                             
    L[0] = A[0]                                                                                                                                              
    for i in range(1,N):                                                                                                                                     
        L[i] = fractions.gcd(L[i-1],A[i])                                                                                                                    
                                                                                                                                                             
    R[-1] = A[-1]                                                                                                                                            
    for i in range(N-2,-1,-1):                                                                                                                               
        R[i] = fractions.gcd(R[i+1],A[i])                                                                                                                    
                                                                                                                                                             
    res = max(R[1],L[-2])                                                                                                                                    
    for i in range(1,N-1):                                                                                                                                   
        res = max(res,fractions.gcd(L[i-1],R[i+1]))                                                                                                          
                                                                                                                                                             
    print(res)

Submission status: Accepted

Solution code:
import copy 

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

N = int(input())
T = list(map(int,input().split()))
T.sort()
LIS = [0]*N
LIS[0] += T[0]
for i in range(N-1):
    LIS[i+1] += gcd(LIS[i],T[i+1])
F = LIS.index(min(LIS))
if len(T) == 2:
    ANS = max(T[0],T[1])
elif F == 0:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(1)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANS = max(ANSU,ANSV)
    
else:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(F)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    ANSU = 0
    ANSV = 0
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANSP = max(ANSU,ANSV)
    ANS = max(ANSP,LIS[N-1])
        
print(ANS)

Submission status: Accepted

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

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

for i in range(n):
    m.append(gcd(left[i], right[n-i-1]))
    
print(max(m))

Submission status: Accepted

Solution code:

def gcd(m, n):
    if n == 0:
        return m

    return gcd(n, m%n)


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))


    l = [0]*(n+1)
    r = [0]*(n+1)
    m = [0]*n

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

    print(max(m))

Submission status: Accepted

Solution code:
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
    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:
def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b
     
N = int(input())
A = [ int(v) for v in input().split() ]
    
if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()
     
l_list = [0]
r_list = [0]
j = -1
for i in range(0, N):
    l_list.append( GCD(l_list[i],  A[i]) )
    r_list.append( GCD(r_list[i],  A[j]) )
    j -= 1

j = -2
mymax = 1   
for i in range(0, N):
    tmp = GCD(l_list[i], r_list[j])
    if tmp > mymax: mymax = tmp 
    j -= 1
print(mymax)

Submission status: Accepted

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

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

R = [0] + list(A) + [0]
L = [0] + list(A) + [0]
M = [0] * (n+2)


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


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

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


print(max(M))

Submission status: Accepted

Solution code:
import fractions

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

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

x = [0]
y = [0]

for i in range(n):
    x.append(gcd(x[i], a[i]))
    y.append(gcd(y[i], a[-(i+1)]))

y.reverse()

ans = []
for i in range(n):
    ans.append(gcd(x[i], y[i+1]))

print(max(ans))

Submission status: Accepted

Solution code:
#!/snap/bin/pypy3
def gcd(a, b):
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


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

    L = [0 for _ in range(N + 1)]
    R = [0 for _ in range(N + 1)]

    for i, num in enumerate(nums):
        L[i + 1] = gcd(L[i], num)

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

    print(max(gcd(L[i], R[i]) for i in range(N)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    print(max(m))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

forward = ([0] + list(accumulate(A[::], gcd)))[:-1]
backward = ([0] + list(accumulate(A[::-1], gcd)))[::-1]

print(max([gcd(x, y) for x, y in zip(forward, backward[1:])]))

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

AL=[0]*N
AR=[0]*N
for i in range(N):
    if i == 0:
        AL[0] = A[0]
        AR[0] = A[N-1]
    else:
        AL[i] = gcd(AL[i-1],A[i])
        AR[i] = gcd(AR[i-1],A[N-i-1])

max=0
for i in range(N):
    if i == 0:
        n_ex_gcd =  AR[N-2]
    elif i == N-1:
        n_ex_gcd = AL[N-2]
    else:
        n_ex_gcd = gcd(AL[i-1],AR[N-i-2])
    if n_ex_gcd > max:
        max = n_ex_gcd
print(max)

Submission status: Accepted

Solution code:
def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    # i を入れた場合のgcdと i を入れない場合のgcdを考える
    ans = 1
    # gcd の結合則を利用する(X, Y, Zがありgcd(gcd(x,y),z)==gcd(x,gcd(x, y)))
    l = [0 for i in range(n)]
    r = [0 for i in range(n+1)]
    for i in range(n-1):
        l[i+1] = gcd(l[i], a[i])
    for i in range(n-1, -1, -1):
        r[i] = gcd(r[i+1],a[i])
    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:
try:
    from fractions import gcd
except:
    from math import gcd
from itertools import accumulate
N=int(input())
A=[int(i) for i in input().split()]
l=[0]+list(accumulate(A,gcd))
g=list(reversed(list(accumulate(reversed(A),gcd))))+[0]

print(max([gcd(l[i-1],g[i]) for i in range(1,N+1)]))

Submission status: Accepted

Solution code:
try:
    from math import gcd
except:
    from fractions import gcd
from itertools import accumulate

N = int(input())
A = [int(s) for s in input().split()]
s = [0] + list(accumulate(A, gcd))
t = list(reversed(list(accumulate(reversed(A), gcd)))) + [0]

ans = max([gcd(s[i-1], t[i]) for i in range(1, N+1)])
print(ans)

Submission status: Accepted

Solution code:
def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b
     
N = int(input())
A = [ int(v) for v in input().split() ]
    
if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()
     
l_list = [0]
r_list = [0]
j = -1
for i in range(0, N):
    l_list.append( GCD(l_list[i],  A[i]) )
    r_list.append( GCD(r_list[i],  A[j]) )
    j -= 1
n = []
j = -2   
for i in range(0, N):
    n.append(GCD(l_list[i], r_list[j]))
    j -= 1
print(max(n))

Submission status: Accepted

Solution code:
def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b

N = int(input())
A = [ int(v) for v in input().split() ]
AR = list(reversed(A))

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()

l_list = [0]
r_list = [0]
for i in range(0, N):
    l_list.append( GCD(l_list[i],  A[i]) )
    r_list.append( GCD(r_list[i], AR[i]) )

n = []
j = -2   
for i in range(0, N):
    n.append(GCD(l_list[i], r_list[j]))
    j -= 1
print(max(n))

Submission status: Accepted

Solution code:
def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b

N = int(input())
A = [ int(v) for v in input().split() ]
AR = list(reversed(A))

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()

l_list = [0]
r_list = [0]
for i in range(0, N):
    l_list.append( GCD(l_list[i],  A[i]) )
    r_list.append( GCD(r_list[i], AR[i]) )

n = []
j = -2   
for i in range(0, N):
    l = l_list[i]
    r = r_list[j]
    n.append(GCD(l, r))
    j -= 1
print(max(n))

Submission status: Accepted

Solution code:
def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b

N = int(input())
A = [ int(v) for v in input().split() ]
AR = list(reversed(A))

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()

l_list = [0]
for i in range(0, N):
    l = GCD(l_list[i], A[i])
    l_list.append( l )

r_list = [0]
for i in range(0, N):
    r = GCD(r_list[i], AR[i])
    r_list.append( r )

n = []
j = -2   
for i in range(0, N):
    l = l_list[i]
    r = r_list[j]
    n.append(GCD(l, r))
    j -= 1
print(max(n))

Submission status: Accepted

Solution code:
def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b

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

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()


l_list = []
l = 0
for i in range(0, N):
    l = GCD(l, A[i])
    l_list.append( l )

r_list = []
r = 0
for i in range(-1, -(N+1), -1):
    r = GCD(r, A[i])
    r_list.append( r )

n = []    
for i in range(0, N):
    if i-1 < 0:
        l = 0
    else:
        l = l_list[i-1]
    if N-i-2 < 0:
        r = 0
    else:
        r = r_list[N-i-2]
    n.append(GCD(l, r))
print(max(n))

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
 
X1 = [0] * (N+2)
X2 = [0] * (N+2)
 
for i in range(N):
    X1[i+1] = gcd(X1[i], A[i])
for i in range(N,0,-1):
    X2[i] = gcd(X2[i+1], A[i-1])

k = []
for i in range(N):
    k.append(gcd(X1[i],X2[i+2]))

print(max(k))

Submission status: Accepted

Solution code:
#gcd関数の定義
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y, x%y)
 
N = int(input())
A = list(map(int, input().split()))
 
#累積gcdの計算
left_gcd = [A[0]]
a = A[0]
for i in range(1,N-1):
  a = gcd(a, A[i])
  left_gcd.append(a)
 
right_gcd = [A[N-1]]
b = A[N-1]
for k in range(N-2, 0, -1):
  b = gcd(b, A[k])
  right_gcd.append(b)
 
#i番目の数字以外の最大公約数を格納
ans_gcd = [right_gcd[N-2], left_gcd[N-2]]
 
for p in range(N-2):
  ans_gcd.append(gcd(left_gcd[p], right_gcd[N-p-3]))
 
#最大公約数の最大値を出力
print(max(ans_gcd))

Submission status: Accepted

Solution code:
import fractions

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

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

M = []
for i in range(N):
    M.append(fractions.gcd(L[i], R[i+2]))
print(max(M))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8


import fractions
gcd = fractions.gcd

def main():
    N = int(input())
    la = list(map(int, input().split()))
    # l(i+1) = gcd(l(i), a(i)), l(0) = 0
    ll = [0]
    # r(i) = gcd(r(i+1), a(i)), r(N+1) = 0
    lr = [0]
    for i in range(N):
        l = gcd(ll[-1], la[i])
        ll.append(l)
        r = gcd(lr[-1], la[N-1-i])
        lr.append(r)
    m = 1
    for i in range(N+1):
        m = max(m, gcd(ll[i], lr[N-1-i]))
    print(m)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
num =int(input())
value = list(map(int, input().split()))
value.sort()
if num == 2:
  answer = value[1]
else:
  cnt = 0
  for i in range(0, num):
      if value[i]%(value[1])!=0:
        cnt += 1
        if cnt == 2:
          break
  if cnt == 1:
    answer = value[1]
  elif cnt == 0:
    answer = value[0]
  else:
    for i in range (0, value[0]):
      cnt = 0
      for j in range(0, num):
        if value[j]%(value[0]-i)!=0:
          cnt += 1
          if cnt == 2:
            break
      if cnt == 1 or cnt == 0:
        answer = value[0] - i
        break
print(answer)

Submission status: Accepted

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

X1 = [0] * (N+2)
X2 = [0] * (N+2)

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

ans = 1
for i in range(N):
    G = gcd(X1[i], X2[i+2])
    if ans < G:
        ans = G
print(ans)

Submission status: Accepted

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

def GCD(A,B):
    if A%B==0:
        return(B)
    return(GCD(B,A%B))

GCD_L = [0]*(N+1)
GCD_R = [0]*(N+1)

GCD_L[0] = A[0]*A[-1]
GCD_R[N] = A[0]*A[-1]

for i in range(N):
    GCD_L[i+1] = GCD(A[i],GCD_L[i])
    GCD_R[N-1-i] = GCD(A[N-1-i],GCD_R[N-i])

GCD_BB = [0] * N
for i in range(N):
    GCD_BB[i] = GCD(GCD_L[i],GCD_R[i+1])

print(max(GCD_BB))

Submission status: Accepted

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

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

def main():
    l = [0] * n
    r = [0] * n
    ans = [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(a[i], r[i+1])
    for i in range(n):
        if i == 0:
            ans[i] = r[i+1]
        elif i == n-1:
            ans[i] = l[i-1]
        else:
            ans[i] = gcd(l[i-1], r[i+1])
    print(max(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

R.reverse()

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

print(max(M))

Submission status: Accepted

Solution code:
import sys
from functools import reduce

input = sys.stdin.readline

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

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


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

Submission status: Accepted

Solution code:
import math
def gcd(x, y): 
   while(y): 
       x, y = y, x % y 
  
   return x 
n = int(input())
a = [int(i) for i in input().split()]
#print(n)
prefix,suffix=[0]*n,[0]*n
prefix[0]=a[0]
suffix[n-1]= a[n-1]
#print(prefix)
for i in range(1,n):
    prefix[i]= gcd(prefix[i-1],a[i])
    suffix[n-i-1]= gcd(suffix[n-i],a[n-i-1])
    pass
maxgcd= max(suffix[1],prefix[-2])
for i in range(1,n-1):
    maxgcd = max(maxgcd, gcd(prefix[i-1],suffix[i+1]))
print(maxgcd)

Submission status: Accepted

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

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

M = []
L = [0]*(N+1)
R = [0]*(N+1)
for i in range(1,N):
    L[i]=gcd(L[i-1],List[i])
    R[-i-1]=gcd(R[-i],List[-i+1])
for i in range(N):
    M.append(gcd(L[i],R[i+1]))
print(max(M))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l_a=list(map(int,input().split()))
l_l=[0]*n#インデ i-1までのgcd
l_r=[0]*n#インデi+1からのgcd
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    if b==0:
        return a
    return gcd(b,a%b)

for i in range(n):
    if i!=0:
        l_l[i]=gcd(l_l[i-1],l_a[i-1])
        l_r[n-1-i]=gcd(l_r[n-i],l_a[n-i])
M=1
for i in range(n):
    m=gcd(l_l[i],l_r[i])
    if m>M:
        M=m
print(M)


#最大公約数→Euclid(log(min(a,b))) ,2数のgcdは簡単に求まる

Submission status: Accepted

Solution code:
# from math import gcd

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

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

R = [0] + list(A) + [0]
L = [0] + list(A) + [0]
M = [0] * (n+2)


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


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

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

# print("A   ", A, " ")
# print("L", L)
# print("R", R)
# print("M", M)
print(max(M))

Submission status: Accepted

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

def GCD(m, n):
  if m == 0:
    return n
  elif n == 0:
    return m
  a = max(m, n)
  b = min(m, n)
  while b > 0:
    r = a % b
    if r == 0:
      return b
    a = b
    b = r  

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

print(max([gcd(r[i],l[i]) for i in range(n)]))

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()))
l = [0 for i in range(n+1)]
r = [0 for i in range(n+1)]
ans = 0

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

bwd = [A[-1]]
for i in range(N-2, -1, -1):
    bwd.append(gcd(bwd[-1], A[i]))
bwd.reverse()

gmax = max(fwd[-2], bwd[1])
for i in range(1, N-1):
    gmax = max(gmax, gcd(fwd[i-1], bwd[i+1]))

print(gmax)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
fw = [0] * n
bw = [0] * n

g = 0
for i in range(n):
    g = gcd(a[i], g)
    fw[i] = g

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

gmax = max(bw[1], fw[n-2])
for i in range(1, n-1):
    g = gcd(fw[i-1], bw[i+1])
    if gmax < g:
        gmax = g

print(gmax)

Submission status: Accepted

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

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

left = [0 for _ in range(n)]
right = [0 for _ in range(n)]
ans = [0 for _ in range(n)]

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

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

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

print(max(ans))

Submission status: Accepted

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

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

l_gcd = [-1] * N
r_gcd = [-1] * N

for i in range(N):
    if i == 0:
        l_gcd [0] = blackboard[0]
    else:
        l_gcd[i] = gcd(l_gcd[i-1],blackboard[i])


for i in reversed(range(N)):
    if i == N - 1:
        r_gcd[N-1] = blackboard[N-1]
    else:
        r_gcd[i] = gcd(r_gcd[i+1],blackboard[i])


#左端と右端のときの値を予め比較しておく。
ans = max(l_gcd[-2],r_gcd[1])

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N = int(input())
A = list(map(int,input().split()))
A.insert(0, 0)
#ユークリッド互除法の関数の定義
def gcd(a,b):
    if(a < b):
        a, b = b, a
    if b == 0 : return a
    return gcd(b, a % b)


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

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

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

'''   
for i in range(1, N + 1):
    print(L[i])
'''

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
l = [0 for i in range(N+1)]
r = [0 for i in range(N+1)]
candidate = []

def GCD(a,b):
    if a == 0 or b == 0: return max(a,b)
    else:
        gcd = 1
        while 1:
            if a%b == 0:
                gcd = b
                break
            else:
                r = a%b
                a = b
                b = r
        return gcd

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

candidate = [0 for i in range(N)]
for i in range(N):
    candidate[i] = GCD(l[i], r[i+1])
print(max(candidate))

Submission status: Accepted

Solution code:

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


def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)


L = [0] * N
R = [0] * N
M = [0] * N

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

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

for i in range(0, N):
    M[i] = (gcd(L[i], R[i]))


print(max(M))

Submission status: Accepted

Solution code:
# coding: utf-8
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


N = int(input())
A = list(map(int, input().split(" ")))
L = [0 for i in range(N)]
R = [0 for i in range(N)]
M = [0 for i in range(N)]

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

Submission status: Accepted

Solution code:
'''input
2
1000000000 1000000000
'''


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

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


# a,b=1071, 1029
# print(gcd(a, b))

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

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

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

# R.reverse()
# print(R)

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

print(max(M))

Submission status: Accepted

Solution code:
from fractions import gcd

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

lgcd, rgcd = [], []
for i in range(n):
    if i == 0:
        lgcd.append(a[0])
        rgcd.append(a[n-1])
        continue

    lgcd.append(gcd(lgcd[i-1], a[i]))
    rgcd.append(gcd(rgcd[i-1], a[-1-i]))

maxgcd = 1
for i in range(n):
    if i == 0:
        tempgcd = rgcd[n-2]
    elif i == n-1:
        tempgcd = lgcd[n-2]
    else:
        tempgcd = gcd(lgcd[i-1], rgcd[n-2-i])
    maxgcd = max(maxgcd, tempgcd)
print(maxgcd)

Submission status: Accepted

Solution code:
import fractions
n=int(input())
lst=list(map(int,input().split()))
xlst=list(reversed(lst))
#1~5と6のgcdは1~6のgcd
#i番目の左側と右側のgcdを求める
#left[i-1]はlstのi番目までのgcd
#xright[i]はlstのnからi-
#lstのi+1番目は右から見たらn-i+1番目



left=[lst[0]]
xright=[lst[n-1]]
for i in range(1,len(lst)):
    left.append(fractions.gcd(left[i-1],lst[i]))

for i in reversed(range(0,len(lst)-1)):
    xright.append(fractions.gcd(xright[n-i-2],lst[i]))


#i-1番目までの左からのgcdはleft[i-2]
#i＋1番目以上のgcdは right[i+2]
result=1
for i in range(1,n-1):
    a=fractions.gcd(left[i-1],xright[n-i-2])
    if a>result:
        result=a
print(max(result,xright[n-2],left[n-2]))

Submission status: Accepted

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

def solve():
  n = int(raw_input())
  a = map(int, raw_input().split())
  left = [0] * (n + 1)
  right = [0] * (n + 1)
  for i in range(1,n + 1):
    left[i] = gcd(left[i - 1], a[i - 1])
  for i in range(n - 1, 0, -1):
    right[i] = gcd(right[i + 1], a[i])
  max_gcd = 0
  for i in range(n):
    max_gcd = max(max_gcd, gcd(left[i], right[i + 1]))
  print max_gcd
        
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import fractions


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

Submission status: Accepted

Solution code:
import fractions

N = int( input() ) # <= 10^5
A = list( map( int, input().split() ) ) # <= 10^9


"""
i番目の数を変更するとすると求めるべき最大公約数はi番目の数を除いた残りの数の最大公約数である
"""

"""
# i = 0 の場合
g = A[1]
g = gcd( g, A[2] )
g = gcd( g, A[3] )
...
g = gcd( g, A[N - 1] ) = R(0)

iを消すとして
iの左側の最大公約数をL(i) (0~i-1の最大公約数)
iの右側の最大公約数をR(i) (i+1からN-1の最大公約数)

i + 1 ~ N - 1
0 ~ N - 1 - (i + 1)

とするとiを消した時の求めるべき最大公約数は
gcd( L(i), R(i) )
であり
L(i + 1) = gcd( L(i), A[i] )
R(i)     = gcd( R(i + 1), A[i] )
という関係が成り立つ
ここで
L(0) = R(N-1) = 0
gcd(0, X) = X
と定義する

L_0を求めて残りは漸化式より順に求める
R_N-1を求めて残りは漸化式より順に求める
"""
def gcd(x, y):
    if x == 0:
        return y
    
    if y == 0:
        return x

    return fractions.gcd(x, y)

# def L(i):
#     if i == 0:
#         return 0
    
#     g = 0
#     for t in range(i):
#         g = gcd( g, A[t] )
#     return g

# def R(i):
#     if i == N - 1:
#         return 0
    
#     g = 0
#     for t in range(N - i - 1):
#         g = gcd( g, A[i + 1 + t] )
#     return g

G = [0] * N # i番目の要素はA_iを除いた時の最大公約数

L_buf = 0
R_buf = 0
tmp1 = 0
tmp2 = 0

for i in range(N):
    if i == 0:
        G[0] = L_buf
        G[N-1] = R_buf
        continue

    tmp1 = gcd( L_buf, A[i-1] )
    # G[i] = G[i] + tmp1
    G[i] = gcd(G[i], tmp1)
    L_buf = tmp1

    tmp2 = gcd( R_buf, A[N - 1 - i + 1] )
    # G[N - 1 - i] = G[N - 1 - i] + tmp2
    G[N - 1 - i] = gcd(G[N - 1 - i], tmp2)
    R_buf = tmp2

print(max(G))

Submission status: Accepted

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

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

print(ans)