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


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

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

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

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

Submission status: Accepted

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

n=int(input())
a=[0]+list(map(int,input().split()))+[0]
#n=2
#a=[1000000000,1000000000]
#a=sorted(a)[::-1]
anslist=[]
L=[0 for i in range(n+2)]
R=[0 for i in range(n+2)]
for i in range(1,n+2):#メモ化
    L[i]=gcd(a[i],L[i-1])#0~iまでgcdを計算したものをメモ
    R[n+1-i]=gcd(a[n+1-i],R[n+2-i])#n+2~iまでを計算したものをメモ
for i in range(1,n+1):
    anslist.append(gcd(L[i-1],R[i+1]))
print(max(anslist))

Submission status: Accepted

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

n = int(input())
a = [0] + list(map(int, input().split())) + [0]
max_gcd = 1
L = [0] * (n+2)
R = [0] * (n+2)

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

print(max_gcd)

Submission status: Accepted

Solution code:

import fractions
a = int(input())
num_list = list(map(int, input().split()))
head_gcd_list = [0]
tail_gcd_list = [0]
for i in range(a - 1):
    head_gcd_list.append(fractions.gcd(head_gcd_list[i], num_list[i]))
    tail_gcd_list.append(fractions.gcd(tail_gcd_list[i], num_list[(i*-1) - 1]))
max_gcd = 0
for i,j in zip(head_gcd_list, reversed(tail_gcd_list)):
    current_gcd = fractions.gcd(i, j)
    if(current_gcd > max_gcd):
        max_gcd = current_gcd
print(max_gcd)

Submission status: Accepted

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

n = int(input())
A = [0] + list(map(int, input().split())) + [0]
largest = 0
L = [0 for _ in range(n+2)]
R = [0 for _ in range(n+2)]
for i in range(1, n+2):
  L[i] = gcd(A[i], L[i-1])
  R[n-i+1] = gcd(R[n-i+2], A[n-i+1])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#累積GCDによるsolution : O(N)
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
B = [A[0]]+[0]*(N-1)
C = [0]*(N-1)+[A[-1]]
for i in range(N-1):
    B[i+1] = gcd(A[i+1],B[i])
for i in range(N):
    C[-i-1] = gcd(A[-i-1],C[-i])

ans = 0
for i in range(1,N-1):
    ans = max(gcd(B[i-1],C[i+1]),ans)
# in case of i=0,N-1
ans = max(ans,C[1])
ans = max(ans,B[-2])
print(ans)

Submission status: Accepted

Solution code:
# coding:UTF-8


def calc_gcd(num1, num2):
    """
    最大公約数算出
    :param num1: 対象の値1
    :param num2: 対象の値2
    :return:最大公約数
    """
    if num1 < num2:
        num1, num2 = num2, num1

    while num2 > 0:
        remainder = num1 % num2

        num1 = num2
        num2 = remainder

    return num1


# 値の個数を取得
num_count = int(input())

# 最大公約数を求める対象の値群を取得
target_num = list(map(int, input().split()))

# 累積GCDリスト(可変で扱うと処理速度が遅くなるため、あらかじめ領域を確保)
left_gcd = [0] * num_count  # +1は0用の領域(1番目を除外する場合に使用)
right_gcd = [0] * num_count  # 同上

for i in range(num_count-1):
    left_gcd[i+1] = calc_gcd(left_gcd[i], target_num[i])
    right_gcd[num_count-2-i] = calc_gcd(right_gcd[num_count-1-i], target_num[num_count-1-i])

# print(left_gcd)
# print(right_gcd)

gcd = 0

for i in range(num_count):
    result = calc_gcd(left_gcd[i], right_gcd[i])
    if gcd < result:
        gcd = result

print(gcd)

Submission status: Accepted

Solution code:
import fractions
def mygcd(N,A,S):
    if S == 'R':
        A.reverse()
    ans = [0, A[0]]
    for i in range(1, N):
        ans.append(fractions.gcd(ans[i],A[i]))
    if S == 'R':
        ans.reverse()
    return ans

