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: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in sys.stdin.readline().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N = int(input())
    A = li_input()

    ans = 0

    for i in range(N):
        A_ = A[:i] + A[i+1:]
        ans = max(ans, gcd_list(A_))

    print(ans)


main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
from math import gcd

class SegTree:
    def __init__(self, N, ele):
        self.num = 2**(N-1).bit_length()
        self.el = ele
        self.data = [ele]*(2*self.num)

    def calc(self, x, y):
        return gcd(x, y)

    def update(self, idx, x):
        idx += (self.num - 1)
        self.data[idx] = x
        while idx > 0:
            idx = (idx-1)//2
            self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2])

    def prod(self, l, r):
        L = l + self.num
        R = r + self.num
        res = self.el
        while L < R:
            if L & 1:
                res  = self.calc(res, self.data[L-1])
                L += 1
            if R & 1:
                R -= 1
                res = self.calc(res, self.data[R-1])
            L >>= 1
            R >>= 1
        return res

    def get(self, idx):
        idx += (self.num - 1)
        return self.data[idx]
    

n = int(input())
A = list(map(int, input().split()))
seg = SegTree(n, 0)
for i, a in enumerate(A):
    seg.update(i, a)

ans = 0
for i in range(n):
    g = seg.get(i)
    seg.update(i, 0)
    ans = max(ans, seg.prod(0, n))
    seg.update(i, g)
print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
if n == 1:
    print(10 ** 9)
    exit()
l = [0] * n
r = [0] * n
l[0] = a[0]
r[-1] = a[-1]
for i in range(n-1):
    l[i+1] = math.gcd(a[i+1], l[i])
    r[-i-2] = math.gcd(a[-i-2], r[-i-1])
ans = max(l[-2], r[1])
for i in range(n-2):
    ans = max(ans, math.gcd(l[i], r[i+2]))
print(ans)

Submission status: Accepted

Solution code:
class SegmentTree():
  def __init__(self, n, oper, e):
    self.n = n
    self.oper = oper
    self.e = e
    self.log = (n - 1).bit_length()
    self.size = 1 << self.log
    self.data = [e] * (2 * self.size)

  def update(self, k):
    self.data[k] = self.oper(self.data[2 * k], self.data[2 * k + 1])

  def build(self, arr):
    #assert len(arr) <= self.n
    for i in range(self.n):
      self.data[self.size + i] = arr[i]
    for i in range(self.size-1,0,-1):
      self.update(i)

  def set(self, p, x):
    #assert 0 <= p < self.n
    p += self.size
    self.data[p] = x
    for i in range(self.log):
      p >>= 1
      self.update(p)

  def get(self, p):
    #assert 0 <= p < self.n
    return self.data[p + self.size]

  def prod(self, l, r):
    #assert 0 <= l <= r <= self.n
    sml = smr = self.e
    l += self.size
    r += self.size
    while l < r:
      if l & 1:
        sml = self.oper(sml, self.data[l])
        l += 1
      if r & 1:
        r -= 1
        smr = self.oper(self.data[r], smr)
      l >>= 1
      r >>= 1
    return self.oper(sml, smr)

  def all_prod(self):
    return self.data[1]

  def max_right(self, l, f):
    #assert 0 <= l <= self.n
    #assert f(self.)
    if l == self.n: return self.n
    l += self.size
    sm = self.e
    while True:
      while l % 2 == 0: l >>= 1
      if not f(self.oper(sm, self.data[l])):
        while l < self.size:
          l = 2 * l
          if f(self.oper(sm, self.data[l])):
            sm = self.oper(sm, self.data[l])
            l += 1
        return l - self.size
      sm = self.oper(sm, self.data[l])
      l += 1
      if (l & -l) == l: break
    return self.n

  def min_left(self, r, f):
    #assert 0 <= r <= self.n
    #assert f(self.)
    if r == 0: return 0
    r += self.size
    sm = self.e
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not f(self.oper(self.data[r], sm)):
        while r < self.size:
          r = 2 * r + 1
          if f(self.oper(self.data[r], sm)):
            sm = self.oper(self.data[r], sm)
            r -= 1
        return r + 1 - self.size
      sm = self.oper(self.data[r], sm)
      if (r & -r) == r: break
    return 0

import sys
input = sys.stdin.readline

from math import gcd

