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:
from typing import Callable, List, Union

T = Union[int, str]


class SegmentTree:
    """Segment Tree"""

    __slots__ = ["e", "op", "_n", "_size", "tree"]

    def __init__(self, a: List[T], e: T, op: Callable[[T, T], T]) -> None:
        self.e = e
        self.op = op
        self._n = len(a)
        self._size = 1 << (self._n - 1).bit_length()

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: T) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> T:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> T:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self.e, self.e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> T:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[T], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[T], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self.e)

        if not r:
            return 0

        r += self._size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1

            if not f(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0


def practice2_j():
    # https://atcoder.jp/contests/practice2/tasks/practice2_j
    N, _, *AQ = map(int, open(0).read().split())
    A, Q = AQ[:N], AQ[N:]
    tree = SegmentTree(A, -1, max)
    res = []
    for t, x, y in zip(*[iter(Q)] * 3):
        if t == 1:
            tree.set(x - 1, y)
        elif t == 2:
            res.append(tree.prod(x - 1, y))
        else:
            res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
    print("\n".join(map(str, res)))


def staticrmq():
    # https://judge.yosupo.jp/problem/staticrmq
    N, Q, *ALR = map(int, open(0).read().split())
    A, LR = ALR[:N], ALR[N:]
    tree = SegmentTree(A, (10 ** 10) + 1, min)
    res = [tree.prod(l, r) for l, r in zip(*[iter(LR)] * 2)]
    print("\n".join(map(str, res)))


def dsl_2_a():
    # https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A
    N, Q, *X = map(int, open(0).read().split())
    tree = SegmentTree([2 ** 31 - 1] * N, 2 ** 31 - 1, min)
    res = []
    for com, x, y in zip(*[iter(X)] * 3):
        if com:
            res.append(tree.prod(x, y + 1))
        else:
            tree.set(x, y)
    print("\n".join(map(str, res)))


def abc125_c():
    # https://atcoder.jp/contests/abc125/tasks/abc125_c
    from math import gcd

    N, *A = map(int, open(0).read().split())
    tree = SegmentTree(A, 0, gcd)
    res = max(gcd(tree.prod(0, i), tree.prod(i + 1, N)) for i in range(N))
    print(res)


if __name__ == "__main__":
    # practice2_j()
    # staticrmq()
    # dsl_2_a()
    abc125_c()

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    a = i_list()

    left = [0]
    right = [0]

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

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



if __name__=="__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from math import gcd
from itertools import accumulate

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

l = list(accumulate(a, lambda x, y: gcd(x, y)))
r = list(accumulate(a[::-1], lambda x, y: gcd(x, y)))[::-1]
ans = max(r[1], l[-2])
for i in range(1, n-1):
    ans = max(ans, gcd(l[i-1], r[i+1]))
print(ans)

Submission status: Accepted

Solution code:
"""
問題文を言い換えると、「最大公約数が最大になるように数字を一つ書き換えろ」ということ。
さらに言い換えると、「最大公約数が最大になるように数字を一つ消せ」ということ。
単純な線形探索でできるか？→NO

最大公約数を小さくする要因となっている数字を一つ消す。
どういう数字が最大公約数を小さくする要因になっているか？
他の数字と共通する素因数が少ない、小さい、次数が小さい。ただ、この3つを総合的に判断するのは難しすぎる。
素因数分解はやめて、単純に約数で探せばよいか。
各Aの約数を昇順で列挙しておく。
まずA1は必ず残すと仮定して、A1の約数の大きい方から順番に、ほかのAの約数になるかどうかを調べる。
その約数を含んでいないAが一つだけ存在するとき、そのAを消せば、その約数が最大公約数となる。

次に、A1を消す場合の最大公約数も求めて、A1を含める場合の最大公約数と比較して大きい方を採用する。
"""

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

#A1を必ず入れる場合の最大公約数を求める。
yakusu = []

a = A[0]
d = 1
while d*d < a:
    if a % d == 0:
        yakusu.append(d)
        yakusu.append(a//d)
    d += 1
if d*d == a:
    yakusu.append(d)
yakusu.sort(reverse=True)

ans = 1
for v in yakusu:
    cnt = 0
    for i in range(1,N):
        if A[i]%v != 0:
            cnt += 1
    if cnt <= 1:
        ans = v
        break

#A1を入れない場合の最大公約数を求める。
import math
g = A[1]
for i in range(2,N):
    g = math.gcd(g,A[i])

ans = max(ans,g)

print(ans)

Submission status: Accepted

Solution code:
from math import gcd


N, *A = map(int, open(0).read().split())
acc_l = [0]
acc_r = [0]
for i in range(N):
    acc_l.append(gcd(acc_l[-1], A[i]))
    acc_r.append(gcd(acc_r[-1], A[N - i - 1]))

ans = 0
for i in range(N):
    ans = max(ans, gcd(acc_l[i], acc_r[N - i - 1]))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(N)]
C = [0 for i in range(N)]
B[0] = A[0]
C[0] = A[N - 1]
for i in range(1, N):
    B[i] = gcd(B[i - 1], A[i])
    C[i] = gcd(C[i - 1], A[N - i - 1])


ans = 0
for i in range(N):
    if i != 0 and i != N - 1:
        ans = max(ans, gcd(B[i - 1], C[N - i - 2]))
    elif i == 0:
        ans = max(ans, C[N - 2])
    else:
        ans = max(ans, B[N - 2])

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

n, *a = map(int, open(0).read().split())

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])
print(max(gcd(l[i], r[i]) for i in range(n)))

