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:
def gcd(n,m):return gcd(m,n%m) if m and n else n+m
n=int(input())
h=list(map(int,input().split()))
l=[0]*n
r=[0]*n
a,s=0,0
for i in range(n):
  l[i]=a
  a=gcd(a,h[i])
  r[-i-1]=s
  s=gcd(s,h[-i-1])
ans=1
for i in range(n):
  ans=max(ans,gcd(l[i],r[i]))
print(ans)

Submission status: Accepted

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

import fractions as math

l=[0]
r=[0]
for i in range(n-1):
  li=math.gcd(l[i],a[i])
  l.append(li)
  ri=math.gcd(r[i],a[n-i-1])
  r.append(ri)
m=[]
for i in range(n):
  mi=math.gcd(l[i],r[n-i-1])
  m.append(mi)

print(max(m))

Submission status: Accepted

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

import fractions
rui_l=[0]*n
rui_r=[0]*n

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

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

ans=[]
ans.append(rui_r[1])
for i in range(1,n-1):
    ans.append(fractions.gcd(rui_l[i-1],rui_r[i+1]))
ans.append(rui_l[-2])

print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
As = list(map(int, input().split()))
re_As = As[::-1]
gcds = [0]*(N)
rgcds = [0]*(N)
gcds[0] = 0
rgcds[0] = 0

for i in range(N-1):
    gcds[i+1] = gcd(As[i], gcds[i])
    rgcds[i+1] = gcd(re_As[i], rgcds[i])

rgcds = rgcds[::-1]

ans = [0]*(N+1)

for i, (s, r) in enumerate(zip(gcds, rgcds)):
    ans[i] = gcd(s, r)
    
print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

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

left = [0]*n
right= [0]*n

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
s1 = [0]*(n+1)
s2 = [0]*(n+1)
s1[0] = 0
s1[1] = a[0]
s2[0] = 0
s2[n] = a[n-1]
for i in range(2, n+1):
    s1[i] = gcd(s1[i-1], a[i-1])
    s2[n-i+1] = gcd(s2[n-i+2], a[n-i])
if s1[n-1] >= s2[2]:
    ans = s1[n-1]
else:
    ans = s2[2]
for i in range(2, n):
    b = gcd(s1[i-1], s2[i+1])
    if ans <= b:
        ans = b
