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:
N = int(input())
A = list(map(int, input().split()))
 
def gcd(a,b):
  if b==0:
    return a
  else:
  	return gcd(b, a%b)

L=[]
R=[]
L.append(0)
R.append(0)

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

R.reverse()

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

Submission status: Accepted

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

L_list = []
R_list = []
#print(A_list)
gcd_list = []
ans = 0

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

for i in range(N):
    if i == 0:
        L_list.append(0)
        R_list.append(0)
    else:
        L_list.append(gcd(A_list[i-1], L_list[i-1]))
        R_list.append(gcd(A_list[-i], R_list[i-1]))

#print(L_list)
#print(R_list)

for j in range(N):
    gcd_list.append(gcd(L_list[j],R_list[-(j+1)]))

print(max(gcd_list))

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = list(map(int,input().split()))
hard = fractions.gcd(A[0],A[1])
easy = [A[0],A[1]]
del A[0]
del A[0]
while len(A) != 0:
  easyt1 = fractions.gcd(easy[0],A[0])
  easyt2 = fractions.gcd(easy[1],A[0])
  easyt3 = hard
  easy = sorted([easyt1,easyt2,easyt3])[1:3]
  hard = fractions.gcd(hard,A[0])
  del A[0]
print(max(easy))

Submission status: Accepted

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

# Common divisor
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


def gcd_wrapper(x, y):
    if x >= y:
        return gcd(x, y)
    else:
        return gcd(y, x)

if N == 2:
    print(max(A))
    exit()
if N == 3:
    x1 = gcd_wrapper(A[0], A[1])
    x2 = gcd_wrapper(A[1], A[2])
    x3 = gcd_wrapper(A[0], A[2])
    print(max([x1, x2, x3]))
    exit()
A = sorted(A)
A.reverse()
init_results = []
for k, g in enumerate(A[0:3]):
    for h in A[k+1:4]:
        init_results.append(gcd_wrapper(g, h))
if max(init_results) == 1:
    print(1)
    exit()
stop_flag = 0
x = max(init_results)
final_result = set()
final_result.add(x)
for i in A:
    tmp = gcd_wrapper(x, i)
    if tmp == 1:
        stop_flag += 1
    else:
        x = tmp
        final_result.add(tmp)
if stop_flag >= 2:
    print(1)
else:
    sorted_final_result = sorted(list(final_result))
    if len(sorted_final_result) == 1:
        print(sorted_final_result[0])
        exit()
    divable = []
    for j in A:
        if j % sorted_final_result[1] != 0:
            divable.append(1)
    if sum(divable) > 1:
        print(sorted_final_result[0])
    else:
        print(sorted_final_result[1])

Submission status: Accepted

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

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

a = sorted(a)
ans = [gcd(a[0], a[1]), a[0]]
for i in range(2, n):
    ans_0, ans_1 = ans
    ans_0_new = gcd(ans_0, a[i])
    ans_1_new = max(ans_0, gcd(ans_1, a[i]))
    ans = [ans_0_new, ans_1_new]
ans_2 = a[1]
for i in range(2, n):
    ans_2 = gcd(ans_2, a[i])
print(max(ans+[ans_2]))

Submission status: Accepted

Solution code:
def gcd(x, y):
    a = max(x, y)
    b = min(x, y)
    if b == 0:
        return a
    remainder = a % b
    if remainder == 0:
        return b
    return gcd(b, remainder)


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

left = [0]
right = [0]

for i in range(N):
    left.append(gcd(left[-1], integers[i]))
    right.append(gcd(right[-1], integers[-i-1]))

# right.reverse()

lr = []
for i in range(N):
    lr.append(gcd(left[i], right[-i-2]))

print(max(lr))

Submission status: Accepted

Solution code:
from fractions import gcd
 
def sequential_gcd(a):
    d = a[0]
    res = [d]
    for v in a[1:]:
        d = gcd(d, v)
        res.append(d)
    return res
    
n = int(input())
a = list(map(int, input().split()))
if n == 2:
    print(max(a))