Submission status: Accepted

Solution code:
# 0-indexed
from math import gcd
INF = 10**9+1
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


def gcd2(a,b):
    if a >= INF: return b
    elif b >= INF: return a
    else: return gcd(a,b)



n = int(input())
al = list(map(int, input().split()))
st = SegTree(al,gcd2,INF)
ans = 0
for i in range(n):
    if i != 0:
        st.update(i-1,al[i-1])
    st.update(i,INF)
    v = st.query(0,n)
    ans = max(ans,v)


print(ans)

Submission status: Accepted

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 2:
        print(max(A))
        exit()
    l_gcd = [A[0]]
    for a in A[1:N-1]:
        l_gcd.append(math.gcd(l_gcd[-1], a))
    r_gcd = [A[-1]]
    for a in list(reversed(A))[1:N-1]:
        r_gcd.append(math.gcd(r_gcd[-1], a))

    ans = 1
    for i in range(N):
        if i == 0:
            v = r_gcd[-1]
        elif i == N-1:
            v = l_gcd[-1]
        else:
            v = math.gcd(l_gcd[i-1], r_gcd[N-i-2])
        if v > ans:
            ans = v
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

pref = [0]; suff = [0]

for i in range(n):
    pref.append(gcd(pref[-1], a[i]))

for i in range(n-1, -1, -1):
    suff.append(gcd(suff[-1], a[i]))

suff.reverse()

ans = pref[-1]

for i in range(len(pref)-1):
    ans = max(ans, gcd(pref[i], suff[i+1]))

print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from math import gcd
N = int(input())
A = [0]+list(map(int, input().split()))+[0]
L = [0]*(N+1)
R = [0]*(N+1)
for i in range(1, N+1):
    L[i] = gcd(L[i-1], A[i])
    R[N-i] = gcd(R[N+1-i], A[N+1-i])
# print(L)
# print(R)

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

Submission status: Accepted

Solution code:
# practice for SegTree
from math import gcd

INF = 10**10
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)

def gcd2(a,b):
    if a == INF:
        return b
    elif b == INF:
        return a
    else:
        return gcd(a,b)


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

st = SegTree(al,gcd2,INF)
# print(st.tree)
ans = 0
for i in range(n):
    if i > 0: st.update(i-1,al[i-1])
    st.update(i,INF)
    c_gcd = st.query(0,n)
    # print(c_gcd,'-')
    ans = max(ans,c_gcd)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import gcd

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

l = list(accumulate(A[:-1], gcd, initial=0))
r = list(accumulate(A[::-1], gcd, initial=0))
print(max(gcd(l[i], r[N-i-1]) for i in range(N)))

