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:
# ABC125C - GCD on Blackboard
from fractions import gcd


def segfunc(x, y):  # modify for each case
    return gcd(x, y)


class SegmentTree:
    def __init__(
        self,
        init_val: "initial value: Array or str",
        ide_ele: "identity element corresponding init_val" = 0,
    ):
        self.size = 1 << (len(init_val) - 1).bit_length()
        self.ide_ele = ide_ele
        self.tree = self._build(init_val)

    def _build(self, init_val: "Array or str"):
        tree = [self.ide_ele] * (2 * self.size)

        for idx, val in enumerate(init_val):  # set
            # modify val if needed (e.g. str -> ord())            
            tree[idx + self.size - 1] = val

        for idx in range(self.size - 2, -1, -1):  # build
            tree[idx] = segfunc(tree[2 * idx + 1], tree[2 * idx + 2])
        return tree

    def update(self, idx: int, val):
        idx += self.size - 1
        # modify val if needed as same as in _build()
        self.tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            self.tree[idx] = segfunc(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

    def query(self, left: int, right: int):
        left += self.size
        right += self.size
        ret = self.ide_ele
        while left < right:
            if left & 1:
                ret = segfunc(ret, self.tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                ret = segfunc(ret, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return ret


def main():
    N, *A = map(int, open(0).read().split())
    seg = SegmentTree(A)
    ans = 0
    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:
# ABC125C - GCD on Blackboard
from fractions import gcd


def segfunc(x, y):  # modify for each case
    return gcd(x, y)


class SegmentTree:
    def __init__(
        self,
        init_val: "initial value: Array or str",
        ide_ele: "identity element corresponding init_val" = 0,
    ):
        self.size = 1 << (len(init_val) - 1).bit_length()
        self.ide_ele = ide_ele
        self.tree = self._build(init_val)

    def _build(self, init_val: "Array or str"):
        tree = [self.ide_ele] * (2 * self.size)

        for idx, val in enumerate(init_val):  # set
            # modify val if needed (e.g. str -> ord())            
            tree[idx + self.size - 1] = val

        for idx in range(self.size - 2, -1, -1):  # build
            tree[idx] = segfunc(tree[2 * idx + 1], tree[2 * idx + 2])
        return tree

    def update(self, idx: int, val):
        idx += self.size - 1
        # modify val if needed as same as in _build()
        self.tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            self.tree[idx] = segfunc(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

    def query(self, left: int, right: int):
        if left >= right:
            return self.ide_ele

        left += self.size
        right += self.size
        ret = self.ide_ele
        while left < right:
            if left & 1:
                ret = segfunc(ret, self.tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                ret = segfunc(ret, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return ret


def main():
    N, *A = map(int, open(0).read().split())
    seg = SegmentTree(A)
    ans = 0
    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 fractions as math

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

l = [a[0] for _ in range(n+2)]
r = [a[-1] for _ in range(n+2)]

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

ans = [math.gcd(l[i], r[i+2]) for i in range(n)]
print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

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

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

Submission status: Accepted

Solution code:
def GCD(x,y):
    x,y=max(x,y),min(x,y)
    if y==0:
        return x
    elif x%y==0:
        return y
    else:
        return GCD(y,x%y)

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

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

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

G=[0 for i in range(N+2)]
for i in range(1,N+1):
    G[i]=GCD(L[i-1],R[i+1])

print(max(G))

Submission status: Accepted

Solution code:
from fractions import gcd

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]
L[0] = A[0]
R[-1] = A[-1]
for i in range(N-1):
  L[i+1] = gcd(L[i],A[i+1])
  R[N-2-i] = gcd(R[N-1-i],A[N-2-i])
#print(L)
#print(R)

ans = 0
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 fractions import gcd
#from math import gcd
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
ans = 0

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

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

Submission status: Accepted

Solution code:
def gcd(x,y): 
	while y != 0:
		x , y = y , x % y 
	return x
n = int(input())
A = list(map(int,input().split()))
lgcds=[1 for _ in range(n)]
rgcds=[1 for _ in range(n)]
lgcd  = A[0]
rgcd = A[-1]
for i in range(1,n):
    lgcd =gcd(A[i-1],lgcd)
    lgcds[i] = lgcd
for i in range(n-2,-1,-1):
    rgcd =gcd(A[i+1],rgcd)
    rgcds[i] = rgcd
ans =[1 for _ in range(n)]
for i in range(n):
    if i ==0:
        ans[i]=rgcds[i]
    elif i ==n-1:
        ans[i]=lgcds[i]
    else:
        ans[i]=gcd(rgcds[i],lgcds[i])
print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

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


def gcd2(x, y):
    if not x:
        return y
    if not y:
        return x
    return gcd(x, y)


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

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

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(1,n):
	l=gcd(L[i-1],A[i-1])
	L.append(l)
	r=gcd(R[i-1],A[n-i])
	R.append(r)
G=[]
for i in range(n):
	g=gcd(L[i],R[n-1-i])
	G.append(g)
print(max(G))

Submission status: Accepted

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

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

Prefix=[0 for i in range(n + 2)] 
Suffix=[0 for i in range(n + 2)] 

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

Suffix[n] = a[n - 1] 

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

ans = max(Suffix[2], Prefix[n - 1]) 

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SegTree:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_val: 区間[l, r)の値を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数
        :param func: 値の操作に使う関数(min, max, addなど)
        :param init: 要素の初期値
        """
        n += 1
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = self.func(x, self.tree[i ^ 1])
            i >>= 1
 
    def get_val(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.init
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

N=INT()
A=LIST()

st=SegTree(N+2, gcd, 0)
for i in range(N):
    st.update(i+1, A[i])

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

Submission status: Accepted

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

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))

    L = [0]
    R = [0]

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

    ans = 0

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

    print(ans)

Submission status: Accepted

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

import sys
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd

left = [a[0]]
right = [a[-1]]

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

ans = 0
for i in range(n):
    if i == 0:
        num = right[n-i-2]
    elif i == n - 1:
        num = left[i-1]
    else:
        num = gcd(left[i-1], right[n-i-2])
    if num > ans:
        ans = num

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

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

def main():
    """ main """
    N = int(input())
    AS = list(map(int, input().split()))
    L = [0]*(N+2)
    R = [0]*(N+2)
    for i in range(0,N):
        L[i+1] = gcd(L[i],AS[i])
    for i in range(N-1,-1,-1):
        R[i] = gcd(R[i+1],AS[i])
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(L[i],R[i+1]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

gcds = [-1] * N
gcds_rev = [-1] * N
for i in range(0,N):
  if i == 0: gcds[i] = A[0]
  else: gcds[i] = gcd(gcds[i-1], A[i])

  rev_i = N-1-i
  if rev_i == N-1: gcds_rev[rev_i] = A[-1]
  else: gcds_rev[rev_i] = gcd(gcds_rev[rev_i+1], A[rev_i])

ans = -float('inf')
for i in range(N):
  if i == 0:val = gcds_rev[1]
  elif i == N-1:val = gcds[-2]
  else: val = gcd(gcds[i-1], gcds_rev[i+1])
  ans = max(ans, val)
print(ans)

Submission status: Accepted

Solution code:
def gcd(x, y):
    x, y = max(x, y), min(x, y)
    if y == 0:
        return x
    return gcd(y, x % y)


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

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

for i in range(n - 1, -1, -1):
    if i == n - 1:
        r[i] = a[i]
        continue
    r[i] = gcd(a[i], r[i+1])

l = [0] + l[:-1]
r = r[1:] + [0]

ans = 0
for x, y in zip(l, r):
    ans = max(ans, gcd(x, y))
print(ans)

Submission status: Accepted

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


def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

L = [0]
R = [0]

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

R = list(reversed(R))


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

# 上のループだと、左端を除いたパターンと右端を除いたパターンが含まれないのでここで考慮に入れる
ans = max(ans, R[1])
ans = max(ans, L[-2])

print(ans)
#print(R)
#print(L)

Submission status: Accepted

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


def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

L = [0]
R = [0]

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

R = list(reversed(R))


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

ans = max(ans, R[1])
ans = max(ans, L[-2])

print(ans)
#print(R)
#print(L)

Submission status: Accepted

Solution code:
import sys
#from math import gcd

#+++++

def gcd(a,b):
	if a < b:
		a,b=b,a
		
	while a != b:
		t=a%b
		if t == 0:
			return b
		else:
			a,b = b,t
	return a
	
def main():
	n = int(input())
	al = list(map(int, input().split()))
	
	if n == 2:
		return max(al)
	
	from_left=[0]*len(al)
	kk=al[0]
	for i, v in enumerate(al):
		kk=gcd(kk,v)
		from_left[i]=kk
	
	from_right=[0]*len(al)
	kk=al[-1]
	for i,v in enumerate(al[::-1]):
		kk=gcd(kk,v)
		from_right[i]=kk
	from_right=from_right[::-1]
	
	ans=0
	for i,_ in enumerate(al):
		if i == 0:
			vv=from_right[1]
		elif i == len(al)-1:
			vv=from_left[-2]
		else:
			a=from_right[i+1]
			b=from_left[i-1]
			#pa((a,b))
			vv=gcd(a,b)
		ans = max(ans, vv)
	print(ans)




#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from fractions import gcd
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
 
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.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+1:
            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=[int(i) for i in input().split()]
B=segtree(A,gcd,0)
C=[gcd(B.query(0,i),B.query(i+1,N)) for i in range(N)]
print(max(C))

Submission status: Accepted

Solution code:
from fractions import gcd
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
 
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.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+1:
            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=[int(i) for i in input().split()]
B=segtree(A,gcd,0)
C=[gcd(B.query(0,i),B.query(i+1,N+1)) for i in range(N+1)]
print(max(C))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
m=[0]*n
L,R=[0]*(n+1),[0]*(n+1)
for i in range(1,n+1):
    L[i]=gcd(L[i-1],a[i-1])
    R[n-i]=gcd(R[n-i+1],a[n-i])
for i in range(n):
    m[i]=gcd(L[i],R[i+1])
print(max(m))

Submission status: Accepted

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

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

ans = 0

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

Submission status: Accepted

Solution code:
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    g_l = [[0, 0] for _ in range(n + 1)]

    for i in range(n):
        g_l[i+1][0] = fractions.gcd(g_l[i][0], a[i])
        g_l[-i-2][1] = fractions.gcd(g_l[-i-1][1], a[-i-1])
    m_g = 0
    for i in range(n):
        m_g = max(m_g, fractions.gcd(g_l[i][0], g_l[i + 1][1]))
    print(m_g)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
# ABC125 C - GCD on Blackboard
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))

l = n*[0]
r = n*[0]
ans = 0

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

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

Submission status: Accepted

Solution code:
#C
import sys
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
if len(a)==2:
    print(max(a))
    sys.exit()
g=gcd(a[0],a[1])
b=[]
for i in range(2,n):
    l=gcd(g,a[i])
    if l!=g:
        b.append(i)
        g=l
s=[]
g=gcd(a[0],a[2])
for i in range(3,n):
    g=gcd(g,a[i])
s.append(g)
g=gcd(a[1],a[2])
for i in range(3,n):
    g=gcd(g,a[i])
s.append(g)
for i in range(len(b)):
    g=gcd(a[0],a[1])
    for j in range(2,n):
        if j==b[i]:
            continue
        g=gcd(g,a[j])
    s.append(g)
print(max(s))

Submission status: Accepted

Solution code:
from fractions import gcd

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    M = [0] * N
    L = [0] * (N+2)
    R = [0] * (N+2)
    for i in range(1,N+1):
        i_r = N-i
        L[i] = gcd(L[i-1], A[i-1])
        R[i_r] = gcd(R[i_r+1], A[i_r])
        
    for i in range(N):
        M[i] = gcd(L[i], R[i+1])

    print(max(M))
    
solve()

Submission status: Accepted

Solution code:
#プログラムの例:
n=int(input())
listsT=list(map(int,input().split()))
from fractions import gcd
lists_left=[]
lists_right=[]
number1=0
number2=0
for i in range(n):
    if i==0:
        lists_left.append(0)
    if i==1:
        lists_left.append(listsT[0])
        number1=listsT[0]
    if i>=2:
        number1=gcd(number1,listsT[i-1])
        lists_left.append(number1)

number2=listsT[-1]
for j in range(n,0,-1):
    if j==n:
        lists_right.append(0)
    if j==n-1:
        lists_right.append(listsT[-1])
    if j<n-1:      
        number2=gcd(number2,listsT[j])  
        lists_right.append(number2)
ans=0
for x in range(n):
    if ans<= gcd(lists_right[x],lists_left[n-1-x]):
        ans=gcd(lists_right[x],lists_left[n-1-x])   
print(ans)

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = list(map(int, input().split()))
max_val = 0
#i番目を消すとするとR[i+1]とL[i-1]のgcdが答え
L = [0] * N
R = [0] * N
for i in range(N-1):
    L[i+1] = fractions.gcd(L[i], A[i])
for i in range(N-1, 0, -1):
    R[i-1] = fractions.gcd(R[i], A[i])
#R.reverse()
for i in range(N):
    max_val = max(max_val, fractions.gcd(L[i], R[i]))


print(max_val)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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




class SegmentTree:
    def __init__(self, init_val, ide_ele, op):
        n = len(init_val)
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [ide_ele] * 2 * self.num
        self.ide_ele = ide_ele
        self.op = op
        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.op(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 + 1:
            k = (k - 1) // 2
            self.seg[k] = self.op(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.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
            p = p // 2
            q = (q - 2) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res



n = I()
L = LI()
ST = SegmentTree(L, 0, gcd)
print(max([gcd(ST.query(0, i), ST.query(i + 1, n)) for i in range(n)]))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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




class SegmentTree:
    def __init__(self, init_val, ide_ele, op):
        n = len(init_val)
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [ide_ele] * 2 * self.num
        self.ide_ele = ide_ele
        self.op = op
        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.op(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 + 1:
            k = (k - 1) // 2
            self.seg[k] = self.op(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.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res



n = I()
L = LI()
ST = SegmentTree(L, 0, gcd)
print(max([gcd(ST.query(0, i), ST.query(i + 1, n)) for i in range(n)]))

Submission status: Accepted

Solution code:
import fractions

n = int(input())
A_list = list(map(int, input().split()))
Left = [0]*(n+1)
Right = [0]*(n+1)
for i in range(n):
    Left[i+1] = fractions.gcd(Left[i], A_list[i])
    Right[n-i-1] = fractions.gcd(Right[n-i], A_list[n-i-1])
gcd_max = 0
for del_pos in range(n):
    gcd_ = fractions.gcd(Left[del_pos], Right[del_pos+1])
    if gcd_max < gcd_:
        gcd_max = gcd_
print(gcd_max)

Submission status: Accepted

Solution code:
# PDF解説
N = int(input())
A = [int(a) for a in input().split()]

import fractions

L = []
# [gcd(0), gcd(0, A[0]), ... , gcd(0, A[0], A[1], ..., A[N-2])]
R = []
# [gcd(A[1], A[2], ... , A[N-1], 0), gcd(A[2], A[3], ... , A[N-1], 0), ... , gcd(0)]

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# 累積和(gcd)
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
lcg = A[:]
rcg = A[:]
for i in range(1, N):
  lcg[i] = gcd(lcg[i], lcg[i - 1])
for i in range(N - 2, -1, -1):
  rcg[i] = gcd(rcg[i], rcg[i + 1])
t = [0] * N
t[0] = rcg[1]
for i in range(1, N - 1):
  t[i] = gcd(lcg[i - 1], rcg[i + 1])
t[N - 1] = lcg[N - 2]
print(max(t))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()


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


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


print(ret)

Submission status: Accepted

Solution code:
import fractions
n = int(input())
a = [0] + list(map(int, input().split())) + [0]

# 前処理。left, rightでそれぞれ累積gcdを作っておく
left = [0] * (n + 2)
right = [0] * (n + 2)

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

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

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

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

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = list(map(int,input().split()))
L = [A[0]]
R = [A[-1]]

for i in range(1,N):
  L.append(fractions.gcd(L[-1],A[i]))
for j in range(N-2,-1,-1):
  R.append(fractions.gcd(R[-1],A[j]))

ans = 0
for m in range(N):
  if m == 0:
    ans = R[-2]
  elif m == N - 1:
    ans = max(ans,L[N-2])
  else:
    M = fractions.gcd(L[m-1],R[N-m-2])
    ans = max(ans,M)
print(ans)