def GCDonBlack(N,A):
    L = mygcd(N,A,'L')
    R = mygcd(N,A,'R')
    M = [fractions.gcd(L[i], R[i+1])  for i  in range(0,N)]
    return max(M)

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

Submission status: Accepted

Solution code:
from fractions import *

n, *a = map(int, open(0).read().split())
b = [0]
for i in a:
    b += gcd(b[-1], i),
w = m = 0
for i in range(n):
    m = max(m, gcd(w, b[-i - 2]))
    w = gcd(w, a[~i])
print(m)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
 
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) #再帰定義
    
list_gcd = [(gcd(A[0],A[1]),False),(A[0],True),(A[1],True)]
#print(list_gcd)
 
for i in range(2,len(A)):
    next_gcd = []
    for j in list_gcd:
        if j[1]:
            this_gcd = (gcd(j[0],A[i]),True)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
        else:
            this_gcd = (gcd(j[0],A[i]),False)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
                
            this_gcd = (j[0],True)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
    list_gcd = next_gcd
    #print(list_gcd)
         
out = 1
for i in list_gcd:
    if i[0] > out:
        out = i[0]
        
print(out)

Submission status: Accepted

Solution code:
from fractions import *

N = int(input())
A = list(map(int,input().split()))
lsum = [0]*(N+2)
rsum = [0]*(N+2)
lsum[1] = A[0]
rsum[N] = A[-1]
for i in range(1,N):
    lsum[i+1] = gcd(lsum[i],A[i])
for i in range(N-2,-1,-1):
    rsum[i+1] = gcd(rsum[i+2],A[i])
ans = 1
for i in range(1,N+1):
    if lsum[i-1] == 0:
        ans = max(ans, rsum[i+1])
    elif rsum[i+1] == 0:
        ans = max(ans, lsum[i-1])
    else:
        ans = max(ans, gcd(lsum[i-1],rsum[i+1]))
print(ans)

Submission status: Accepted

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

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

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 x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

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

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],a[i-1])
  
for i in range(n-1)[::-1]:
  r[i] = gcd(r[i+1],a[i+1])
  
lr = [gcd(l[i],r[i]) for i in range(n)]
print(max(lr))

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import random
import string
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))

def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]

n = II()
a = LI()
left = [0] * (n+1)
right = [0] * (n+1)

for i in range(1, n+1):
    left[i] = fractions.gcd(left[i-1], a[i-1])
for i in range(n-1, -1, -1):
    right[i] = fractions.gcd(right[i+1],a[i])
maxi = -INF
for i in range(n):
    maxi = max(maxi, fractions.gcd(left[i], right[i+1]))
print(maxi)

Submission status: Accepted

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

gcd_from_the_left = []
gcd_from_the_left.append(values[0])
for i in range(N):
	gcd_from_the_left.append(fractions.gcd(gcd_from_the_left[i],values[i]))
gcd_from_the_left.pop(0)

gcd_from_the_right = []
gcd_from_the_right.append(values[-1])
for i in range(N):
	gcd_from_the_right.append(fractions.gcd(gcd_from_the_right[i],values[-i-1]))

gcd_from_the_right.pop(0)

ans = 0
gcd = 0

for i in range(N-2):
  gcd = fractions.gcd(gcd_from_the_left[i],gcd_from_the_right[N-i-3])
  if gcd > ans:
    ans = gcd
    
gcd = gcd_from_the_left[-2]
if gcd > ans:
  ans = gcd
gcd = gcd_from_the_right[-2]
if gcd > ans:
  ans = gcd
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

def gcd(x, y):
    if x == 0:
        return y
    if y == 0:
        return x
        
    if y > x:
        temp = y
        y = x
        x = temp
    amari = x % y
    if amari == 0:
        return y
    else:
        return gcd(y, amari)
        
L = list(range(N))
L[0] = 0
for i in range(N-1):
    L[i+1] = gcd(L[i], A[i])
    
R = list(range(N))
R.append(0)
for i in reversed(range(N)):
    R[i] = gcd(R[i+1], A[i])

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

