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 operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1

        return res

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

n = int(input())
a = list(map(int, input().split()))
seg = SegmentTree(n,0,gcd)
for i in range(n):
    seg.update(i,a[i])
ans = 1
for i in range(n):
    seg.update(i,0)
    ans = max(ans, seg.get(0,n))
    seg.update(i,a[i])
print(ans)

Submission status: Accepted

Solution code:
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 1
        while self.size < size:
            self.size *= 2
        self.dat = [default for i in range(self.size*2-1)]
        self.op = op

    def update(self, i, x):
        i += self.size - 1
        self.dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] = self.op(self.dat[i*2+1], self.dat[i*2+2])

    def add(self, i, x):
        i += self.size - 1
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b, k = None, l = None, r = None):
        if k is None:
            k = 0
            l = 0
            r = self.size

        if r <= a or b <= l:
            return None

        if a <= l and r <= b:
            return self.dat[k]

        res_l = self.get(a, b, k*2+1, l, (l+r)//2)
        res_r = self.get(a, b, k*2+2, (l+r)//2, r)
        if res_l is None:
            return res_r
        if res_r is None:
            return res_l
        return self.op(res_l, res_r)


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

n = int(input())
a = list(map(int, input().split()))
seg = SegmentTree(n,0,gcd)
for i in range(n):
    seg.update(i,a[i])
ans = 1
for i in range(n):
    seg.update(i,0)
    ans = max(ans, seg.get(0,n))
    seg.update(i,a[i])
print(ans)

Submission status: Accepted

Solution code:
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 1
        while self.size < size:
            self.size *= 2
        self.dat = [default]*(self.size*2-1)
        self.op = op

    def update(self, i, x):
        i += self.size - 1
        self.dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] = self.op(self.dat[i*2+1], self.dat[i*2+2])

    def add(self, i, x):
        i += self.size - 1
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b, k = None, l = None, r = None):
        if k is None:
            k = 0
            l = 0
            r = self.size

        if r <= a or b <= l:
            return None

        if a <= l and r <= b:
            return self.dat[k]

        res_l = self.get(a, b, k*2+1, l, (l+r)//2)
        res_r = self.get(a, b, k*2+2, (l+r)//2, r)
        if res_l is None:
            return res_r
        if res_r is None:
            return res_l
        return self.op(res_l, res_r)
def gcd(a,b):
    if a == 0:
        return b
    if b == 0:
        return a
    return gcd(b%a, a)

n = int(input())
a = list(map(int, input().split()))
seg = SegmentTree(n,0,gcd)
for i in range(n):
    seg.update(i,a[i])
ans = 1
for i in range(n):
    seg.update(i,0)
    ans = max(ans, seg.get(0,n))
    seg.update(i,a[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)

res = [0] * N
l = [0] * (N+1)
r = [0] * (N+1)

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

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

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

print(max(res))

Submission status: Accepted

Solution code:
import fractions

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

for i in range(1, N+1):
  L[i] = fractions.gcd(L[i-1], A[i-1]) 
  R[N-i+1] = fractions.gcd(R[N-i+2], A[N-i+2])
ans = 0
for i in range(1, N+1):
  rest_gcd = fractions.gcd(L[i], R[i])
  ans = max(ans, rest_gcd)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
 
l = [0]*(N+1)
r = [0]*(N+1)

for i in range(N):
	l[i+1] = gcd(l[i], A[i])
for i in reversed(range(N)):	
	r[i] = gcd(r[i+1],A[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 fractions

N = int(input())
A = [0] + list(map(int, input().split()))


l = [0, A[1]] + [0] * (N - 1)
r = [0] * N + [A[N]]

for i in range(2, N + 1):
	l[i] = fractions.gcd(l[i - 1], A[i])
for i in reversed(range(1, N)):
	r[i] = fractions.gcd(r[i + 1], A[i])

gcds = [r[2]]
for i in range(2, N):
	gcds.append(fractions.gcd(l[i - 1], r[i + 1]))
gcds.append(l[N - 1])

print(max(gcds))

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect


def divisor(n):  # nの約数を全て求める
    i = 1
    div_set = set()
    while i * i <= n:
        if n % i == 0:
            div_set.add(i)
            div_set.add(n//i)
        i += 1
    return div_set


def divisor2(n):  # 既存のリストからnの約数だけを返す
    div_set = set()

    for i in kouho:
        if i > n:
            return div_set
        if n % i == 0:
            div_set.add(i)
    return div_set


N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
max_index = bisect.bisect_left(A_list, A_list[-1])
# print(max_index)
times = max_index

divcount = defaultdict(int)
for n in A_list[:2]:
    # print(n)
    for i in divisor(n):
        divcount[i] += 1

kouho = list(divcount.keys())
kouho.sort()
# print(kouho)

for n in A_list[2:max_index+1]:
    # print(n)
    for i in divisor2(n):
        divcount[i] += 1

# print(divcount)
max_divisor = 0
for key, value in divcount.items():
    if value >= max_index and key > max_divisor:
        max_divisor = key

print(max_divisor)

Submission status: Accepted

Solution code:
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

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

    #累積GCD
    left = [0]*n
    right = [0]*n

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

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

Submission status: Accepted

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

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

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

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

print(gcd)

Submission status: Accepted

Solution code:
import fractions

def mygcd(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    else:
        return fractions.gcd(a, b)
N = int(input())
A = list(map(int, input().split()))

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

M = []
for i in range(N):
    M.append(mygcd(L[i], R[i]))
print(max(M))

Submission status: Accepted

Solution code:
def Gcd(x,y):
    if( y>x ): # x>yにする
        r = x
        x = y
        y = r
    if( y==0 ):
        return x
    return Gcd(y,x%y)

import sys
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
MAX = 10**5+5

def resolve():
    n = int(input())
    a = [0]
    a.extend(list(map(int,input().split())))
    leftmax = [0]*(n+2)
    rightmax = [0]*(n+2)
    leftmax[1]=a[1]
    rightmax[n]=a[-1]
    for i in range(2,n):
        r=n-i+1
        leftmax[i]=Gcd(leftmax[i-1],a[i])
        rightmax[r]=Gcd(rightmax[r+1],a[r])
    ans = 0
    for i in range(1,n+1):
        s = Gcd(leftmax[i-1],rightmax[i+1])
        ans = max(ans,s)
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import fractions
n=int(input())
a=list(map(int, input().split())) 
b=[0]
c=[0]
ans=[]
for i in range(n):
    b.append(fractions.gcd(b[i],a[i]))
    c.append(fractions.gcd(c[i],a[-i-1]))
del b[n]
del c[n]
 
for i in range(n):
    d=b[i]
    e=c[n-1-i]
    ans.append(fractions.gcd(d,e))
print(max(ans))

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[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

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

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

Ls = [As[-1]] + list(accumulate(As, gcd))
Rs = list(accumulate(As[::-1], gcd))[::-1] + [As[0]]

ans = 0
for i in range(N):
    g = gcd(Ls[i], Rs[i+1])
    ans = max(ans, g)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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[-1], a[i+1]))
  r.append(gcd(r[-1], a[-2-i]))
r = r[::-1]

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

Submission status: Accepted

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


a = int(input())
b = list(map(int, input().split()))
c = [0] * (a + 1)
d = [0] * (a + 1)
for i in range(1, a + 1):
    c[i] = g_c_d(b[i-1], c[i-1])
    d[-i-1] = g_c_d(b[-i], d[-i])
e = 0
for i in range(len(c)-1):
    e = max(e, g_c_d(c[i], d[i+1]))
print(e)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

########

n = i_inpl()

# a, bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

# リストnumbers最大公約数
def gcdlist(numbers):
    a = numbers[0]
    for i in range(len(numbers)):
        a = gcd(a, numbers[i])
    return a

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

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

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=list(map(int, input().split()))

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

ans = 0

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

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


print(ans)

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

Z=[gcd(L[i],R[i]) for i in range(N)]

print(max(Z))

Submission status: Accepted

Solution code:
import fractions

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

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

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

Submission status: Accepted

Solution code:
#125

import math
import fractions

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

L = [0] *(N+2)
R = [0] *(N+2)
ans = 0

#漸化式的に最大公約数算出(前から順に算出)
for j in range(0,N-1):
    L[j + 1] = fractions.gcd(L[j], A[j])
#漸化式的に最大公約数算出(後ろから順に算出)
for j in range(N -1,0,-1):
    R[j - 1] = fractions.gcd(R[j], A[j])
for j in range(0,N):
    if ans < fractions.gcd(L[j],R[j]):
        ans = fractions.gcd(L[j],R[j])

print(ans)

Submission status: Accepted

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

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

gcdL = [0] * N
gcdR = [0] * N
gcdL[0] = A[0]
gcdR[N-1] = A[N-1]

for i in range(1, N) :
    gcdL[i] = gcd(gcdL[i-1], A[i])
    gcdR[N-1-i] = gcd(gcdR[N-i], A[N-1-i])
  
ret = max(gcdL[N-2], gcdR[1])
for i in range(1, N - 1) :
    ret = max(ret, gcd(gcdL[i-1], gcdR[i+1]))

print(ret)

Submission status: Accepted

Solution code:
import fractions as f

N = int(input())

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

rightGCD = [0]*N
leftGCD = [0]*N

for i in range(N-1):
    leftGCD[i+1] = f.gcd(leftGCD[i],A[i])
    rightGCD[-i-2] = f.gcd(rightGCD[-i-1],A[-i-1])

#print(leftGCD)
#print(rightGCD)

ans = 0

for i in range(N):
    ans = max(ans,f.gcd(rightGCD[i],leftGCD[i]))

print(ans)

Submission status: Accepted

Solution code:
import sys

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

def get_cum_gcd(N, As):
    cum_gcd = [0] * N
    for i, n in enumerate(As):
        if i == 0:
            cum_gcd[i] = n
        else:
            cum_gcd[i] = gcd(cum_gcd[i-1], n)
    return cum_gcd

def get_cav_gcds(N, cum_l, cum_r):
    cav_gcds = [0] * N
    for i in range(N):
        if i == 0:
            cav_gcds[i] = cum_r[i+1]
        elif i == N-1:
            cav_gcds[i] = cum_l[i-1]
        else:
            cav_gcds[i] = gcd(cum_l[i-1], cum_r[i+1])
    return cav_gcds

def main():
    input = sys.stdin.readline
    N = int(input())
    As = list(map(int, input().split()))
    cum_l = get_cum_gcd(N, As)
    cum_r = list(reversed(get_cum_gcd(N, reversed(As))))
    cav_gcds = get_cav_gcds(N, cum_l, cum_r)
    print(max(cav_gcds))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions

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

ans = 0

lf = [0]*N
rf = [0]*N

for i in range(1,N):
    lf[i] = fractions.gcd(lf[i-1],a[i-1])
    rf[i] = fractions.gcd(rf[i-1],a[-i])

ans = 0
for i in range(N):
    ans = max(ans,fractions.gcd(lf[i],rf[-i-1]))

print(ans)

Submission status: Accepted

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

L = [0] * N
for i in range(N) :
        if i == 0 :
                L[0] = 0
        elif i == 1 :
                L[1] = a[0]
        else :
                L[i] = fractions.gcd(L[i-1], a[i-1])

a.reverse()
R = [0] * N
for i in range(N) :
        if i == 0 :
                R[0] = 0
        elif i == 1 :
                R[1] = a[0]
        else :
                R[i] = fractions.gcd(R[i-1], a[i-1])
R.reverse()
a.reverse()

gcd = [0] * N
for i in range(N) :
        if i == 0 :
                gcd[0] = R[0]
        elif i == N-1 :
                gcd[N-1] = L[N-1]
        else :
                gcd[i] = fractions.gcd(L[i],R[i])

print(max(gcd))

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
a_list = list(map(int, input().split()))
gcd_l = [0] * (N+1) 
gcd_r = [0] * (N+1) 
for i, a in enumerate(a_list):
    gcd_l[i+1] = gcd(gcd_l[i], a)
for i in range(N, 0, -1):
    a = a_list[i-1]
    gcd_r[i-1] = gcd(gcd_r[i], a)
ans = 1
# print(gcd_l, gcd_r)
for i in range(N):
    tmp = gcd(gcd_l[i], gcd_r[i+1])
    if (ans < tmp):
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

l = [0]*n
r = [0]*n
l[0] = an[0]
r[n-1] = an[n-1]

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

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

Submission status: Accepted

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


a = int(input())
b = list(map(int, input().split()))
b.append(0)
b.insert(0, 0)
c = [0]*(len(b))
d = [0]*(len(b))
for i in range(1, len(b)):
    c[i] = (g_c_d(b[i], c[i-1]))
    d[-i-1] = (g_c_d(b[-i-1], d[-i]))
e = 0
for i in range(0, len(c)-2):
    e = max(g_c_d(c[i], d[i+2]), e)
print(e)

Submission status: Accepted

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


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

gl = []
g = 0
for aa in a:
    g = gcd(g, aa)
    gl.append(g)
gl = tuple(gl)

gr = []
g = 0
for aa in reversed(a):
    g = gcd(g, aa)
    gr.append(g)
gr = tuple(reversed(gr))

ans = 0
for rm in range(n):
    if rm - 1 < 0:
        ans = max(ans, gr[rm + 1])
    elif rm + 1 >= len(gr):
        ans = max(ans, gl[rm - 1])
    else:
        ans = max(ans, gcd(gl[rm - 1], gr[rm + 1]))
print(ans)

Submission status: Accepted

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


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

gl = []
g = 0
for aa in a:
    g = gcd(g, aa)
    gl.append(g)

gr = []
g = 0
for aa in reversed(a):
    g = gcd(g, aa)
    gr.append(g)
gr = list(reversed(gr))

ans = 0
for rm in range(n):
    if rm - 1 < 0:
        ans = max(ans, gr[rm + 1])
    elif rm + 1 >= len(gr):
        ans = max(ans, gl[rm - 1])
    else:
        ans = max(ans, gcd(gl[rm - 1], gr[rm + 1]))
print(ans)

Submission status: Accepted

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

st = set()
for tar in a[:2]:
    i = 1
    while i * i <= tar:
        if tar % i == 0:
            st.add(i)
            st.add(tar // i)
        i += 1

for d in sorted(st, reverse=True):
    cnt = 0
    for aa in a:
        if aa % d != 0:
            cnt += 1
        if cnt > 1:
            break
    else:
        print(d)
        exit()

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
n=0
i=0
while(n<N):
    i+=1
    n=2**i
INF=0
dat=[INF]*(2*n-1)
def update(i,x):
    i+=n-1
    dat[i]=x
    while(i>0):
        i=(i-1)//2
        dat[i]=gcd(dat[i*2+1],dat[i*2+2])
def find(a,b,k,l,r):
    if r<=a or b<=l:
        return INF
    if a<=l and r<=b:
        return dat[k]
    else:
        vl=find(a,b,k*2+1,l,(l+r)//2)
        vr=find(a,b,k*2+2,(l+r)//2,r)
        return gcd(vl,vr)
for i in range(N):
    update(i,A[i])
ans=0
for i in range(N):
    f=find(0,i,0,0,n)
    g=find(i+1,N,0,0,n)
    ans=max(gcd(f,g),ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


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


def gcd_m(*args):
    if len(args) == 0:
        return 0
    if len(args) == 1:
        return args[0]
    if len(args) >= 2:
        ret = gcd(args[0], args[1])

    for value in args[2:]:
        ret = gcd(ret, value)
    return ret


def solve(inputs):
    [N] = string_to_int(inputs[0])
    # A = [0] + (string_to_int(inputs[1])) + [0]
    A = string_to_int(inputs[1])

    if N == 2:
        return max(A)

    left_gcd_memo = deque([0])
    right_gcd_memo = deque([0])

    for v in A:
        left_gcd_memo.append(gcd(left_gcd_memo[-1], v))
    left_gcd_memo.append(0)
    for v in reversed(A):
        right_gcd_memo.appendleft(gcd(right_gcd_memo[0], v))
    right_gcd_memo.appendleft(0)

    max_gcd = 0
    for i in range(0, len(A)):
        left = left_gcd_memo[i]
        right = right_gcd_memo[i+2]
        g = gcd(left_gcd_memo[i], right_gcd_memo[i+2])
        max_gcd = g if g > max_gcd else max_gcd

    return max_gcd


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(2))
    print(ret)

Submission status: Accepted

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

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

    l[0] = a[0]
    r[-1] = a[-1]

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

    print(ans)





main()

Submission status: Accepted

Solution code:
import fractions

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

L = [0]
R = [0]
ans_list = []

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

for j in range(n):
    ans_list.append(fractions.gcd(L[j], R[-j-1]))

print(max(ans_list))

Submission status: Accepted

Solution code:
import fractions

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

ans = 0

ls = [0]*n
rs = [0]*n

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

ans = 0
for i in range(n):        
    ans = max(ans,fractions.gcd(ls[i],rs[-i-1]))

print(ans)

Submission status: Accepted

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


N = int(input())
A = list(map(int,input().split()))
L = [] #[A[0], gcd(A[0], A[1]), gcd(A[0], A[1], A[2]), ...,gcd(A[0], ..., A[N-2]) -> N-1個の要素
R = [] #[A[N-1], gcd(A[N-1], A[N-2]), gcd(A[N-1], A[N-2], A[N-3]), ... ,gcd(A[N-1], A[N-2], A[N-3], ..., A[1])]

L.append(A[0])
R.append(A[-1])
for i in range(1, N-1):
    L.append(gcd(L[i-1], A[i]))
    R.append(gcd(R[i-1], A[N-1-i]))
ans = max(R[-1], L[-1])
for i in range(N-2):
    val = gcd(L[i], R[N-i-3])
    if val > ans:
        ans = val
print(str(ans))

Submission status: Accepted

Solution code:
from fractions import gcd


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

# l[i] := [0, i]の数のGCDメモ
l = [None for _ in range(N)]
l[0] = A[0]
for i in range(1, N):
    l[i] = gcd(l[i - 1], A[i])

# r[i] := [i, N - 1]の数のGCDメモ
r = [None for _ in range(N)]
r[N - 1] = A[N - 1]
for i in reversed(range(N - 1)):
    r[i] = gcd(r[i + 1], A[i])

ans = 0
for i in range(N):
    if i == 0:
        ans = max(ans, r[1])
    elif i == N - 1:
        ans = max(ans, l[N - 2])
    else:
        ans = max(ans, gcd(l[i - 1], r[i + 1]))
print(ans)

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y:
		return x
	return y

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

N = int(input())
A = list(map(int, input().split()))
gcdL = [A[0]]
for i in range(1, N):
	gcdL.append(euc(gcdL[-1], A[i]))
gcdR = [A[-1]]
for i in range(1, N):
	gcdR.append(euc(gcdR[-1], A[-1-i]))
gcdR.reverse()
max = gcdR[1]
for i in range(1, N-1):
	max = larger(max, euc(gcdL[i-1], gcdR[i+1]))
max = larger(max, gcdL[-2])
print(max)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

import fractions
from functools import reduce

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

def mygcd(a,b):
    if a==0:
        return b
    elif b==0:
        return a
    else:
        return fractions.gcd(a,b)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ls = list(map(int, input().split()))
p = 50
ans = 0
if p>n:p=n

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

def cul(n, x):
    l = len(x)
    b = [x[i] for i in range(l)]
    b.pop(n)
    tmp = b[0]
    for i in range(1, l-1):
        tmp = gcd(tmp, b[i])
    return tmp
    
for i in range(p):
    s = cul(i,ls[:p])
    if s > ans:
        ans = s
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

# +1 shifted
dp_l = [0] * (N + 1)
dp_r = [0] * (N + 1)

dp_l[0] = 0
dp_r[0] = 0

for i in range(1, N):
    dp_l[i] = gcd(dp_l[i - 1], AAA[i - 1])
    dp_r[i] = gcd(dp_r[i - 1], AAA[-i])

max_gcd = 0
for i in range(N + 1):
    gcd_cand = gcd(dp_l[i], dp_r[N - i - 1])
    max_gcd = max(gcd_cand, max_gcd)

print(max_gcd)

Submission status: Accepted

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


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

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

ans = 0
for i in range(n):
    ans = max(ans, gcd(b[i], c[n - i - 1]))

print(ans)

Submission status: Accepted

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#解説の方針にしたがった
import fractions

N = int(input())
X = list(map(int, input().split()))
   
M = 1  
L = [0 for i in range(100004)] #L(0)=0
R = [0 for i in range(100004)]  #R(N+1) = 0

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

for i in reversed(range(N)):
  #print(i)
  R[i] = (fractions.gcd(R[i+1],X[i]))
    
ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
import sys

def gcd(a, b):
	if a < b:
		a, b = b, a
	if not b:
		return a
	return gcd (b, a % b)
	
n = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(100004)]
r = [0 for i in range(100004)]

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

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

Submission status: Accepted

Solution code:
import sys

def gcd(a, b):
	if a < b:
		a, b = b, a
	if not b:
		return a
	return gcd (b, a % b)
	
n = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(100004)]
r = [0 for i in range(100004)]

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


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

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

Submission status: Accepted

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


N = int(input())
A = [0] + list(map(int, input().split()))

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

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

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

print(ret)

Submission status: Accepted

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