else:
    l = sequential_gcd(a)
    r = sequential_gcd(a[::-1])[::-1]
    m = []
    for i in range(n):
        if i == 0:
            m.append(r[1])
        elif i == n-1:
            m.append(l[n-2])
        else:
            m.append(gcd(l[i-1], r[i+1]))
    print(max(m))

Submission status: Accepted

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


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

M = []

# print(L,R)

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

print(max(M))

Submission status: Accepted

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


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

# 累積最大公約数的な
head = []
tail = []
head.append(A[0])
tail.append(A[-1])
for i, j in zip(A[1:], A[N-2::-1]):
    head.append(gcd(head[-1], i))
    tail.append(gcd(tail[-1], j))
ans = 0
for i in range(len(head)-2):
    tmp = gcd(head[i], tail[len(tail)-1-2-i])
    if ans < tmp:
        ans = tmp
print(max(head[-1], head[-2], tail[-2], ans))

Submission status: Accepted

Solution code:
from fractions import gcd

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

# 入力が2つなら最大値が解となる
if n == 2:
    print(max(A))
    exit()

# A1 A2 A3の最大公約数はA1とA2の最大公約数とA3の最大公約数と同値になるので、
# 左右から順番に最大公約数を求めていく。
# 初期値を代入する（右からは0番目にAの最初の要素を、左からは末尾にAの末尾の要素）
gcdL = [0]*n
gcdR = [0]*n
gcdL[0] = A[0]
gcdR[-1] = A[-1]

for i in range(1, n):
    gcdL[i] = gcd(gcdL[i-1], A[i])
    gcdR[-i-1] = gcd(gcdR[-i], A[-i-1])

# A0～AiとAi+1～Anの最大公約数を求めていく
# 最大値が解となる
ans = gcdR[1]
for i in range(1, n-1):
    tmp = gcd(gcdL[i-1], gcdR[i+1])
    ans = max(ans, tmp)
ans = max(ans, gcdL[-2])

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
def gcd(x,y):
    return gcd(y,x%y) if y else x 
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)

Submission status: Accepted

Solution code:
import functools
import fractions

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    A = list(map(int, input().split()))
  else:
    # N = 3
    # A = [7,6,8]
    N = 3
    A = [12,15,18]
    # N = 3
    # A = [1,1000000000,1000000000]

  AL = [0] * N    
  AR = [0] * N
  for i in range(N):
    if i != 0:
      AL[i] = fractions.gcd(AL[i-1],A[i])
    else:
      AL[i] = A[i]
    j = N - i - 1
    if j!= N - 1:
      AR[j] = fractions.gcd(AR[j+1],A[j])
    else:
      AR[j] = A[j]
      
  if 'get_ipython' in globals():   
    print(AL)
    print(AR)
  
  x = 0
  for i in range(N):
    if i == 0:
      tmp = AR[i+1]
    elif i == N - 1:
      tmp = AL[i-1]
    else:
      tmp = fractions.gcd(AL[i-1],AR[i+1])
    if tmp > x: x = tmp
  
  print(x)
    
main()

Submission status: Accepted

Solution code:
# あまりにもTLEになるから解説見ちゃった

from sys import stdin
import numpy as np
from copy import deepcopy
from fractions import gcd

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

"""
## 入力生成用
import random
N = 1000
A = [random.randint(1,1e9) for i in range(N)]
"""

solve = []
L = np.zeros(N)
R = np.zeros(N)

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

ans = int(max(solve))
print(ans)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(n)]
r = l[:]

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

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)

max_element = 1

L = []
R = []

L.append(A[0])
R.append(A[N-1])

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

ans = 1

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

print(ans)

Submission status: Accepted

Solution code:

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

def main( ) :

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

  l = [0 for i in range(n)]
  r = l[:]

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

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

main()

Submission status: Accepted

Solution code:

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

def main( ) :


    n = int(input())
    v = [int(i) for i in input().split()]
    
    l, r = [0], [0]
    for x in v :
        l.append(gcd(l[-1], x))
    l.append(0)
    for x in v[::-1] :
        r.append(gcd(r[-1], x))
    r = [0] + r[::-1]

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

    print(ans)
                 