print(ans)

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  A = sorted([int(_) for _ in input().split()])
  a0 = set()
  for i in range(1, int(A[0]**0.5)+1):
    if A[0]%i == 0:
      a0.add(i)
      a0.add(A[0]//i)
  a0 = list(a0)
  a1 = set()
  for i in range(1, int(A[1]**0.5)+1):
    if A[1]%i == 0:
      a1.add(i)
      a1.add(A[1]//i)
  a1 = list(a1)
  ret = 1
  for p in a0:
    cc = 0
    if p == 1:
      continue
    for a in A:
      if a%p != 0:
        cc += 1
    if cc <= 1:
      ret = max(ret, p)
  for p in a1:
    cc = 0
    if p == 1:
      continue
    for a in A:
      if a%p != 0:
        cc += 1
    if cc <= 1:
      ret = max(ret, p)
  print(ret)
  return

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# solution
import io
from fractions import gcd

data=int(input())
array=list(map(int,input().split()))
k=[0]
l=[0]
for i in range(data-1):
    k.append(gcd(k[i],array[i]))
    l.append(gcd(l[i],array[data-i-1]))
ans=0
for i in range(data):
    ans=max(ans,gcd(k[i],l[data-i-1]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
tA=list(reversed(A))
l=[0]
r=[0]
m=[]
for i in range(N):
  l.append(gcd(l[i],A[i]))
  r.append(gcd(r[i],tA[i]))
r=list(reversed(r))
for i in range(N):
  m.append(gcd(l[i],r[i+1]))
print(max(m))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from fractions import gcd

n, *a = map(int, read().split())
b = a[::-1]
cumsum_m = [0] * (n - 1)
cumsum_p = [0] * (n - 1)
cumsum_m[0] = b[0]
cumsum_p[0] = a[0]
for i in range(1, n - 1):
    cumsum_p[i] = gcd(cumsum_p[i - 1], a[i])
    cumsum_m[i] = gcd(cumsum_m[i - 1], b[i])
ans = max(cumsum_m.pop(), cumsum_p.pop())
for p, m in zip(cumsum_p, cumsum_m[::-1]):
    v = gcd(p, m)
    if ans < v:
        ans = v
print(ans)

Submission status: Accepted

Solution code:
class Segtree:
    def __init__(self, original, func, element):
        self.n = len(original)
        self.element = element
        self.func = func
        self.N0 = 1 << (n-1).bit_length()
        self.seg = [element]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = func(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            i >>= 1
            x = self.func(x, y)
            self.seg[i] = x
                
    def query(self, l, r):
        res = self.element
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = self.func(res, self.seg[r-1])
            if l & 1:
                res = self.func(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

    
import sys
input = sys.stdin.readline
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))
seg = Segtree(A, gcd, 0)
ans = 0
for i in range(n):
  left = seg.query(0, i)
  right = seg.query(i+1, n)
  temp = gcd(left, right)
  ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
class Segtree:
    def __init__(self, original, func, element):
        self.n = len(original)
        self.element = element
        self.func = func
        self.N0 = 1 << (n-1).bit_length()
        self.seg = [element]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = func(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y <= x:
              break
            i >>= 1
            x = self.func(x, y)
            self.seg[i] = x
                
    def query(self, l, r):
        res = self.element
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = self.func(res, self.seg[r-1])
            if l & 1:
                res = self.func(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

    
import sys
input = sys.stdin.readline
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))
seg = Segtree(A, gcd, 0)
ans = 0
for i in range(n):
  left = seg.query(0, i)
  right = seg.query(i+1, n)
  temp = gcd(left, right)
  ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

n=int(input())
a_1=list(map(int,input().split()))
a_2=list(reversed(a_1))
l=[0]
r=[0]

for i in range(n):
    l.append(gcd(l[i],a_1[i]))  

for i in range(n):    
    r.append(gcd(r[i],a_2[i]))
    
r=list(reversed(r))

m=[]
for i in range(n):
   m.append(gcd(l[i],r[i+1])) 

print(max(m))

Submission status: Accepted

Solution code:
from fractions import gcd

n=int(input())
a_1=list(map(int,input().split()))
a_2=list(reversed(a_1))
l=[0]
r=[0]

for i in range(n):
    l.append(gcd(l[i],a_1[i]))  

for i in range(n):    
    r.append(gcd(r[i],a_2[i]))
    
r=list(reversed(r))

m=[]
for i in range(n):
   m.append(gcd(l[i],r[i+1])) 

print(max(m))

Submission status: Accepted

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


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


# input = sys.buffer.readlines()
n = int(input())
a = list(map(int, input().split()))
# 左右からの累積和を計算し、どのいちを消すかでループ回す
r_cum = [0] * n
l_cum = [0] * n
r_cum[n - 1] = a[-1]
l_cum[0] = a[0]
for i in range(1, n):
    l_cum[i] = gcd(l_cum[i - 1], a[i])
for i in range(n - 2, -1, -1):
    r_cum[i] = gcd(r_cum[i + 1], a[i])
# 本当は番兵を入れると実装が楽だった
ans = max(l_cum[n - 2], r_cum[1])
# print(r_cum, l_cum)
for i in range(1, n - 1):
    ans = max(ans, gcd(r_cum[i + 1], l_cum[i - 1]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

left = [0] * n
left[0] = a[0]

right = [0] * n
right[n-1] = a[n-1]

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

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

b = [0] * n
b[0] = right[1]
b[n-1] = left[n-2]

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

print(max(b))

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    from fractions import gcd
    n = int(input())
    A = readInts()
    left = [0] * (n+1)
    right = [0] * (n+1)
    for i in range(1,n):
        left[i] = gcd(left[i-1],A[i-1])
    for i in range(n-2,-1,-1):
        right[i] = gcd(right[i+1],A[i+1])
    # 全部で探索してみるべ
    res = 0
    for i in range(n):
        l = left[i]
        r = right[i]
        res = max(res,gcd(l,r))
    print(res)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import fractions


N = int(input())
A = list(map(int, input().split()))
L, R = [0]*N, [0]*N
for i in range(1, N):
    L[i] = fractions.gcd(L[i-1], A[i-1])
    R[-i-1] = fractions.gcd(R[-i], A[-i])
ans = 0
for l, r in zip(L, R):
    ans = max(ans, fractions.gcd(l, r))
print(ans)

Submission status: Accepted

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

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

l,r = [0],[0]
for i in range(n-1):
    l.append(gcd(l[-1],a[i]))
    r.append(gcd(r[-1],a[n-i-1]))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def gcd(a, b): return gcd(b, a % b) if b else abs(a)
def lcm(a, b): return abs(a // gcd(a, b) * b)

n, *a = map(int, sys.stdin.read().split())

def main():
    lg = [0] * n
    rg = [0] * n
    for i in range(1, n):
        lg[i] = gcd(lg[i-1], a[i-1])
    for i in range(n-2, -1, -1):
        rg[i] = gcd(rg[i+1], a[i+1])
    res = max([gcd(lg[i], rg[i]) for i in range(n)])
    print(res)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    from fractions import gcd
    #ma = -1
    n = int(input())
    A = readInts()
    left = [0] * (n+1)
    right = [0] * (n+1)
    for i in range(n):
        left[i+1] = gcd(left[i],A[i])
    for i in range(n-1,-1,-1):
        right[i] = gcd(right[i+1],A[i])
    # 集計
    res = 0
    for i in range(n):
        l = left[i]
        r = right[i+1]
        res = max(res,gcd(l,r))
    print(res)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    import sys 
    from fractions import gcd 
    input = sys.stdin.readline 

    def init(init_val):
        for i in range(n):
            seg[i+num-1] = init_val[i]
        for i in range(num-2,-1,-1):
            seg[i] = gcd(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] = gcd(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return 0
        p += num - 1
        q += num - 2
        res = 0
        while q - p > 1:
            if p & 1 == 0:
                res = gcd(res, seg[p])
            if q & 1 == 1:
                res = gcd(res, seg[q])
                q -= 1
            p //= 2
            q = (q - 1)//2

        if p==q:
            res = gcd(res, seg[p])
        else:
            res = gcd(gcd(res, seg[p]), seg[q])
        return res
         
    n= int(input())
    a = tuple(map(int, input().split()))
    num = 2**(n-1).bit_length()
    seg = [0]*2*num
    init(a)    
                
    ans = -1
    for i in range(n):
        ans = max(ans, gcd(query(0,i), query(i+1,n)))
    print(ans) 

if __name__ == '__main__':
    main()

Submission status: Accepted

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

left = [0]*n
right = [0]*n
from fractions import gcd
for i in range(1,n):
  left[i] = gcd(left[i-1],a[i-1])
  right[n-i-1] = gcd(right[n-i],a[n-i])

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

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(N):
    L.append(gcd(L[i],A[i]))
    R.append(gcd(R[i],A[-(i+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:
from fractions import gcd

X = int(input())

line = input()
numbers = [int(n) for n in line.split()]

left_list = [0]*(X+1)
right_list = [0]*(X+1)
for i in range(X):
    left_list[i+1] = gcd(left_list[i], numbers[i])
    right_list[X-1-i] = gcd(right_list[X-i], numbers[X-1-i])
predicted_value = max([gcd(left_list[i], right_list[i+1]) for i in range(X)])

print(predicted_value)

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
from fractions import gcd
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
a = nl()

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

ans = []

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = [int(i) for i in input().split()]

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

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

print(mx)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
gcd_b = {}
gcd_a = {}
gcd_b[-1] = 0
for i in range(N):
    gcd_b[i] = gcd(gcd_b[i-1], A[i])
gcd_a[N] = 0
for i in range(N):
    gcd_a[N-1-i] = gcd(gcd_a[N-i], A[N-1-i])
ans = 0
for i in range (N):
    ans = max(ans, gcd(gcd_b[i-1], gcd_a[i+1]))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# A[i]の左までのgcdと右以降のgcdを保持
N = ir()
A = lr()

def calc(arr):
    ret = [arr[0]]
    g = arr[0]
    for x in arr[1:]:
        g = gcd(g, x)
        ret.append(g)
    return ret

g_left = calc(A)
g_right = calc(A[::-1])[::-1]

cand = [g_right[1]]
for i in range(1, N-1):
    temp = gcd(g_left[i-1], g_right[i+1])
    cand.append(temp)

cand.append(g_left[-2])
answer = max(cand)
print(answer)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ar = a[::-1]
    lgcds = [1]*n
    rgcds = [1]*n
    lgcd, rgcd = a[0], ar[0]
    lgcds[0] = rgcd
    lgcds[1] = lgcd
    rgcds[n-1] = lgcd
    rgcds[n-2] = rgcd
    for i in range(2, n):
        lgcd = gcd(lgcd, a[i-1])
        rgcd = gcd(rgcd, ar[i-1])
        lgcds[i] = lgcd
        rgcds[n-1-i] = rgcd
    ans = 1
    for i in range(n):
        gi = gcd(lgcds[i], rgcds[i])
        if gi > ans:
            ans = gi
    print(ans)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ar = a[::-1]
    lgcds = [1]*n
    rgcds = [1]*n
    lgcd, rgcd = a[0], ar[0]
    lgcds[0] = rgcd
    lgcds[1] = lgcd
    rgcds[n-1] = lgcd
    rgcds[n-2] = rgcd
    for i in range(2, n):
        lgcd = gcd(lgcd, a[i-1])
        rgcd = gcd(rgcd, ar[i-1])
        lgcds[i] = lgcd
        rgcds[n-1-i] = rgcd
    ans = 1
    for i in range(n):
        gi = gcd(lgcds[i], rgcds[i])
        if gi > ans:
            ans = gi
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (fractions.gcd(left[i],a[i]))
    right[n - i - 1] = (fractions.gcd(right[n - i],a[n - 1 - i]))

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

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
from itertools import accumulate as acc
def gcd(a,b):
    while b: a, b = b, a%b
    return a
def main():
    n = II()
    aa = MII()
    b = list(acc([0]+aa, gcd))
    c = list(acc([0]+aa[::-1], gcd))
    print(max(gcd(s,t) for s, t in zip(b, c[::-1][1:])))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class SegmentTree():
    def segfunc(self, x, y):
        if x > y:
            x, y = y, x
        if x == -1:
            return y
        return gcd(x, y) #関数
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = -1 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[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
    
from fractions import gcd
    
N = int(input())
A = list(map(int, input().split()))
M = 0
S = SegmentTree(A)
for i in range(N):
    M = max(M, S.segfunc(S.query(0,i), S.query(i+1, N)))
print(M)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

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

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

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

dp1 = []
dp2 = []

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

for i in range(len(a_list)):
    if not dp1:
        dp1.append(a_list[0])
    else:
        dp1.append(gcd(dp1[-1], a_list[i]))
    if not dp2:
        dp2.append(a_list[-1])
    else:
        dp2.append(gcd(dp2[-1], a_list[-i-1]))

ret = 0

dp2.reverse()

for i in range(len(a_list)-2):
    val = gcd(dp1[i], dp2[-len(dp2)+2+i])
    ret = max(ret, val)

ret = max(ret, dp1[-2], dp2[1])

print(ret)

Submission status: Accepted

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

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

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

R = [A[-1]]
for i in range(n-2, -1, -1):
  R.append(gcd(R[-1], A[i]))
R = list(reversed(R))

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

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

l = [0]
r = [0]

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

print(max(fractions.gcd(l[i], r[-i-1]) for i in range(N)))

Submission status: Accepted

Solution code:
from fractions import gcd

n=int(input())
A=list(map(int,input().split()))
left=[0]*n
right=[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:
n = int(input())
nums = list(map(int, input().split()))

# maekara は 前から当該までの最大公約数
# ushirokara は 後ろから当該までの最大公約数
import fractions

maekara = [-1] * n
ushirokara = [-1] * n

maekara[0] = nums[0]
for i in range(1, n):
    maekara[i] = fractions.gcd(maekara[i-1], nums[i])

ushirokara[-1] = nums[-1]
for i in reversed(range(n-1)):
    ushirokara[i] = fractions.gcd(ushirokara[i+1], nums[i])

ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans, ushirokara[1])
    elif i == n-1:
        ans = max(ans, maekara[n-2])
    else:
        ans = max(ans, fractions.gcd(maekara[i-1], ushirokara[i+1]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class SegmentTree:

    def __init__(self, array, operator, identity):
        self.identity = identity
        self.operator = operator

        self.array_size = len(array)
        tree_height = (self.array_size - 1).bit_length()
        self.tree_size = 2 ** (tree_height + 1)
        self.leaf_start_index = 2 ** tree_height
        self.tree = [identity] * self.tree_size

        for i in range(self.array_size):
            self.tree[self.leaf_start_index + i] = array[i]

        for i in range(1, tree_height):
            begin = 1 << (tree_height - i)
            end = begin << 1
            for j in range(begin, end):
                self.tree[j] = self.operator(self.tree[j << 1], self.tree[j << 1 | 1])

    def update(self, index, val):
        cur_node = self.leaf_start_index + index
        self.tree[cur_node] = val

        while cur_node > 1:
            self.tree[cur_node >> 1] = self.operator(self.tree[cur_node], self.tree[cur_node ^ 1])
            cur_node >>= 1

    def query(self, begin, end):
        res = self.identity

        if begin < 0:
            begin = 0
        elif begin > self.array_size:
            return self.identity

        if end > self.array_size:
            end = self.array_size
        elif end < 1:
            return self.identity

        left = begin + self.leaf_start_index
        right = end + self.leaf_start_index

        while left < right:
            if left & 1:
                res = self.operator(res, self.tree[left])
                left += 1

            if right & 1:
                right -= 1
                res = self.operator(res, self.tree[right])

            left >>= 1
            right >>= 1

        return res


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, readline().split()))
    seg = SegmentTree(a, gcd, 0)
    ans = 0

    for i in range(n):
        temp1 = seg.query(0, i)
        temp2 = seg.query(i + 1, n)
        temp = gcd(temp1, temp2)
        ans = max(ans, temp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

def segfunc(x, y):
    return gcd(x, y)
ide_ele = 0
"""
最小値 min(x, y),float('inf) RMQ
最大値 max(x, y),float('inf)
区間和 x + y,0 BIT
区間積 x * y,1
最大公約数 math.gcd(x, y),0
"""

class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):
 
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        # 葉の数 2**n個
        self.tree = [ide_ele] * 2 * self.num
        # 木の要素数は1originだとこう
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築 葉に数列の値を
        # 葉のindexはnum ~ num + n
        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
        # 葉のスタートのindexはnumのため
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1
            # 親へ
            # 1とのXORは兄弟になる

    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 = 0
for i in range(N):
    left = seg.query(0, i)
    right = seg.query(i + 1, N)
    ans = max(ans, gcd(left, right))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
gcd1 = [0] * (N - 1)
gcd1[0] = A[0]
gcd2 = [0] * (N - 1)
gcd2[-1] = A[-1]
for i in range(N - 2):
    a, b = gcd1[i], A[i + 1]
    while b:
        a, b = b, a % b
    gcd1[i + 1] = a
    a, b = gcd2[-i-1], A[-i-2]
    while b:
        a, b = b, a % b
    gcd2[-i-2] = a
ans = max(gcd1[-1], gcd2[0])
for i in range(N - 2):
    a, b = gcd1[i], gcd2[i + 1]
    while b:
        a, b = b, a % b
    ans = max(a, ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = list(map(int, input().split()))
# 左から
L = [0 for _ in range(n + 1)]
for i in range(n):
    L[i + 1] = gcd(L[i], a[i])

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

# print(L)
# print(R)
m = 0
for i in range(n):
    m = max(m, gcd(L[i], R[i + 1]))
print(m)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a = [int(i) for i in input().split()]
# 累積 gcd（左と右両方）
left, right = [0] * (n + 1), [0] * (n + 1)
for i in range(n):
    left[i + 1] = gcd(left[i], a[i])
for i in reversed(range(0, n)):
    right[i] = gcd(right[i + 1], a[i])


# 累積
ans = 0
for i in range(n):
    l = left[i]
    r = right[i + 1]
    ans = max(ans, gcd(l, r))
print(ans)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
c1, c2 = [0, a[0]], [a[n - 1]]
x, y = a[0], a[n - 1]
for i in range(n - 2):
    x = gcd(x, a[i + 1])
    y = gcd(y, a[n - 2 - i])
    c1.append(x)
    c2.append(y)
c2.reverse()
c2.append(0)
ans = 0
for i in range(n):
    if c1[i] != 0 and c2[i] != 0:
        m = gcd(c1[i], c2[i])
        ans = max(ans, m)
    else:
        ans = max(ans, max(c1[i], c2[i]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import *
from itertools import *
N = int(input())
A = list(map(int,input().split()))
B = list(accumulate([0]+A,gcd))
C = list(accumulate([0]+A[::-1],gcd))
print(max(gcd(s,t)for s,t in zip(B,C[::-1][1:])))