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 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()))
    res = 0

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

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#create date: 2020-06-29 23:17

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("out.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)
t=1
# t=int(input())
for _ in range(t):
    n=l()[0]
    A=l()
    L=[A[0] for i in range(n)]
    R=[A[-1] for i in range(n)]
    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])
    mx=0
    # print(*L)
    # print(*R)
    for i in range(n):
        if i==0:
            mx=max(mx,R[i+1])
        elif i==n-1:
            mx=max(mx,L[i-1])
        else:
            g=gcd(L[i-1],R[i+1])
            mx=max(mx,g)
    print(mx)

Submission status: Accepted

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[n-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: Accepted

Solution code:
# Segment tree (GCD)
from math import 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):
        f = self._f
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = f(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


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: Accepted

Solution code:
# Disjoint sparse table (GCD)
from math import gcd


class DisjointSparseTable:
    _f = None
    _data = None
    _lookup = None

    def __init__(self, a, f):
        self._f = f
        b = 0
        while (1 << b) <= len(a):
            b += 1
        _data = [[0] * len(a) for _ in range(b)]
        _data[0] = a[:]
        for i in range(1, b):
            shift = 1 << i
            for j in range(0, len(a), shift << 1):
                t = min(j + shift, len(a))
                _data[i][t - 1] = a[t - 1]
                for k in range(t - 2, j - 1, -1):
                    _data[i][k] = f(a[k], _data[i][k + 1])
                if t >= len(a):
                    break
                _data[i][t] = a[t]
                r = min(t + shift, len(a))
                for k in range(t + 1, r):
                    _data[i][k] = f(_data[i][k - 1], a[k])
        self._data = _data
        _lookup = [0] * (1 << b)
        for i in range(2, len(_lookup)):
            _lookup[i] = _lookup[i >> 1] + 1
        self._lookup = _lookup

    def query(self, start, stop):
        stop -= 1
        if start >= stop:
            return self._data[0][start]
        p = self._lookup[start ^ stop]
        return self._f(self._data[p][start], self._data[p][stop])



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

st = DisjointSparseTable(A, gcd)

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: Accepted

Solution code:
import math

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

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

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

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

Submission status: Accepted

Solution code:
# Sparse table (GCD)
from math import gcd


class SparseTable():
    _data = None
    _lookup = None
    _f = None

    def __init__(self, a):
        data = []
        lookup = []
        f = gcd
        b = 0
        while (1 << b) <= len(a):
            b += 1
        for _ in range(b):
            data.append([0] * (1 << b))
        data[0][:len(a)] = a
        for i in range(1, b):
            j = 0
            di = data[i]
            di1 = data[i - 1]
            while j + (1 << i) <= (1 << b):
                di[j] = f(di1[j], di1[j + (1 << (i - 1))])
                j += 1
        lookup = [0] * (len(a) + 1)
        for i in range(2, len(lookup)):
            lookup[i] = lookup[i >> 1] + 1
        self._data = data
        self._lookup = lookup
        self._f = f

    def query(self, start, stop):
        b = self._lookup[stop - start]
        db = self._data[b]
        return self._f(db[start], db[stop - (1 << b)])


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

st = SparseTable(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: Accepted

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, 0, -1):
    R[i-1] = gcd(R[i], A[i])

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

print(ans)

Submission status: Accepted

Solution code:
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])
    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: Accepted

Solution code:
from math import gcd

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

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

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

Submission status: Accepted

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-2])
ans = max(ans,R[0])
print(ans)

Submission status: Accepted

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

ans=max(ctmp,dtmp)