main()

Submission status: Accepted

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

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


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

Submission status: Accepted

Solution code:
from fractions import gcd

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

ga = [0] * (n + 1)
gr = [0] * (n + 1)
g = []

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

for j in range(n):
    g.append(gcd(ga[j], gr[n - j - 1]))

print(max(g))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
a.sort()
yaku = set()


import math
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n //= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
#a = factorization(n)
#b = []
#for i,j in a:
#  b.append(i)
def divisor_sub(p, q):
    a = []
    for i in range(0, q + 1):
        a.append(p ** i)
    return a

def divisor(n):
    if n == 1:
      return([1])
    xs = factorization(n)
    ys = divisor_sub(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        ys = [x * y for x in divisor_sub(p, q) for y in ys]
    return sorted(ys)
#素因数列挙
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  table = set(table)
  table = list(table)
  return table


a1 =divisor(a[0])
a2 = divisor(a[1])
for i in a1:
    yaku.add(i)
for i in a2:
    yaku.add(i)
yaku = list(yaku)
yaku.sort()
yaku = yaku[::-1]
for i in yaku:
    flag = 1
    for j in range(n):
        if a[j] % i == 0:
            continue
        else:
            if flag:
                flag = 0
            else:
                break
    else:
        print(i)
        exit()

Submission status: Accepted

Solution code:
n = int(input(), 10)
a = list(map(int, input().split()))
greatCDlist = []


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


left = [0 for i in range(n+1)]
right = [0 for i in range(n+1)]

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


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


result = 0
for i in range(n):
    l = left[i]
    r = right[i+1]
    result = max(result, gcd(l, r))

print(result)

Submission status: Accepted

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

#ユークリッド互除法の関数の定義
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)


def gcd_multi(n,x):
    if n==1:
        return x[0]
    else:
        element = gcd(x[0], x[1])
        if n==2:
            return element
        else:
            for i in range(2,n):
                element=gcd(element,x[i])
            return element

X=[0 for i in range(n)]
Y=[0 for i in range(n)]

for i in range(1,n):
    X[i]=gcd(X[i-1],x[i-1])

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

Z=[gcd(X[i],Y[i]) for i in range(n)]
print(max(Z))

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
def gcdaaaaaaaaa(L):
    nextminb = L[0]
    nextn = len(L)
    while True:
        n = nextn
        minb = nextminb
        for l in L[:n]:
            nextn = 0
            r= l % minb
            
            if r != 0:
                L[nextn] = r
                nextn += 1
                if r < nextminb :
                    nextminb = r
        if minb == nextminb:
            return minb
        
def gcd(a,b):
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b,r)
def gcdL(L):
    g = L[0]
    for l in L:
        g = gcd(g,l)
    return g



lgcd = [0] * N
rgcd = [0] * N

lg = A[0]
rg = A[-1]
for i in range(N):
    
    lg = gcd(lg,A[i])
    lgcd[i] = lg
    rg = gcd(rg,A[N-i-1])
    rgcd[N-i-1] = rg
    
maxg = max(lgcd[N-2],rgcd[1])
for i in range(1,N-1):
    g = gcd(lgcd[i-1],rgcd[i+1])
    if maxg < g:
        maxg = g

print(maxg)

Submission status: Accepted

Solution code:
from sys import exit

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


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

    if b == 0:
        return a

    temp = a % b
    while temp != 0:
        a = b
        b = temp
        temp = a % b

    return b


left = [0 for i in range(N)]
right = left[:]

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

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

print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
if n == 2:
  print(max(a))