print(max(M))

Submission status: Accepted

Solution code:
from functools import reduce
import fractions


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

    print(algorithm(N, A))


def algorithm(N, A):
    if N == 0:
        return 0
    if N == 1:
        return A[0]
    if N == 2:
        return max(A[0],A[1])

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

    maxGCD = R_i[1]
    for i in range(1, N-1):
        L_i = fractions.gcd(L_i, A[i - 1])
        tmp = fractions.gcd(L_i, R_i[i+1])
        if tmp > maxGCD:
            maxGCD = tmp

    L_i = gcd_list(A[:N-1])
    if L_i > maxGCD:
        maxGCD = L_i
    return maxGCD

problem()

Submission status: Accepted

Solution code:
#import math
import fractions as math

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

gcd_l, gcd_r = [0], [0]

for l, r in [(A[i], A[N-i-1]) for i in range(N)]:
    gcd_l.append(math.gcd(gcd_l[-1], l))
    gcd_r.append(math.gcd(gcd_r[-1], r))
gcd_r.reverse()

gcd_nums = [gcd_l[-1]] + [math.gcd(gcd_l[i], gcd_r[i+1]) for i in range(N)]
print(max(gcd_nums))

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
left = []
right = [0]*N
for i in range(N):
    if i == 0:
        left.append(A[i])
    else:
        left.append(gcd(left[i - 1], A[i]))
for i in reversed(range(N)):
    if i == N - 1:
        right[i] = A[i]
    else:
        right[i] = gcd(right[i+1], A[i])

ans = 0
for i in range(N):
    if i == 0:
        an_ = right[i + 1]
    elif i == N - 1:
        an_ = left[i-1]
    else:
        an_ = gcd(left[i-1], right[i+1])
    ans = max(ans, an_)
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
from sys import stdin


@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def make_acc_gdbs(As):
    result = []
    tmp = 0
    for x in As:
        tmp = gcd(tmp, x)
        result.append(tmp)
    return result


def main():
    N = int(stdin.readline().rstrip())
    As = [int(x) for x in stdin.readline().rstrip().split()]
    lAs = make_acc_gdbs(As)
    rAs = make_acc_gdbs(As[::-1])[::-1]
    max_ = 0
    for i in range(N):
        left = 0 if i == 0 else lAs[i - 1]
        right = 0 if i == (N - 1) else rAs[i + 1]
        max_ = max(max_, gcd(left, right))
    print(max_)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache, reduce


@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def sub():
    N, As = [input() for _ in range(2)]
    N = int(N)
    As = [int(e) for e in As.split(" ")]
    # As = sorted(As, reverse=True)

    memG = 0
    # if N == 2:
    # memG = gcd(As[0], As[1])
    # if N < 3:
    #     for i in range(N):
    #         tmp = As[:i] + As[i + 1 :]
    #         g = reduce(gcd, tmp)
    #         if g > memG:
    #             memG = g
    if N == 2:
        memG = max(As)
    else:
        gLeft = {0: As[0], 1: gcd(As[0], As[1])}
        for i in range(2, N):
            gI = gcd(gLeft[i - 1], As[i])
            gLeft[i] = gI
        gRight = {N - 1: As[N - 1], N - 2: gcd(As[N - 1], As[N - 2])}
        for i in range(2, N):
            gI = gcd(gRight[N - i], As[N - 1 - i])
            gRight[N - 1 - i] = gI

        buf = []
        for i in range(N):
            leftG = None
            if (i - 1) in gLeft:
                leftG = gLeft[i - 1]
            rightG = None
            if (i + 1) in gRight:
                rightG = gRight[i + 1]
            # tmpG = None
            if leftG is None:
                leftG = rightG
            elif rightG is None:
                rightG = leftG
            buf.append(gcd(leftG, rightG))
            # tmpG = gcd(leftG, rightG)
            # if tmpG > memG:
            #     memG = tmpG
        memG = max(buf)

    print("{}".format(memG))


sub()