for i in range(n-1,-1,-1):
    if i==n-1:
        tmp=b[i]
    else:
        tmp=gcd(tmp, b[i])
        if tmp==1:
            l=i
            r=i+1
            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(ans,ctmp,dtmp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

L = [A[0]]
R = [A[-1]]

ans = 0

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

R.reverse()

for i in range(N):
  if i == 0:
    ans = max(ans, R[i+1])
  elif i == N-1:
    ans = max(ans, L[i-1])
  else:
    ans = max(ans, math.gcd(L[i-1], R[i+1]))

print(ans)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

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 = 0
for i in range(N):
  if i == 0:
    if ans < right[1]:
      ans = right[1]
  elif i == N - 1:
    if ans < left[-2]:
      ans = left[-2]
  else:
    g = math.gcd(left[i - 1],right[i + 1])
    if ans < g:
      ans = g
print(ans)

Submission status: Accepted

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

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


accl = [0]*(n+1)
accr = [0]*(n+1)

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

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

res = 0
for i in range(n):
    if i==0:
        res = max(res, accr[1])
    elif i==n-1:
        res = max(res, accl[n-1])
    else:
        res = max(res, gcd(accl[i], accr[i+1]))
print(res)

Submission status: Accepted

Solution code:
from math import gcd

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

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

ans = -1
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:
from math import gcd
n=int(input())
A=list(map(int,input().split()))
left,right=[0]*n,[0]*n

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import math

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

fo = [a[0]]
re = [a[-1]]

x,y = a[0] , a[-1]
for i in range(n-1):
    x = math.gcd(x,a[i+1])
    y = math.gcd(y,a[n-2-i])
    fo.append(x)
    re.append(y)
    
ans = re[n-2]
for i in range(1,n-1):
    ans = max(ans , math.gcd(fo[i-1],re[n-2-i]))
ans = max(ans , fo[n-2])

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

#####segfunc#####
def segfunc(x, y):
    return gcd(x,y)
#################

#####ide_ele#####
ide_ele = 0#gcd(8,0)=8　だからね
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    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, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

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

seg = SegTree(A,segfunc,ide_ele)

ans = 1
for i in range(0,N+1,1):
    ans = max(ans,gcd(seg.query(0,i),seg.query(i+1,N)))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
N = int(input())
A = list(map(int, input().split()))
L = [0]*(N+2)
R = [0]*(N+2)

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

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

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

Submission status: Accepted

Solution code:
from math import gcd

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

L = [0] * N
L[0] = A[0]

#配列の左から順番に最大公約数を求める
for i, a in enumerate(A):
    L[i] = gcd(L[max(0, i-1)], a)

# print("L", L)
R = [0] * N
R[0] = A[-1]

#配列の右から順番に最大公約数を求める
for i, a in enumerate(A[::-1]):
    R[i] = gcd(R[max(0, i-1)], a)

# print("R", R)
ans = 0

for i in range(N):
    #一番左の数字を削除
    if i == 0:
        ans = max(ans, R[N-2])
    #一番右の数字を削除
    elif i == N-1:
        ans = max(ans, L[N-2])
    #i+1番目の数字を削除
    else:
        ans = max(ans, gcd(L[i-1], R[N-i-2]))
    
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

L = [0] * n
L[0] = A[0]
for i, a in enumerate(A):
  L[i] = gcd(L[max(0, i - 1)], a)
  
R = [0] * n 
R[0] = A[-1]
for i, a in enumerate(A[::-1]):
  R[i] = gcd(R[max(0, i - 1)], a)

ans = 0
for i in range(n):
  if i == 0:
    ans = max(ans, R[n - 2])
  elif i == n - 1:
    ans = max(ans, L[n - 2])
  else:
    ans = max(ans, gcd(L[i - 1], R[n - i - 2]))
    
print(ans)

Submission status: Accepted

Solution code:
from math 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 range(N, 0, -1):
    R[i - 1] = gcd(R[i], A[i - 1])

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

print(ans)

Submission status: Accepted

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)])
A.pop(-1)
B.pop(-1)
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: Accepted

Solution code:
from math import gcd

n = int(input())
alst = list(map(int, input().split()))
l_gcd = []
r_gcd = []

tmp = alst[0]
for num in alst[:-1]:
    tmp = gcd(tmp, num)
    l_gcd.append(tmp)
    
tmp = alst[-1]
for num in alst[1:][::-1]:
    tmp = gcd(tmp, num)
    r_gcd.append(tmp)
    
