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: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
from math import gcd
def main():
    n, *a = map(int, read().split())

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

    from math import sqrt
    from math import ceil
    maxa = max(a)
    maxa2 = ceil(sqrt(maxa))
    maxa2 = max(6, maxa2)  # maxa2が6未満だとエラーになる
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    prime_list = [i for i, b in enumerate(p) if b]

    r = 1
    flag = True
    jo = -1
    for pre in prime_list:
        while True:
            c = [ae % pre == 0 for ae in a]
            if all(c):
                r *= pre
                a = [ae // pre for ae in a]
            else:
                if c.count(0) == 1:
                    if flag:
                        jo = c.index(0)
                        flag = False
                        r *= pre
                        a = [ae // pre for ae in a]
                    else:
                        if jo == c.index(0):
                            r *= pre
                            a = [ae // pre for ae in a]
                        else:
                            break
                else:
                    break
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
def main():
    n, *a = map(int, read().split())

    from math import sqrt
    from math import ceil
    maxa = max(a)
    maxa2 = ceil(sqrt(maxa))
    maxa2 = max(6, maxa2)  # maxa2が6未満だとエラーになる
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    prime_list = [i for i, b in enumerate(p) if b]

    r = 1
    flag = True
    jo = -1
    for pre in prime_list:
        while True:
            c = [ae % pre == 0 for ae in a]
            if all(c):
                r *= pre
                a = [ae // pre for ae in a]
            else:
                if c.count(0) == 1:
                    if flag:
                        jo = c.index(0)
                        flag = False
                        r *= pre
                        a = [ae // pre for ae in a]
                    else:
                        if jo == c.index(0):
                            r *= pre
                            a = [ae // pre for ae in a]
                        else:
                            break
                else:
                    break
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import math
l_gcd = []
r_gcd = []

c = a[0]
for i in a[::-1]:
  c = math.gcd(c, i)
  l_gcd.append(c)
  
c = a[-1]
for j in a[1:][::-1]:
  c = math.gcd(c, j)
  r_gcd.append(c)
  
ans = max(r_gcd[-1], l_gcd[-1])
for r, l in zip(r_gcd[:-1], l_gcd[:-1][::-1]):
  c = math.gcd(r, l)
  ans = max(ans, c)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
dp_left=[0]*(N+1)
dp_right=[0]*(N+1)
for i in range(N):#左から累積GCD
  dp_left[i+1]=math.gcd(dp_left[i],A[i])
  dp_right[N-i-1]=math.gcd(dp_right[N-i],A[N-1-i])#右から累積GCD

print(dp_left)
print(dp_right)


ans = 0
for i in range(N):
  ans = max(ans,math.gcd(dp_left[i],dp_right[i+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
dp_left=[0]*N
dp_right=[0]*N
dp_left[0]=A[0]
dp_right[N-1]=A[N-1]
for i in range(1,N):#左から累積GCD
  dp_left[i]=math.gcd(dp_left[i-1],A[i])
for j in range(N-2,-1,-1):#右から累積GCD
  dp_right[j]=math.gcd(dp_right[j+1],A[j])

#print(dp_left)
#print(dp_right)

dp_left.append(0)
dp_right.append(0)

dp_left.insert(0,0)
dp_right.insert(0,0)


ans = 0
for i in range(N-1):
  ans = max(ans,math.gcd(dp_left[i],dp_right[i+2]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def segfunc(x, y):
    """
    区間(x,y)に対して行いたい操作の入力
    最小値：min(x,y)
    最大値：max(x,y)
    和：x + y
    積：x * y
    最大公約数：math.gcd(x, y)
    """
    return math.gcd(x, y)


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    ma = max(A)
    res = 0

    ide_ele = 0
    seg = SegTree(A, segfunc, ide_ele)

    for i in range(n):
        tmp = A[i]
        seg.update(i, ma)
        g = seg.query(0, n)
        res = max(res, g)
        seg.update(i, tmp)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def segfunc(x, y):
    """
    区間(x,y)に対して行いたい操作の入力
    最小値：min(x,y)
    最大値：max(x,y)
    和：x + y
    積：x * y
    最大公約数：math.gcd(x, y)
    """
    return math.gcd(x, y)


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    ma = max(A)
    res = 0

    ide_ele = ma
    seg = SegTree(A, segfunc, ide_ele)

    for i in range(n):
        tmp = A[i]
        seg.update(i, ma)
        g = seg.query(0, n - 1)
        res = max(res, g)
        seg.update(i, tmp)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict, Counter
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)

def fix(arr, d = 0):
	lis = [0]*len(arr)
	if d:
		gcd_ = arr[-1]
		for i in range(len(arr)-1, -1, -1):
			gcd_ = gcd(gcd_, arr[i])
			lis[i] = gcd_
	else:
		gcd_ = arr[0]
		for i in range(len(arr)):
			gcd_ = gcd(gcd_, arr[i])
			lis[i] = (gcd_)
	return(lis)

def solve():
	n = int(inp()); a = read()
	if n == 2:
		print(gcd(a[0], a[1]))
		exit()
	pref_gcd = fix(a)
	suf_gcd = fix(a, 1)
	# print(pref_gcd, suf_gcd)
	ans = pref_gcd[1]
	for i in range(n):
		if i == 0:
			ans = max(ans, suf_gcd[i+1])
		elif i == n-1:
			ans = max(ans, pref_gcd[i-1])
		else:
			ans = max(ans, gcd(pref_gcd[i-1], suf_gcd[i+1]))
	print(ans)

	





		

if __name__ == "__main__":
	solve()

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict, Counter
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)

def fix(arr, d = 0):
	lis = [0]*len(arr)
	if d:
		gcd_ = arr[-1]
		for i in range(len(arr)-1, -1, -1):
			gcd_ = gcd(gcd_, arr[i])
			lis[i] = gcd_
	else:
		gcd_ = arr[0]
		for i in range(len(arr)):
			gcd_ = gcd(gcd_, arr[i])
			lis[i] = (gcd_)
	return(lis)

def solve():
	n = int(inp()); a = read()
	pref_gcd = fix(a)
	suf_gcd = fix(a, 1)
	# print(pref_gcd, suf_gcd)
	ans = pref_gcd[1]
	for i in range(n):
		if i == 0:
			ans = max(ans, suf_gcd[i+1])
		elif i == n-1:
			ans = max(ans, pref_gcd[i-1])
		else:
			ans = max(ans, gcd(pref_gcd[i-1], suf_gcd[i+1]))
	print(ans)

	





		

if __name__ == "__main__":
	solve()

Submission status: Wrong Answer

Solution code:
# Segment tree (GCD)
class SegmentTree:
    _f = None
    _data = None
    _offset = None
    _size = None

    def __init__(self, size, f):
        self._f = f
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = data[i * 2 + 1] + data[i * 2 + 2]

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        f = self._f
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = next(it)
        for e in it:
            result = f(result, e)
        return result


from math import gcd

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

st = SegmentTree(N, gcd)
st.build(A)

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, st.query(0, N - 1))
print(result)

Submission status: Wrong Answer

Solution code:
"""
累積GCD
"""

import sys
sys.setrecursionlimit(10**6)

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

from math import gcd

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

for i in range(n-1):
    L[i+1] = gcd(L[i], A[i])
for i in range(n-1, 1, -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: Wrong Answer

Solution code:
"""
累積GCD
"""

import sys
sys.setrecursionlimit(10**6)

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

from math import gcd

L = [0] * (n+1)
R = [0] * (n+1)

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

if N==2:
    print(max(A))
else:
    L=[0 for _ in range(N)]
    R=[0 for _ in range(N)]
    L[0]=A[0]
    R[-1]=A[-1]
    for i in range(1,N):
        L[i]=gcd(A[i-1],L[i-1])
        R[N-1-i]=gcd(A[N-i],R[N-i])
    print(L)
    print(R)
    ans=max(L[-1],R[0])
    for j in range(1,N-1):
        ans=max(ans,gcd(L[j],R[j]))
    print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

r1=A[1]
a=A[0]

for i in range(2,N):
    r1=max(gcd(A[i],r1),a)
    a=gcd(a,A[i])

if N==2:
    print(max(A))
elif N==3:
    print(max(gcd(A[0],A[1]),gcd(A[1],A[2]),gcd(A[2],A[0])))
else:
    print(r1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N==2: print(max(A));exit()
from math import gcd
L = {}
R = {}
L[0] = A[0]
R[N-1] = A[-1]
ans = 0
for i in range(1,N):
    L[i] = gcd(L[i-1],A[i])
    R[N-i-1] = gcd(R[N-i],A[N-i-1])
for i in range(2,N):
    ans = max(ans,gcd(L[i-2],R[i]))
ans = max(ans,R[1])
ans = max(ans,L[N-1])
ans = max(ans,R[0])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N==2: print(max(A));exit()
from math import gcd
L = {}
R = {}
L[0] = A[0]
R[N-1] = A[-1]
ans = 0
for i in range(1,N):
    L[i] = gcd(L[i-1],A[i])
    R[N-i-1] = gcd(R[N-i],A[N-i-1])
for i in range(2,N):
    ans = max(ans,gcd(L[i-2],R[i]))
ans = max(ans,R[1])
ans = max(ans,L[N-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
*a,=map(int,input().split())
a=sorted(a)
from math import gcd

for i in range(n):
    if i==0:
        tmp=a[i]
    else:
        tmp=gcd(tmp, a[i])

b=[x//tmp for x in a]

for i in range(n):
    if i==0:
        tmp=b[i]
    else:
        tmp=gcd(tmp, b[i])
        if tmp==1:
            l=i-1
            r=i
            break
if l>0:
    c=a[:l]+a[l+1:]
else:
    c=a[1:]
if r+1<n:
    d=a[:r]+a[r+1:]
else:
    d=a[:r]

for i in range(len(c)):
    if i==0:
        ctmp=c[i]
        dtmp=d[i]
    else:
        ctmp=gcd(ctmp, c[i])
        dtmp=gcd(dtmp, d[i])

print(max(ctmp,dtmp))

Submission status: Wrong Answer

Solution code:
n=int(input())
*a,=map(int,input().split())
a=sorted(a)
from math import gcd

for i in range(n):
    if i==0:
        tmp=a[i]
    else:
        tmp=gcd(tmp, a[i])

b=[x//tmp for x in a]

for i in range(n):
    if i==0:
        tmp=b[i]
    else:
        tmp=gcd(tmp, b[i])
        if tmp==1:
            l=i-1
            r=i
            break

c=a[:l]+a[l+1:]
d=a[:r]+a[r+1:]

for i in range(n-1):
    if i==0:
        ctmp=c[i]
        dtmp=d[i]
    else:
        ctmp=gcd(ctmp, c[i])
        dtmp=gcd(dtmp, d[i])

print(max(ctmp,dtmp))

Submission status: Wrong Answer

Solution code:
n=int(input())
*a,=map(int,input().split())
a=sorted(a)
from math import gcd
for i in range(n):
    if i==0:
        tmp=a[i]
    else:
        tmp=gcd(tmp, a[i])

b=[x//tmp for x in a]

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

c=a[:l]+a[l+1:]
d=a[:r]+a[r+1:]

for i in range(n-1):
    if i==0:
        ctmp=c[i]
        dtmp=d[i]
    else:
        ctmp=gcd(ctmp, c[i])
        dtmp=gcd(dtmp, d[i])

print(max(ctmp,dtmp))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

left = [A[0]] * N
right = [A[-1]] * N

import math

for i in range(1, N):
  left[i] = math.gcd(left[i - 1], A[i])
  
for i in range(N - 2,-1,-1):
  right[i] = math.gcd(right[i + 1], A[i])
  
ans = max(right[N - 2],left[1])
for i in range(1,N - 1):
  g = math.gcd(left[i - 1],right[i + 1])
  if ans < g:
    ans = g
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections
INF = 10**18
ans = 0
import math

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    l = 1
    for i in range(1,n):
        c = math.gcd(a[0],a[i])
        ans = max(ans,c)
    print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce

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

def gcd(numbers):
    return reduce(gcd1, numbers)

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

ans = []

if len(A) == 1:
    ans.append(A[0])
else:
    ans.append(gcd(A[1:]))
    ans.append(gcd(A[:N]))

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

print(max(ans))

Submission status: Wrong Answer

Solution code:
import fractions
from functools import reduce

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

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

ans = []

if len(A) == 1:
    ans.append(A[0])
else:
    ans.append(gcd(A[1:]))
    ans.append(gcd(A[:N]))

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

print(max(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
	a,b=max(a,b),min(a,b)
	return a if b==0 else gcd(b,a%b)
def GCD(t):
	if len(t)==0:
		return 0
	l=t[0]
	r=t[-1]
	for i in range(1,len(t)//2):
		l=gcd(l,t[i])
		r=gcd(r,t[-i-1])
	return gcd(l,r)
n=int(input())
a=list(map(int,input().split()))
m=1
for i in range(n):
	t=a[:i]+a[i+1:]
	m=max(GCD(t),m)
print(m)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
	a,b=max(a,b),min(a,b)
	return a if b==0 else gcd(b,a%b)
def GCD(t):
	if len(t)==0:
		return 0
	l=t[0]
	r=t[-1]
	for i in range(1,len(t)//2):
		l=gcd(l,t[i])
		r=gcd(r,t[-i-1])
	return gcd(l,r)

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

Submission status: Wrong Answer

Solution code:
import collections

def gcd(u,v):
	if v:
		return gcd(v, u % v)
	else:
		return u

n = int(raw_input())
elems = map(int , raw_input().split(' '))
dpp = [ None ] * len(elems)
dps = [ None ] * len(elems)
dpp[0] = elems[0]
for i in range(1,len(elems)): 
	dpp[i] = gcd(elems[i], dpp[i-1])
dps[len(elems) -1]  = elems[-1]
for i in range(len(elems) - 2, -1, -1)[::-1]: 
	dps[i] = gcd(elems[i], dps[i+1])
r = 0
for i in range(len(elems)):
	u,v = dpp[i-1] if i-1 >= 0 else -1, dps[i+1] if i+1 < len(elems) else -1
	r  = max(r, gcd(u,v) if u != -1 and v != -1 else max(u,v))
print r

Submission status: Wrong Answer

Solution code:
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections,math,fractions
sys.setrecursionlimit(1000000)
INF = float("inf")

N = int(sys.stdin.readline())
A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

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

right =[A[N-1]]*(N+1)
for i in range(N)[::-1]:
    right[i] = fractions.gcd(right[i+1],A[i])

#print(left,right)
#print(left[1],right[1],left[-2],right[-2])
l = 0
r = N

while l < r and left[r] == right[l]:
    r -= 1
    l += 1
#print(left[r],right[l],l,r)
if abs(r-l)>1:
    print(min(left[r],right[l]))
elif min(left[1],right[1])==min(left[-2],right[-2]):
    print(fractions.gcd(left[1],right[-2]))
else:
    print(max(min(left[1],right[1]),min(left[-2],right[-2])))
# ret = 0
# for i in range(N):
#     print(left[i],right[i+1])
#     ret = max(ret,min(left[i],right[i+1]))
#print(ret)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections,math,fractions
sys.setrecursionlimit(1000000)
INF = float("inf")

N = int(sys.stdin.readline())
A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

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

right =[A[N-1]]*(N+1)
for i in range(N)[::-1]:
    right[i] = fractions.gcd(right[i+1],A[i])

#print(left,right)
#print(left[1],right[1],left[-2],right[-2])
if min(left[1],right[1])==min(left[-2],right[-2]):
    print(fractions.gcd(left[1],right[-2]))
else:
    print(max(min(left[1],right[1]),min(left[-2],right[-2])))
# ret = 0
# for i in range(N):
#     print(left[i],right[i+1])
#     ret = max(ret,min(left[i],right[i+1]))
#print(ret)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

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

N = ii()
A = li()

forward = [0]*(N+1)
backward = [0]*(N+1)

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

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

ans = 0
for i in range(N):
    ans = max(ans, gcd(forward[i], backward[N-1-i]))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
from functools import reduce

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

def gcd_list(numbers):
    return reduce(segfunc, numbers)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


n = ii()
A = li()

#####単位元######
if n == 2:
    print(max(A))
    exit()
elif n == 3:
    ide_ele = max(segfunc(A[0], A[1]), segfunc(A[1], A[2]), segfunc(A[0], A[2]))
else:
    ide_ele = max(segfunc(A[0], A[1]), segfunc(A[2], A[3]))

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(A)
ans = 0

ans = max(query(1, n), ans)
for i in range(1, n-1):
    #print(i, query(0, i), query(i+1, n))
    ans = max(segfunc(query(0, i), query(i+1, n)), ans)
ans = max(query(0, n-1), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
from functools import reduce

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

def gcd_list(numbers):
    return reduce(segfunc, numbers)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


n = ii()
A = li()
gcd_a = gcd_list(A)

#####単位元######
if n == 2:
    print(max(A))
    exit()
elif n==3:
    ide_ele = max(segfunc(A[0], A[1]), segfunc(A[1], A[2]), segfunc(A[0], A[2]))
else:
    ide_ele = max(segfunc(A[0], A[1]), segfunc(A[2], A[3]))

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(A)
ans = 0

for i in range(n):
    #print(i, query(0, i), query(i+1, n))
    ans = max(segfunc(query(0, i), query(i+1, n)), ans)

print(ans)

Submission status: Wrong Answer

Solution code:

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt


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

al_fac = []
for a in al:
    fac = factorization(a)
    al_fac.append(fac)

gcd_l = [1]*n
gcd_r = [1]*n

gcd_l[0] = al_fac[0]
gcd_r[-1] = al_fac[-1]

for i in range(1,n):
    next_l = al_fac[i]
    next_l_gcd = {1:1}
    for prime,cnt in next_l.items():
        if prime in al_fac[i-1]:
            next_l_gcd[prime] = min(cnt, al_fac[i-1][prime])
    gcd_l[i] = next_l_gcd

    next_r = al_fac[n-i-1]
    next_r_gcd = {1:1}
    for prime,cnt in next_r.items():
        if prime in al_fac[n-i]:
            next_r_gcd[prime] = min(cnt, al_fac[n-i][prime])
    gcd_r[n-i-1] = next_r_gcd

ans = 1
for i in range(1,n-1):
    curr_gcd = 1
    for prime,cnt in gcd_l[i-1].items():
        if prime in gcd_r[i+1]:
            min_cnt = min(cnt, gcd_r[i+1][prime])
            curr_gcd *= prime**min_cnt
    ans = max(ans, curr_gcd)


# i = 0
curr_gcd = 1
for prime,cnt in gcd_r[1].items():
    curr_gcd *= (prime**cnt)
ans = max(ans, curr_gcd)

# i = n-1
curr_gcd = 1
for prime,cnt in gcd_l[n-2].items():
    curr_gcd *= (prime**cnt)
ans = max(ans, curr_gcd)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(sorted((map(int, readline().split()))))

MAX = 1
for a in A:
    MAX *= a

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

dp = [[0, 0] for _ in range(N + 1)]

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

print(dp[N - 1][1])