else:
  a0 = a[0]
  a1 = a[1]
  r = 0
  while True:
    r = a1 % a0
    if r == 0:
      b0 = a0
      break
    elif r > a0:
      a1, a0 = r, a0
    else:
      a1, a0 = a0, r
  a1 = a[1]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a1
    if r == 0:
      b1 = a1
      break
    elif r > a1:
      a2, a1 = r, a1
    else:
      a2, a1 = a1, r
  a0 = a[0]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a0
    if r == 0:
      b2 = a0
      break
    elif r > a0:
      a2, a0 = r, a0
    else:
      a2, a0 = a0, r
  max_a = max(b0,b1,b2)
  for j in range(max_a,1,-1):
    if max_a % j == 0:
      c = list(map(lambda x: x % j,a))
      c_ng = [i for i in c if i > 0]
    #print("j=",j,"c=",c,"c_ng=",c_ng)
      if len(c_ng) <= 1:
        ans = j
        break
  print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
if n == 2:
  print(max(a))
else:
  a0 = a[0]
  a1 = a[1]
  r = 0
  while True:
    r = a1 % a0
    if r == 0:
      b0 = a0
      break
    elif r > a0:
      a1, a0 = r, a0
    else:
      a1, a0 = a0, r
  a1 = a[1]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a1
    if r == 0:
      b1 = a1
      break
    elif r > a1:
      a2, a1 = r, a1
    else:
      a2, a1 = a1, r
  a0 = a[0]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a0
    if r == 0:
      b2 = a0
      break
    elif r > a0:
      a2, a0 = r, a0
    else:
      a2, a0 = a0, r
  max_a = max(b0,b1,b2)
  kouho = []
  for j in range(max_a,1,-1):
    if max_a % j == 0:
      c = list(map(lambda x: x % j,a))
      c_ng = [i for i in c if i > 0]
    #print("j=",j,"c=",c,"c_ng=",c_ng)
      if len(c_ng) <= 1:
        ans = j
        break
  print(ans)

Submission status: Accepted

Solution code:
import sys
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd



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

left_gcds = [gcd(As[0], As[0])]
for i in range(1, len(As)):
    left_gcds.append(gcd(left_gcds[i-1], As[i]))

right_gcds = [gcd(As[-1], As[-1])]
for i in range(1, len(As)):
    right_gcds.append(gcd(right_gcds[i-1], As[-(i+1)]))
right_gcds.reverse()

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

Submission status: Accepted

Solution code:
n = int(input())
v = [int(i) for i in input().split()]


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


l = [0 for i in range(n)]
r = [0 for i in range(n)]

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

Submission status: Accepted

Solution code:
n = int(input())
v = [int(i) for i in input().split()]


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


l = [0 for i in range(n)]
r = [0 for i in range(n)]

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

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

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

l = list(accumulate(a, gcd))
r = list(reversed(list(accumulate(reversed(a), gcd))))

ans = max(gcd(li, ri) for li, ri in zip(l[:-2], r[2:]))

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import functools
import sys

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

left_gcd = [a[0]]
for i in range(1,len(a)):
  left_gcd.append(gcd(left_gcd[-1],a[i]))
#print(left_gcd)
  
right_gcd = [a[-1]]
for i in range(len(a)-1)[::-1]:
  right_gcd.append(gcd(right_gcd[-1],a[i]))
right_gcd = right_gcd[::-1]
#print(right_gcd)

each_gcd = [right_gcd[1]]
for i in range(1,len(a)-1):
  each_gcd.append(gcd(left_gcd[i-1],right_gcd[i+1]))
each_gcd.append(left_gcd[-2])

#print(each_gcd)
print(max(each_gcd))

Submission status: Accepted

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

def ABC125gcd(x, y):
    if min(x, y) == 0:
        return max(x, y)
    else:
        return ABC125gcd(y, x % y)

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a*b<0:
        return -a*b
    while b!=0:
        tmp=a%b
        a=b
        b=tmp
    return a

# def gcd_list(numbers):
#     # print(numbers)
#     g=numbers[0]
#     for i in range(n-1):
#         g=gcd(g,numbers[i])
#     return g
#
# n=int(input())
# a=list(map(int,input().split()))
# gcd_without_i=[gcd_list(a[:i]+a[i+1:]) for i in range(n)]
# # print(gcd_without_i)
# print(max(gcd_without_i))