Submission status: Accepted

Solution code:
from functools import lru_cache, reduce


@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def sub():
    N, As = [input() for _ in range(2)]
    N = int(N)
    As = [int(e) for e in As.split(" ")]
    # As = sorted(As, reverse=True)

    memG = 0
    # if N == 2:
    # memG = gcd(As[0], As[1])
    if N < 3:
        for i in range(N):
            tmp = As[:i] + As[i + 1 :]
            g = reduce(gcd, tmp)
            if g > memG:
                memG = g
    else:
        gLeft = {0: As[0], 1: gcd(As[0], As[1])}
        for i in range(2, N):
            gI = gcd(gLeft[i - 1], As[i])
            gLeft[i] = gI
        gRight = {N - 1: As[N - 1], N - 2: gcd(As[N - 1], As[N - 2])}
        for i in range(2, N):
            gI = gcd(gRight[N - i], As[N - 1 - i])
            gRight[N - 1 - i] = gI

        buf = []
        for i in range(N):
            leftG = None
            if (i - 1) in gLeft:
                leftG = gLeft[i - 1]
            rightG = None
            if (i + 1) in gRight:
                rightG = gRight[i + 1]
            # tmpG = None
            if leftG is None:
                leftG = rightG
            elif rightG is None:
                rightG = leftG
            buf.append(gcd(leftG, rightG))
            # tmpG = gcd(leftG, rightG)
            # if tmpG > memG:
            #     memG = tmpG
        memG = max(buf)

    print("{}".format(memG))


sub()

Submission status: Accepted

Solution code:
from functools import lru_cache, reduce


@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def sub():
    N, As = [input() for _ in range(2)]
    N = int(N)
    As = [int(e) for e in As.split(" ")]
    # As = sorted(As, reverse=True)

    memG = 0
    # if N == 2:
    # memG = gcd(As[0], As[1])
    if N < 10:
        for i in range(N):
            tmp = As[:i] + As[i + 1 :]
            g = reduce(gcd, tmp)
            if g > memG:
                memG = g
    else:
        gLeft = {0: As[0], 1: gcd(As[0], As[1])}
        for i in range(2, N):
            gI = gcd(gLeft[i - 1], As[i])
            gLeft[i] = gI
        gRight = {N - 1: As[N - 1], N - 2: gcd(As[N - 1], As[N - 2])}
        for i in range(2, N):
            gI = gcd(gRight[N - i], As[N - 1 - i])
            gRight[N - 1 - i] = gI

        buf = []
        for i in range(N):
            leftG = None
            if (i - 1) in gLeft:
                leftG = gLeft[i - 1]
            rightG = None
            if (i + 1) in gRight:
                rightG = gRight[i + 1]
            # tmpG = None
            if leftG is None:
                leftG = rightG
            elif rightG is None:
                rightG = leftG
            buf.append(gcd(leftG, rightG))
            # tmpG = gcd(leftG, rightG)
            # if tmpG > memG:
            #     memG = tmpG
        memG = max(buf)

    print("{}".format(memG))


sub()

Submission status: Accepted

Solution code:
from fractions import gcd


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

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

gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

gcd_array = []
for index in range(n):
    if index == 0:
        gcd_array.append(a_array[0])
    else:
        gcd_array.append(gcd(gcd_array[index - 1], a_array[index]))
gcd_reversed_array = []
for index in range(n):
    if index == 0:
        gcd_reversed_array.append(a_array[index - 1])
    else:
        gcd_reversed_array.append(gcd(gcd_reversed_array[index - 1], a_array[-(index + 1)]))

res = 0
for i in range(n):
    if i == 0:
        res = max(res, gcd_reversed_array[-2])
    elif i == n - 1:
        res = max(res, gcd_array[-2])
    else:
        res = max(res, gcd(gcd_array[i - 1], gcd_reversed_array[-i - 1 -1]))
print(res)

Submission status: Accepted

Solution code:
from fractions import gcd

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