ans = max(r_gcd[-1], l_gcd[-1])
for r, l in zip(r_gcd[:-1], l_gcd[:-1][::-1]):
    tmp = gcd(r, l)
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from math import gcd as gcd
import numpy as np
N = int(input())
A = list(map(int,input().split()))

A = [0] + A + [0]

fromleft = np.array([0]*N)
fromright = np.array([0]*N)

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

#print(fromleft)
#print(fromright)

ansgcd = [0]*N

for i in range(N):
    ansgcd[i] = gcd(fromright[i], fromleft[i])

print(max(ansgcd))

Submission status: Accepted

Solution code:
from math 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:
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): 
	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: Accepted

Solution code:
from collections import defaultdict

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    divisors.sort()
    return divisors

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

div1 = set(make_divisors(a[0]))
div2 = set(make_divisors(a[1]))
common = div1 | div2

cnt = defaultdict(int)
for i in range(n):
    for j in common:
        if a[i] % j == 0:
            cnt[j] += 1

for k, v in sorted(cnt.items(), reverse=True):
    if v == n or v == n-1:
        print(k)
        exit()

Submission status: Accepted

Solution code:

N = int(input())
A = list(map(int, input().split()))
        
    
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b != 0:
        s = a % b
        a = b
        b = s
    return a

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

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

MAX = max(B[-2], F[-2])
for i in range(N-2):
    #print(B[-(3+i)], F[i])
    #print(gcd(B[-(3+i)], F[i]))
    MAX = max(MAX, gcd(B[-(3+i)], F[i]))
    
print(MAX)

Submission status: Accepted

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


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

gcd_from_left = [0]*n
gcd_from_right = [0]*n

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

ans = 0

for a, b in zip(gcd_from_left, gcd_from_right):
    x = gcd(a, b)
    if ans < x:
        ans = x

print(ans)

Submission status: Accepted

Solution code:
#from fractions import gcd
"""
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
"""
def gcd(a,b):
    if b==0:
        return a
    r=a%b
    while r!=0:
        a=b
        b=r
        r=a%b
    return b
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)#basementで初期化
 
        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]
 
        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])
 
    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])
 
    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res
 

n=int(input())
a=list(map(int,input().split()))
seg=SegTree(a,gcd,0)
ans=1
for i in range(n):
    ans=max(ans,gcd(seg.query(0,i),seg.query(i+1,n)))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
"""
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
"""
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)#basementで初期化
 
        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]
 
        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])
 
    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])
 
    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res
 

n=int(input())
a=list(map(int,input().split()))
seg=SegTree(a,gcd,0)
ans=1
for i in range(n):
    ans=max(ans,gcd(seg.query(0,i),seg.query(i+1,n)))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


class SegTree():
    # ここでは操作の都合上根元のindexを1とする
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*2**(self.K+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


# gcd on blackboard
# セグ木（区間gcd) verify
N = int(input())
A = list(map(int, input().split()))
seg = SegTree(A, gcd, 0)
ans = 1
for i in range(-1, N):
    v = gcd(seg.query(0, i), seg.query(i+1, N))
    ans = max(v, ans)
print(ans)

Submission status: Accepted

Solution code:
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*2**(self.K+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X-1] = v

        for i in range(2*X-2, 0, -2):
            self.seg[(i-1) >> 1] = self.f(self.seg[i], self.seg[i-1])

    def update(self, k, value):
        X = 2**self.K
        k += X-1
        self.seg[k] = value
        while k:
            k = (k-1) >> 1
            self.seg[k] = self.f(self.seg[(k << 1)+1], self.seg[(k << 1)+2])

    def query(self, L, R):
        num = 2**self.K-1
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1 == 0:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1 == 0:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


#gcd on blackboard
#セグ木（区間gcd) verify
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
seg=SegTree(A,gcd,0)
ans=1
for i in range(-1,N):
    v=gcd(seg.query(0,i),seg.query(i+1,N))
    ans=max(v,ans)
print(ans)