n=int(input())
a=list(map(int,input().split()))
# gcd_lhs[i]=gcd(a[0],...,a[i-1])
gcd_lhs=[-1 for _ in range(n)]
# gcd_rhs[i]=gcd(a[i+1],...,a[n-1])
gcd_rhs=[-1 for _ in range(n)]
gcd_lhs[1]=a[0]
gcd_rhs[n-2]=a[n-1]
for i in range(1,n):
    gcd_lhs[i]=gcd(gcd_lhs[i-1],a[i-1])
    gcd_rhs[n-1-i]=gcd(gcd_rhs[n-i],a[n-i])

gcd_without_i=[gcd(gcd_lhs[i],gcd_rhs[i]) for i in range(n)]
print(max(gcd_without_i))

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
num = list(map(int, input().split(' ')))

def find_max(idx):
    
    prev_gcd = gcd(num[idx[0]], num[idx[1]])
    curr_excluded_num = None

    for i in range(n):
        if i == idx[0] or i == idx[1]:
            continue
        
        curr_gcd = gcd(prev_gcd, num[i])
        if curr_gcd == prev_gcd:
            continue
        else:
            if curr_excluded_num is None:
                curr_excluded_num = num[i]
            else:
                if curr_gcd > gcd(prev_gcd, curr_excluded_num):
                    prev_gcd = curr_gcd
                else:
                    prev_gcd = gcd(prev_gcd, curr_excluded_num)
                    curr_excluded_num = num[i]

    
    return prev_gcd



if n == 2:
    print(max(num[0], num[1]))
elif n == 3:
    a = gcd(num[0], num[1])
    b = gcd(num[0], num[2])
    c = gcd(num[2], num[1])
    print(max(max(a, b), c))

else:
    ans = find_max((0, 1))
    ans = max(find_max((2, 3)), ans)
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import random


def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) #再帰定義

def solve(N, A):
    left = [A[0]]
    right = [A[N-1]]
    for i in range(1, N):
        left.append(gcd(left[i-1], A[i]))
    for i,j in zip(range(1,N),range(N-2, -1, -1)):
        right.append(gcd(right[i-1], A[j]))

    result = -1
    max_value = -1

    for i in range(N):
        if i == 0:
            current_value = right[N-2]
        elif i == N-1:
            current_value = left[N-2]
        else:
            current_value = gcd(left[i-1], right[N-i-2])
        if current_value > max_value:
            max_value = current_value
    print(max_value)

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
def gcd(a,b):
  if a*b==0:
    return a if b==0 else b
  else:
    while b:
      a,b=b,a%b
  return a

B=[0]*(n+5)
C=[0]*(n+5)

for i in range(n):
  B[i+1]=gcd(B[i],A[i])
  C[i+1]=gcd(C[i],A[n-i-1])
po=0
for i in range(n):
  po=max(po,gcd(B[i],C[n-1-i]))
print(po)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd  # in math module python >= 3.5


def main():
    n = int(input())
    a = list(map(int, input().split()))
    if len(a) < 3:
        print(max(a))
        return

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

    rs = []
    for i in range(n+1):
        if i == 0:
            rs.append(0)
        else:
            rs.append(gcd(rs[i-1], a[-i]))
    rs = list(reversed(rs)) + [0]

    m = [gcd(ls[i], rs[i+1]) for i in range(n+1)]

    print(max(m))


main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
X = [0 for i in range(N)]
Y = [0 for i in range(N)]

def gcd(a,b):
    x = max(a, b)
    y = min(a, b)
    if y == 0:
        return x
    if x % y == 0:
        return y
    else:
        return gcd(y, x%y)

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

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

Z = [gcd(X[i], Y[i]) for i in range(N)]

print(max(Z))

Submission status: Accepted

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

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

ans = 1

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

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
  if b == 0:
    return a
  return gcd(b, a % b)

X = [0] * (n + 1)
Y = [0] * (n + 1)

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

gcds = []

for i in range(n):
  gcds.append(gcd(X[i], Y[i+1]))

print(max(gcds))

Submission status: Accepted

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

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

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

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

g_max = -1
for i in range(n):
    g = gcd(l[i], r[i])
    if g > g_max:
        g_max = g

print(g_max)

Submission status: Accepted