e = 0

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#import
import math
#import numpy as np
N = int(input())
A = list(map(int, input().split()))

class SegTree:
    def __init__(self, segfunc, e, v, init_val = None):
        """
        segfunc: function 区間にしたい操作\n
        e: Any 単位元\n
        v: int or List 要素数か格納する配列\n
        init_val: Any 初期値
        """
        self.segfunc = segfunc
        self.e = e
        self.init_val = init_val if init_val != None else e
        if isinstance(v, int):
            v = [self.init_val] * v
        self.n = len(v)
        self.log = (self.n).bit_length()
        self.size = 1 << self.log
        self.tree = [e] * 2 * self.size
        # 1-indexedなのでtree[1:self.size]がN-1要素
        # tree[self.size:self.size + N]が配列
        for i in range(self.n):
            self.tree[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1):
            self._update(i)

    def set(self, k, x) -> None:
        """
        k番目の値をxに更新\n
        k: index(0-indexed)\n
        x: update value
        """
        k += self.size
        self.tree[k] = x
        for i in range(1, self.log + 1):
            self._update(k >> i)

    def get(self, k):
        """
        a[k]を返す\n
        k: index(0-indexed)
        """
        assert 0 <= k < self.size
        return self.tree[k + self.size]

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る\n
        l: index(0-indexed)\n
        r: index(0-indexed)
        """
        res = self.e
        l += self.size
        r += self.size
        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

    def all_query(self):
        """
        全範囲にsegfuncしたものを得る
        """
        return self.tree[1]

    # 二分探索実装、いる？

    def _update(self, k):
        self.tree[k] = self.segfunc(self.tree[k * 2], self.tree[k * 2 + 1])

seg = SegTree(math.gcd, 0, A)

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
l = [0]
r = [0]
for i in range(n-1):
    #左から見ていく
    l.append(math.gcd(l[i],a[i]))
    #右から見ていく
    r.append(math.gcd(r[i],a[-1-i]))
r = r[::-1]
ans = 0
for i in range(n):
    ans = max(ans,math.gcd(l[i],r[i]))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

class segtree:
    def __init__(self,n,op,e):
        self.e=e
        self.op=op
        self.size=1<<(n-1).bit_length()
        self.SEG=[self.e]*(self.size*2)
    
    def update(self,i,x):
        i+=self.size
        self.SEG[i]=x
        
        while i>0:
            i>>=1
            self.SEG[i]=self.op(self.SEG[i*2],self.SEG[i*2+1])
    
    def get(self,i):
        return self.SEG[i+self.size]
    
    def query(self,l,r):
        l+=self.size
        r+=self.size
        
        lres,rres=self.e,self.e
        
        while l<r:
            if l&1:
                lres=self.op(lres,self.SEG[l])
                l+=1
            
            if r&1:
                r-=1
                rres=self.op(rres,self.SEG[r])
            
            l>>=1
            r>>=1
            
        res=self.op(lres,rres)
        return res
 

N=int(input())
seg=segtree(N,gcd,0)
A=list(map(int,input().split()))
for i in range(N):
    seg.update(i,A[i])
ans=1
for i in range(N):
    l,r=seg.query(0,i),seg.query(i+1,N)
    ans=max(ans,gcd(l,r))
print(ans)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

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

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i, a[i])

ans = 1
for i in range(n):
    left = s.query(0, i)
    right = s.query(i+1, n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

Submission status: Accepted

Solution code:
from math import gcd as g
#####segfunc#####
def segfunc(x, y):
    return g(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)
ans=1
for i in range(n):
    p=seg.query(0,i)
    q=seg.query(i+1,n)
    ans=max(ans,g(p,q))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

class SegmentTree:
    """Segment Tree

    Attributes:
        n (int):       要素数以上の最小の2の累乗
        ide_ele (int): 単位元
            - RmQ (Range Minimum Query): inf
            - RMQ (Range Maximum Query): -1
            - RSQ (Range Sum Query):     0
            - RPQ (Range Product Query): 1
            - RGQ (Range GCD Query):     0
        seg (list):    要素の格納先
    """
    def __init__(self, a):
        """初期化 O(N)
        
        Args:
            a (list): 対象の配列
        """
        self.n = 2 ** (len(a) - 1).bit_length()
        self.ide_ele = 0
        self.seg = [self.ide_ele] * (2*self.n)

        for i, v in enumerate(a, self.n):
            self.seg[i] = v
        for i in range(self.n-1, 0, -1):
            self.seg[i] = self.st_func(self.seg[2*i], self.seg[2*i+1])

    def query(self, l, r):
        """区間クエリの計算 O(logN)

        Args:
            l (int): 区間の左端
            r (int): 区間の右端
        
        Returns:
            int: [l, r)についての区間クエリ
        """
        l += self.n
        r += self.n
        res_l = self.ide_ele
        res_r = self.ide_ele

        while l < r:
            if l % 2 == 1:
                res_l = self.st_func(res_l, self.seg[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res_r = self.st_func(self.seg[r], res_r)
            l //= 2
            r //= 2

        return self.st_func(res_l, res_r)

    def update(self, i, v):
        """値の更新 O(logN)

        Args:
            i (int): 更新対象のindex
            v (int): 更新値
        """
        i += self.n
        self.seg[i] = v
        while i > 1:
            i //= 2
            self.seg[i] = self.st_func(self.seg[i*2], self.seg[i*2+1])
    
    def st_func(self, x, y):
        """問題に応じた処理

        Returns:
            int: 問題に応じた値
                - RmQ(Range Minimum Query): min(x, y)
                - RMQ(Range Maximum Query): max(x, y)
                - RSQ(Range Sum Query):     x + y
                - RPQ(Range Product Query): x * y
                - RGQ(Range GCD Query):     gcd(x, y)
        """
        return gcd(x, y)
 
n = int(input())
a = list(map(int, input().split()))

st = SegmentTree(a)

res = 0
for i in range(n):
	res = max(res, gcd(st.query(0, i), st.query(i+1, n)))

print(res)

Submission status: Accepted

Solution code:
n = int(input())
raw = list(map(int,input().split()))
nn = 1
scale = 1
while True:
  if n <= nn:
    raw += [0] * (nn-n)
    break
  else:
    nn *= 2
    scale += 1
#print(raw,scale)
n = len(raw)

def gcd(aa,bb):
  if aa == 0:
    return bb
  elif bb == 0:
    return aa
  else:
    big,sml = aa,bb
    while sml:
      big,sml = sml,big%sml
    return big
seg = [0] * n + raw
for i in range(1,n)[::-1]:
  seg[i] = gcd(seg[2*i],seg[2*i+1])
#print(seg)
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
#print(rdb)
can = []
for j in range(n):
  now = [[0,j],[j+1,db[-1]]]
  #print(now)
  g = 0
  for i in range(scale):
    last = now
    now = []
    for lr in last:
      l,r = lr
      if l == r:
        continue
      L = (l-1) // rdb[i] + 1
      R =   r   // rdb[i]
      if L < R:
        for U in range(L,R):
          g = gcd(g,seg[db[i]+U])
        now.append([l,rdb[i]*L])
        now.append([rdb[i]*R,r])
      else:
        now.append(lr)
      #print(now)
  can.append(g)
print(max(can))
#print(seg)

Submission status: Accepted

Solution code:
from math import gcd


class SegmentTree:
    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)

    def __getitem__(self, key):
        return self._data[self._offset + key]

    def __setitem__(self, key, value):
        op = self._op
        data = self._data
        i = self._offset + key
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(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
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result


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

st = SegmentTree(N, gcd, 0)
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:
import math
import sys
sys.setrecursionlimit(10**6)
class SegmentTree:
    """
    単位元のメモ書き（各演算に対する単位元の対応）
    f(x,y) := x+y -> 0
    f(x,y) := x-y -> 0
    f(x,y) := x*y -> 1
    f(x,y) := gcd(x, y) -> 0
    """

    def __init__(self, size, func=lambda x,y:x+y, default=0):
        """
        size : 配列のサイズ
        func : queryの内容(e.g. 区間和ならf(x, y)=x+y)
        default : 単位元
        """
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default for _ in range(self.size*2-1)]
        self.f = func

    def update(self, i, x):
        """
        i番目の値をxに変更する。0-indexedなので注意
        """
        i = i + self.size - 1 #一番下の層の値
        self.dat[i] = x

        while i > 0:
            i = (i-1)>>1
            self.dat[i] = self.f(self.dat[i*2+1], self.dat[i*2+2])

    def query(self, a, b, k=0, L=0, R=None):
        """
        区間[a, b]に関するクエリを処理します。
        例えばi=1,2,3に関して処理したいなら外からquery(1, 3+1)と呼ぶ必要があります。
        """
        if R is None:
            R = self.size

        #区間がかぶっていない場合
        if R <= a or b <= L:
            return self.default

        #区間が完全に収まっている場合
        if a <= L and R <= b:
            return self.dat[k]

        else:
            lres = self.query(a, b, 2*k+1, L, (L+R)>>1)
            rres = self.query(a, b, 2*k+2, (L+R)>>1, R)
            return self.f(lres, rres)


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

segTree = SegmentTree(N, func=lambda x,y:math.gcd(x,y), default=0)
for i in range(N):
    segTree.update(i, A[i])

ans = -1
for i in range(N):
    a = segTree.query(0, i)
    b = segTree.query(i+1, N)
    ans = max(ans, math.gcd(a,b))

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

#####segfunc#####
def segfunc(x, y):
    # return min(x, y) #最小値
    # return max(x, y) #最大値
    # return x + y #区間和
    # return x * y #区間積
    return gcd(x, y) # 最大公約数

#################
INF = float("inf")
#####ide_ele 単位元#####
# ide_ele = INF
# ide_ele = -INF
# ide_ele = 0
# ide_ele = 1
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()))
ans = 1
seg_tree = SegTree(A, segfunc, ide_ele)
for i in range(N):
    ans = max(ans, gcd(seg_tree.query(0, i), seg_tree.query(i+1, N)))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N = NI()
    A = NLI()
    
    L = [0 for _ in range(N)]
    L_gcd = 0
    for n in range(0,N-1):
        L_gcd = math.gcd(A[n],L_gcd)
        L[n+1] = L_gcd

    

    R = [0 for _ in range(N)]
    R_gcd = 0
    for n in range(N-1,-1,-1):
        R_gcd = math.gcd(A[n],R_gcd)
        R[n-1] = R_gcd
    R[-1] = 0

    
    ans = 0
    for n in range(N):
        ans = max(ans,math.gcd(L[n],R[n]))
    print(ans)
    


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

    n = int(input())
    a = [int(x) for x in input().split()]
    x = [0] * n
    y = [0] * n
    # x []   [0~1][0~2][0~3]...[0~n-1][0~n]
    # y [0~n][1~n][2~n][3~n]...[n]    []
    # yのrangeのとり方を工夫する
    for i in range(1,n):
        x[i] = gcd(x[i-1], a[i-1])
    for i in range(n-2, -1, -1):
        y[i] = gcd(y[i+1], a[i+1])
    ans = [gcd(x[i], y[i]) for i in range(n)]
    print(max(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    left = [0] * (N + 1)
    right = [0] * (N + 1)

    # 予めGCDを計算する
    for i in range(N):
        # 左から累積したGCD
        left[i+1] = math.gcd(left[i], A[i])
    for i in reversed(range(N)):
        # 右から累積したGCD
        right[i] = math.gcd(right[i+1], A[i])

    ret = 0
    for i in range(N):
        ret = max(ret, math.gcd(left[i], right[i+1]))
    print(ret)

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    left = [0] * (N + 1)
    right = [0] * (N + 1)

    # 予めGCDを計算する
    for i in range(N):
        left[i+1] = math.gcd(left[i], A[i])
    for i in reversed(range(N)):
        right[i] = math.gcd(right[i+1], A[i])

    ret = 0
    for i in range(N):
        ret = max(ret, math.gcd(left[i], right[i+1]))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())



def run():
    N, *A = mapread()
    LEFT = [0] * (N+2)
    RIGHT = [0] * (N+2)
    for i, a in enumerate(A, 1):
        LEFT[i] = math.gcd(LEFT[i-1], a)
    for i in range(N-1, -1, -1):
        k = i+1# for RIGHT
        RIGHT[k] = math.gcd(RIGHT[k+1], A[i])
    #print(LEFT)
    #print(RIGHT)
    ans = 0
    for i in range(N):
        k = i + 1# for LEFT and RIGHT
        v = math.gcd(LEFT[k-1], RIGHT[k+1])
        #print(v)
        ans = max(ans, v)

    print(ans)



if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()