gcd_array = []
for index in range(n):
    if index == 0:
        gcd_array.append(a_array[0])
    else:
        gcd_array.append(gcd(gcd_array[index - 1], a_array[index]))
gcd_reversed_array = []
for index in range(n):
    if index == 0:
        gcd_reversed_array.append(a_array[index - 1])
    else:
        gcd_reversed_array.append(gcd(gcd_reversed_array[index - 1], a_array[-(index + 1)]))

res = 0
gcd_reversed_array.reverse()
for i in range(n):
    if i == 0:
        res = max(res, gcd_reversed_array[1])
    elif i == n - 1:
        res = max(res, gcd_array[-2])
    else:
        res = max(res, gcd(gcd_array[i - 1], gcd_reversed_array[i+1]))
print(res)

Submission status: Accepted

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

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

Llist = [0]
Rlist = [0]

for i in range(N):
    Llist.append(gcd(Llist[i], A[i])) 
    # Rlist.insert(0, gcd(Rlist[0], A[N-1-i]))
    Rlist.append(gcd(Rlist[i], A[N-1-i]))
Rlist = Rlist[::-1]
ans = 0
for i in range(N):
    t = gcd(Llist[i], Rlist[i+1])
    if ans < t:
        ans = t

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

gcdl = [0]
gcdr = [0]

for i in range(n-1) :
    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]))

print(max(ans))

Submission status: Accepted

Solution code:
from fractions import*
a=int(input())
b=list(map(int,input().split()))
alis=[b[0]]
blis=[b[-1]]
for i in range(a-1):
  alis.extend([gcd(alis[-1],b[i+1])])
  blis.extend([gcd(blis[-1],b[-i-2])])
blis=list(reversed(blis))+[0]
alis=[0]+alis
ans=[]
for i in range(a):
	ans+=[gcd(alis[i],blis[i+1])]
print(max(ans))

Submission status: Accepted

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

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

x = [0]*n
y = [0]*n

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

z = [gcd(x[i], y[i]) for i in range(n)]

print(max(z))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
L = [A[0]]
R = [A[-1]]
for i in range(N-1):
    L.append(gcd(L[i],A[i+1]))
    R.append(gcd(R[(i)],A[-(i+2)]))
ans = []    
for i in range(N):
    if i == 0:
        ans.append(R[N - 2])
    elif i <= N - 2:
        ans.append(gcd(L[i - 1],R[N - i - 2]))
    else:
        ans.append(L[N - 2])

print(max(ans))

Submission status: Accepted

Solution code:
import fractions

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

ans = 0
left = [0]
right = [0] * (n+1)

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

for i in range(n):
  x = fractions.gcd(left[i], right[i+1])
  if ans < x:
    ans = x
print(ans)

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 = l[:]

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:

from fractions import*

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

l = [a[0]]
r = [a_r[0]]

for i in range(1, n-1):
#    print(i)
    l.append(gcd(l[i-1], a[i]))
    r.append(gcd(r[i-1], a_r[i]))

l = [0] + l
r = r[::-1] + [0]