Solution code:
# http://tsutaj.hatenablog.com/entry/2017/03/29/204841

from fractions import gcd


class SegmentTree:
    def __init__(self, v):
        sz = len(v)

        self.n = 1
        while self.n < sz:
            self.n *= 2

        self.node = [0 for _ in range(2 * self.n - 1)]
        # 元配列 v をセグメント木で表現する
        # 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        # セグメント木全体で必要なノード数は 2n - 1 個である

        for i in range(sz):
            self.node[i + self.n - 1] = v[i]
        # 最下段に値を入れたあとに、下の段から順番に値を入れる

        for i in range(self.n - 2, -1, -1):
            self.node[i] = gcd(self.node[2 * i + 1], self.node[2 * i + 2])
        # 値を入れるには、自分の子の 2 値を参照すれば良い

    def update(self, x, val):
        x += self.n - 1
        # 最下段のノードにアクセスする

        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = gcd(self.node[2 * x + 1], self.node[2 * x + 2])
        # 最下段のノードを更新したら、あとは親に上って更新していく

    # 要求区間 [a, b) 中の要素の最小値を答える
    # k := 自分がいるノードのインデックス
    # 対象区間は [l, r) にあたる

    def get_val(self, a, b, k, l, r):
        if r <= a or b <= l: return 0
        # 要求区間と対象区間が交わらない -> 適当に返す

        if a <= l and r <= b: return self.node[k]
        # 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う

        vl = self.get_val(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.get_val(a, b, 2 * k + 2, (l + r) // 2, r)
        return gcd(vl, vr)
        # 要求区間が対象区間の一部を被覆 -> 子について探索を行う
        # 左側の子を vl ・ 右側の子を vr としている
        # 新しい対象区間は、現在の対象区間を半分に割ったもの


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

st = SegmentTree(a)

g = max(
    gcd(
        st.get_val(0, drop_idx, 0, 0, st.n),
        st.get_val(drop_idx + 1, N, 0, 0, st.n)
    ) for drop_idx in range(N)
)
print(g)

Submission status: Accepted

Solution code:
# http://tsutaj.hatenablog.com/entry/2017/03/29/204841
class SegmentTree:
    def __init__(self, v):
        sz = len(v)

        self.n = 1
        while self.n < sz:
            self.n *= 2

        self.node = [0 for _ in range(2 * self.n - 1)]
        # 元配列 v をセグメント木で表現する
        # 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        # セグメント木全体で必要なノード数は 2n - 1 個である

        for i in range(sz):
            self.node[i + self.n - 1] = v[i]
        # 最下段に値を入れたあとに、下の段から順番に値を入れる

        for i in range(self.n - 2, -1, -1):
            self.node[i] = gcd(self.node[2 * i + 1], self.node[2 * i + 2])
        # 値を入れるには、自分の子の 2 値を参照すれば良い

    def update(self, x, val):
        x += self.n - 1
        # 最下段のノードにアクセスする

        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = gcd(self.node[2 * x + 1], self.node[2 * x + 2])
        # 最下段のノードを更新したら、あとは親に上って更新していく

    # 要求区間 [a, b) 中の要素の最小値を答える
    # k := 自分がいるノードのインデックス
    # 対象区間は [l, r) にあたる

    def get_val(self, a, b, k, l, r):
        if r <= a or b <= l: return 0
        # 要求区間と対象区間が交わらない -> 適当に返す

        if a <= l and r <= b: return self.node[k]
        # 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う

        vl = self.get_val(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.get_val(a, b, 2 * k + 2, (l + r) // 2, r)
        return gcd(vl, vr)
        # 要求区間が対象区間の一部を被覆 -> 子について探索を行う
        # 左側の子を vl ・ 右側の子を vr としている
        # 新しい対象区間は、現在の対象区間を半分に割ったもの


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


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

st = SegmentTree(a)

g = max(
    gcd(
        st.get_val(0, drop_idx, 0, 0, st.n),
        st.get_val(drop_idx + 1, N, 0, 0, st.n)
    ) for drop_idx in range(N)
)
print(g)