Submission status: Accepted

Solution code:
from math import gcd


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

#####ide_ele#####
ide_ele = 0
#################

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)

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

print(mx)

Submission status: Accepted

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

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

gcd_from_left = [0]*N # 自分のindexは含まないようなもの
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-1-i] = 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:
#/usr/bin/env python
from functools import *
from math import *

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

gcds = []
lgcd = []
rgcd = [0 for _ in range(n)]
l = r = 0 
for i in range(n):
    if i == 0:
        l = 0 
    else:
        l = gcd(l, a[i-1])
    lgcd.append(l)

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

for i in range(n):
    g = gcd(lgcd[i], rgcd[i])
    gcds.append(g)

print(max(gcds))

Submission status: Accepted

Solution code:
from math import gcd

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

A = [0] + A + [0]

#Left side
L = [A[1]]
tempL = A[1]
for i in range(1, N):
    tempL = gcd(tempL, A[i+1])
    L.append(tempL)
L = [0] + L
    
#Right side
R = [A[-2]]
tempR = A[-2]
for i in range(1, N):
    tempR = gcd(tempR, A[-i-2])
    R.append(tempR)
R = list(reversed(R)) + [0]

ans = []
for i in range(N):
    result = gcd(L[i], R[i+1])
    ans.append(result)

print(max(ans))

Submission status: Accepted

Solution code:
from math import gcd

class SegTree():
    def segfunc(self, x, y):
        return gcd(x, y)

    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segfunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segfunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segfunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segfunc(res, self.seg[begin])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[begin]), self.seg[end])
        return res

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
A = rl()

class SegTree:
	def __init__(self, n, f=min, v=float('inf')):
		self.n = n
		self.f = f
		self.v = v
		self.nums = [v] * (2*n)
		
	def init(self, seq):
		n, f, nums = self.n, self.f, self.nums
		assert len(seq) == n, 'seq size error'
		for i, x in enumerate(seq):
			nums[i+n] = x
		for i in range(n-1, 0, -1):
			nums[i] = f(nums[i<<1], nums[i<<1|1])

	def update(self, i, x):
		n, f, nums = self.n, self.f, self.nums
		i += n
		nums[i] = x
		while i > 1:
			i >>= 1
			nums[i] = f(nums[i<<1], nums[i<<1|1]) # f(nums[i//2], nums[i//2+1])
	
	def query(self, l, r): # f([l, r))
		n, f, v, nums = self.n, self.f, self.v, self.nums
		l, r = l+n, r+n
		vl, vr = v, v
		while l < r:
			if l & 1:
				vl = f(vl, nums[l])
				l += 1
			if r & 1:
				r -= 1
				vr = f(nums[r], vr)
			l, r = l>>1, r>>1
		return f(vl, vr)

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

st = SegTree(N, f=gcd, v=0)
st.init(A)

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

Submission status: Accepted

Solution code:
from math import gcd
class SegmentTree:
    def __init__(self,n,ele=0):

        self.ide_ele = ele

        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num


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

    def init(self,init_val):
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
n=int(input())
a=list(map(int,input().split()))
st=SegmentTree(n)
st.init(a)
ans=-1
for i in range(n):
    ans=max(ans,gcd(st.query(0,i),st.query(i+1,n)))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

N=int(input())
A = [0] + list(map(int, input().split()))
L = [0]*(N+2)
R = [0]*(N+2)
ans = 0
L[0] = 0
R[N+1] = 0
for i in range(1, N+1):
    L[i+1] = gcd(L[i], A[i])
for i in range(N, 0, -1):
    R[i] = gcd(R[i+1], A[i])
for i in range(N+1):
    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()))

lefGcd = [0]*100100
rigGcd = [0]*100100

lefGcd[0] = a[0]
rigGcd[n-1] = a[n-1]

#左側からGCDを計算した値を保持する。
for i in range(1,n):
	lefGcd[i] = math.gcd(lefGcd[i-1],a[i])

#右側からGCDを計算した値を保持する。
for i in reversed(range(0,n-1)):
	rigGcd[i] = math.gcd(rigGcd[i+1],a[i])