print(max(gcd(s, t) for s, t in zip(l, r)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

forward = []
backward = [0 for x in range(n)]

if n == 2:
    print(max(a[0], a[1]))
    exit(0)

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


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


ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

forward = []
backward = [0 for x in range(n)]

if n == 2:
    print(max(a[0], a[1]))
    exit(0)

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


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


ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

forward = []
backward = [0 for x in range(n)]

if n == 2:
    print(max(a[0], a[1]))
    exit(0)

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


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


ans = 1

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

print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    L = []
    last = A[0]
    for i in range(N):
        last = fractions.gcd(last, A[i])
        L.append(last)
    last = A[-1]
    R = []
    for i in range(1, N+1):
        last = fractions.gcd(last, A[-i])
        R.append(last)
    R.reverse()
    if N == 2:
        print(max(A[0], A[1]))
        return
    maxGCD = max(L[-2], R[1])
    for i in range(1, N-1):
        maxGCD = max(fractions.gcd(L[i-1], R[i+1]), maxGCD)
    print(maxGCD)
    return


# 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 = [int(n) for n in input().split()]

from fractions import gcd
L = [0]*(N+1)
R = [0]*(N+1)
ans = 0
for i in range(N):
    L[i] = gcd(L[i-1],A[i])
for i in reversed(range(N)):
    R[i] = gcd(R[i+1],A[i])
for i in range(N):
    if gcd(L[i-1],R[i+1]) > ans:
        ans = gcd(L[i-1],R[i+1])
print(ans)

Submission status: Accepted

Solution code:
import copy
import heapq
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]
ans = []

for i in range(N):
  ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd 

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

# Lを埋める
L = [0 for _ in range(N+1)]
for i in range(1, N+1):
    if not L[i-1]:
        L[i] = A[i-1]
    else: 
        L[i] = gcd(L[i-1], A[i-1])

# Rを埋める
R = [0 for _ in range(N+1)]
for i in range(1, N+1)[::-1]:
    if not R[i]:
        R[i-1] = A[i-1] 
    else:
        R[i-1] = gcd(R[i], A[i-1])

# Mを埋める
M = [0 for _ in range(N)]
for i in range(N):
    if not L[i]:
        M[i] = R[i+1]
    elif not R[i]:
        M[i] = L[i]
    else: 
        M[i] = gcd(L[i], R[i+1])

print(max(M))

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()

import fractions
from functools import reduce
from functools import lru_cache

@lru_cache(maxsize=None)
def calc_gcd(a, b):
    return fractions.gcd(a, b)

def gcd_list(numbers):
    if len(numbers) == 0: return None
    elif len(numbers) == 1: return numbers[0]
    else: return reduce(calc_gcd, numbers)

left_gcd = [None,A_li[0]]
prev_gcd = A_li[0]
for i in range(1,N-1):
    prev_gcd = calc_gcd(prev_gcd, A_li[i])
    left_gcd.append(prev_gcd)

right_gcd = [None, A_li[N-1]]
prev_gcd = A_li[N-1]
for i in range(1,N-1):
    prev_gcd = calc_gcd(prev_gcd, A_li[N-1-i])
    right_gcd.append(prev_gcd)
right_gcd.reverse()

print(max([right_gcd[0]]+[calc_gcd(left_gcd[i], right_gcd[i]) for i in range(1,len(A_li)-1)]+[left_gcd[N-1]]))

Submission status: Accepted

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

from fractions import gcd
L = [0]*(N+1)
R = [0]*(N+1)
ans = 0
for i in range(N):
    L[i] = gcd(L[i-1],A[i])
for i in reversed(range(N)):
    R[i] = gcd(R[i+1],A[i])

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

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])
GCD = 0
GCD += LIS[N-1]
if N == 2:
    ANS = max(T[0],T[1])
else:
    #第１項がtarget
    S = copy.copy(T)
    S.pop(0)
    LS = [0]*(N-1)
    LS[0] += S[0]
    for i in range(N-2):
        LS[i+1] += gcd(LS[i],S[i+1])
    ANSA = LS[N-2]

    #その他の場合
    LJ = []
    for i in range(N-1):
        if LIS[i] != LIS[i+1]:
            LJ.append(i+1)
    if LJ == []:
        ANS =max(ANSA,LIS[0])
    else:
        LK = []
        for j in range(len(LJ)):
            U = copy.copy(T)
            U.pop(LJ[j])
            LS = [0]*(N-1)
            LS[0] += U[0]
            for i in range(N-2):
                LS[i+1] += gcd(LS[i],U[i+1])
            LK.append(LS[N-2])
        ANSB = max(LK)
        ANS = max(ANSA,ANSB)
print(ANS)

Submission status: Accepted

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

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

LN = [0] * (N)
LN[0] = AN[0]
for i in range(N - 1):
    LN[i + 1] = gcd(LN[i], AN[i + 1])

RN = [0] * (N)
RN[N - 1] = AN[N - 1]
for i in range(N - 1, 0, -1):
    RN[i - 1] = gcd(RN[i], AN[i - 1])


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