#一番左か一番右の値を除去したGCDの値を初期値にする。
ans = max(rigGcd[1],lefGcd[n-2])

#左からのGCD,1個飛ばし,右からのGCDを計算し、比較する。
for i in range(1,n-1):
	ans = max(ans,math.gcd(lefGcd[i-1],rigGcd[i+1]))

print(ans)

Submission status: Accepted

Solution code:
import math

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

lefGcd = [0]*100100
rigGcd = [0]*100100

lefGcd[0] = a[0]
rigGcd[n-1] = a[n-1]

for i in range(1,n):
	lefGcd[i] = math.gcd(lefGcd[i-1],a[i])

for i in reversed(range(0,n-1)):
	rigGcd[i] = math.gcd(rigGcd[i+1],a[i])

ans = max(rigGcd[1],lefGcd[n-2])

for i in range(1,n-1):
	ans = max(ans,math.gcd(lefGcd[i-1],rigGcd[i+1]))

print(ans)

Submission status: Accepted

Solution code:
class PSTNode():
    def __init__(self, val=None):
        self.val = val
        self.key = 0
        self.dep = None
        self.lt = None
        self.rt = None
        self.par = None

class PersistentSegmentTree():
    def __init__(self, q, array, func=min, ie=2**63-1):
        self.q = q
        self.h = (len(array) - 1).bit_length()
        self.n = 2**self.h
        array += [ie] * (self.n - len(array))
        self.roots = [None for _ in range(q + 2)]
        self.roots[-1] = root = PSTNode()
        root.dep = 0
        self.idx = -1
        self.func = func
        self.ie = ie
        stack = [root]
        order = [root]
        while stack:
            node = stack.pop()
            node.lt = PSTNode()
            node.rt = PSTNode()
            node.lt.par = node
            node.rt.par = node
            ndep = node.dep + 1
            node.lt.dep = ndep
            node.rt.dep = ndep
            node.lt.key = node.key
            node.rt.key = node.key + 2**(self.h - ndep)
            if ndep == self.h:
                node.lt.val = array[node.lt.key]
                node.rt.val = array[node.rt.key]
            else:
                stack.append(node.lt)
                stack.append(node.rt)
                order.append(node.lt)
                order.append(node.rt)
        for node in order[::-1]:
            node.val = self.func(node.lt.val, node.rt.val)

    def get_node(self, idx, t=-1):
        node = self.roots[t]
        k = self.h - 1
        while k != -1:
            if (idx >> k) & 1:
                node = node.rt
            else:
                node = node.lt
            k -= 1
        return node

    def get_val(self, idx, t=-1):
        return self.get_node(idx, t).val

    def set_val(self, idx, x, t=-1):
        old_node = self.get_node(idx, t)
        new_node = PSTNode(x)
        new_node.key = old_node.key
        for i in range(self.h):
            new_par = PSTNode()
            old_par = old_node.par
            new_par.key = old_par.key
            new_node.par = new_par
            if old_par.lt == old_node:
                new_par.lt = new_node
                new_par.rt = old_par.rt
                old_par.rt.par = new_par
            else:
                new_par.lt = old_par.lt
                new_par.rt = new_node
                old_par.lt.par = new_par
            new_par.val = self.func(new_par.lt.val, new_par.rt.val)
            old_node = old_par
            new_node = new_par
        self.roots[self.idx] = new_node

    def get_range(self, lt, rt, t=-1):
        node = self.roots[t]
        res = self.ie
        stack = [node]
        while stack:
            node = stack.pop()
            if lt <= node.key and node.key + 2**(self.h - node.dep) <= rt:
                res = self.func(res, node.val)
            elif node.key + 2**(self.h - node.dep) <= lt or rt <= node.key:
                continue
            else:
                stack.append(node.lt)
                stack.append(node.rt)
        return res

    def update(self):
        self.idx += 1
        self.roots[self.idx] = self.roots[self.idx - 1]

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

pst = PersistentSegmentTree(0, A, gcd, 0)
res = 1

for i in range(N):
    res = max(res, gcd(pst.get_range(0, i), pst.get_range(i + 1, N)))

print(res)