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:
n=int(input())
A=list(map(int,input().split()))

L,R=[0]*n,[0]*n
L[0],R[-1]=A[0],A[-1]

from fractions import gcd

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(x, y):
  if(x == 0):
    return y
  elif(y == 0):
    return x
  else:
    while(x % y != 0 and y % x != 0):
      if(x > y):
        x = x % y
      else:
        y = y % x
    if(x > y):
      return y
    else:
      return x
  
N = int(input())
A = list(map(int, input().split()))
L = [0]*(N+2) #L[i]:= 1, 2, ..., i-1番目までの最大公約数
R = [0]*(N+2) #R[i]:= i, i+1, i+2, ..., N番目までの最大公約数
M = [0]*N
L[0] = 0
R[N+1] = 0
for i in range(N):
  L[i+1] = gcd(L[i], A[i])
for i in range(N, 0, -1):
  R[i] = gcd(R[i+1], A[i-1])
for i in range(N):
  M[i] = gcd(L[i], R[i+2])
print(max(M))

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
gl=[0]
gr=[0]
for i in range(n):
  gl.append(gcd(a[i], gl[-1]))
  gr.append(gcd(a[n-i-1], gr[-1]))
gr=gr[::-1]
ans = 0
for i in range(n):
  ans = max(ans, gcd(gl[i],gr[i+1]))
  
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

def gcd_list(numbers):
  return reduce(gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
gl=[0]
gr=[0]
for i in range(n):
  gl.append(gcd(a[i], gl[-1]))
  gr.append(gcd(a[n-i-1], gr[-1]))
gr=gr[::-1]
ans = 0
for i in range(n):
  ans = max(ans, gcd(gl[i],gr[i+1]))
  
print(ans)

Submission status: Accepted

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

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

# 1個目と2個目の約数列挙
# ⇨ 1個しか消さないから必ずどちらかの約数は残る
divs = make_divisors(As[0]) + make_divisors(As[1])
divs = list(set(divs))
cnt = 1

for div in sorted(divs,reverse=True):
    a = sum([1 for a in As if a%div == 0])
    if n - a <= 1:
        print(div)
        exit()

Submission status: Accepted

Solution code:
"""
左右の累積gcdをもたせて置く

i番目を除く(i=1)
R : acc[i-1]
L : racc[n-i-1] 
"""

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

def gcd(n, m):
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a


acc = [As[0]]
racc = [As[-1]] #(右から)i番目の累積gcd
for i in range(1,n):
    acc.append(gcd(acc[i-1],As[i]))
    racc.append(gcd(racc[i-1],As[-i-1]))

racc = racc[::-1] #i番目以降のgcd
ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans, racc[i+1])
    elif i == n-1:
        ans = max(ans, acc[i-1])
    else:
        ans = max(ans, gcd(acc[i-1],racc[i+1]))
    
print(ans)

Submission status: Accepted

Solution code:
# from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
As = list(map(int, input().split()))

def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

class segmented_tree:
    X_unit = 1 << 30
    X_f = lambda self, a, b: gcd(a,b)
    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (2*N)
        
    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x 
        # 後ろから入れていく
        for i in range(self.N-1, 0, -1):
            self.X[i] = self.X_f(self.X[i<<1], self.X[i<<1|1])

    # 1点更新
    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i<<1],self.X[i<<1|1])
    
    # 区間取得
    def fold(self, l, r):
        l += self.N
        r += self.N
        vl = self.X[l]
        vr = self.X[r-1]
        # 外から決めていく
        while l < r:
            # print(l,r)
            if l & 1:
                vl = self.X_f(vl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.X_f(vr, self.X[r])
            l >>= 1
            r >>= 1
        return self.X_f(vl,vr)
  
st = segmented_tree(n)
st.build(As)
mx = 0
for i in range(n):
    if i == 0:
        a = st.fold(i+1,n)
    else:
        a = st.fold(0,i)
    if i+1 < n:
        b = st.fold(i+1,n)
    else:
        b = a        
    mx = max(mx,gcd(a,b))
print(mx)

Submission status: Accepted

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

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : fractions.gcd(x,y), default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        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
    
tree = SegmentTree(n)
for i in range(n):
    tree.update(i,a[i])

max_=tree.query(1,n)
for i in range(1,n-1):
    max_=max(max_,fractions.gcd(tree.query(0,i),tree.query(i+1,n)))
max_=max(max_,tree.query(0,n-1))
print(max_)

Submission status: Accepted

Solution code:
from fractions import gcd

n=int(input())
a=list(map(int,input().split(' ')))
east=[0]*(n+1)
west=[0]*(n+1)
for i in range(1,n+1):
    east[i]=gcd(east[i-1],a[i-1])
    west[-i-1]=gcd(west[-i],a[-i])
ans=0
for k in range(1,n+1):
    tmp=gcd(east[k-1],west[k])
    if tmp>ans:
        ans=tmp
print(ans)

Submission status: Accepted

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
if n <= 2:
    print(max(a))
else:
    gcd_left = [a[0]]
    gcd_right = [a[-1]]
    for i in range(1, n):
        gcd_left.append(fractions.gcd(a[i], gcd_left[-1]))
        gcd_right.append(fractions.gcd(a[n-i-1], gcd_right[-1]))
    gcd_right = gcd_right[::-1]
    # print(gcd_left, gcd_right)
    ans = max(gcd_left[-2], gcd_right[1])
    for i in range(n-2):
        ans = max(ans, fractions.gcd(gcd_right[i+2], gcd_left[i]))
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
import fractions
def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

class segtree():#seg=segtree(A),単位元とsegfuncを指定すること
    def __init__(self,A,ide=0):#単位元とsegfuncを指定すること
        n=len(A)
        num=2**(n-1).bit_length()
        seg=[ide]*(2*num-1)
        segfunc=self.segfunc
        self.ide,self.n,self.num,self.seg = ide, n, num, seg
        for i in range(n): seg[i+num-1]=A[i]#setvalue
        for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])#build
            
    def segfunc(self,x,y):return fractions.gcd(x,y) #seg木の基本関数
        
    def update(self,k,x):#Aのk番目の要素をxに置き換える,計算量log(N)
        k += self.num-1
        seg,segfunc=self.seg,self.segfunc
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
    def query(self,p,q):#区間[p,q)の累積segfuncを求める,計算量log(N)
        if q<=p: return self.ide
        num,segfunc,seg=self.num,self.segfunc,self.seg
        p += num-1; q += num-2
        res=self.ide
        while q-p>1:
            if p&1 == 0: res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p,q = p//2, (q-1)//2
        if p == q: res = segfunc(res,seg[p])
        else: res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    seg=segtree(A)
    ans=1
    for i in range(N):
        seg.update(i,0)
        ans=max(ans,seg.query(0,N))
        seg.update(i,A[i])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import*;from fractions import*;c=lambda l:list(accumulate([0]+l,gcd));input();*a,=map(int,input().split());print(max(gcd(s,t)for s,t in zip(c(a),c(a[::-1])[-2::-1])))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import*
from fractions import*
ac = lambda l: list(accumulate([0] + l, gcd))
n, *a = map(int, open(0).read().split())
print(max(gcd(s, t) for s, t in zip(ac(a), ac(a[::-1])[::-1][1:])))

Submission status: Accepted

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

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

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

MAX =0
for i in range(n):
    if i == 0:
        MAX =max(MAX, c[-1])
    elif i ==n-1:
        MAX =max(MAX, b[-1])
    else:
        MAX =max(MAX, gcd(b[i-1], c[n-i-2]))
print(MAX)

Submission status: Accepted

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

from fractions import gcd
left = [a[0]]
right = [0]*n
right[-1] = a[-1]

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
L = [A[0]]
R = [A[-1]]

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

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

print(ans)

Submission status: Accepted

Solution code:
# ==================== gcd   最大公約数
from fractions import gcd
#from math import gcd

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

l=[0]*(n+1)
r=[0]*(n+1)

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

mimax=1
for i in range(n):
    mi=gcd(l[i],r[i+1])
    mimax=max(mi,mimax)
   
print(mimax)

Submission status: Accepted

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

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

C = [A[-1]]
for i in range(N-2,0,-1):
    C.append(gcd(C[-1], A[i]))

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

print(MAX)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

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

    def init(arr):
        # 0-index/上段の分ズラす
        for i in range(n):
            seg[i+num-1]=arr[i]
        # 上段の分を右から埋めていく
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        # 元の配列のindex→seg木上のindex
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
        
    def query(p,q):
        # 不当な区間
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        # 最下段から区間を見て更新していく
        # 見ている区間が覆う区間はその時点で見る必要はなく
        # 半分しか覆っていない区間は更新する
        # 上段に上がる際に区間外が混ざらないようにする
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

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

    # 単位元
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    # n:5~8のときnum=8なので3が入ってほしいから-1
    num =2**((n-1).bit_length())

    # セグ木初期化
    seg=[ide_ele]*2*num
    init(A)

    res = 0
    for i in range(n):
        res = max(res, segfunc(query(0, i), query(i+1, n)))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

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

    def init(arr):
        # 0-index/上段の分ズラす
        for i in range(n):
            seg[i+num-1]=arr[i]
        # 上段の分を右から埋めていく
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        # 元の配列のindex→seg木上のindex
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
        
    def query(p,q):
        # 不当な区間
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        # 最下段から区間を見て更新していく
        # 見ている区間が覆う区間はその時点で見る必要はなく
        # 半分しか覆っていない区間は更新する
        # 上段に上がる際に区間外が混ざらないようにする
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

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

    # 単位元
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    # n:5~8のときnum=8なので3が入ってほしいから-1
    num =2**((n-1).bit_length())

    # セグ木初期化
    seg=[ide_ele]*2*num
    init(A)

    res = 0
    for i in range(n):
        res = max(res, segfunc(query(0, i), query(i+1, n)))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from fractions import gcd
left = [A[0]]
right = [A[-1]]

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

ans = 1
for i in range(N):
    if i == 0:
        tmp = right[-1]
    elif i == N-1:
        tmp = left[-1]
    else:
        tmp = gcd(left[i-1], right[N-2-i])
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


class Ruiseki_lr:
    """左右からの畳み込みをそれぞれ計算する"""
    def __init__(self, array, op, e):
        self.op = op
        self.e = e

        n = len(array)
        self.left = [e] * (n + 1)
        self.right = [e] * (n + 1)
        for i in range(n):
            self.left[i + 1] = self.op(self.left[i], array[i])
        for i in reversed(range(n)):
            self.right[i] = self.op(self.right[i + 1], array[i])

    def get_left(self, p):
        """区間[0, p)の畳み込み結果を返す"""
        return self.left[p]

    def get_right(self, p):
        """区間[p, n)の畳み込み結果を返す"""
        return self.right[p]

    def fold(self, p):
        """p番目を除いた区間[0, n)の畳み込み結果を返す"""
        return self.op(self.left[p], self.right[p + 1])


n = int(input())
a = list(map(int, input().split()))
ru = Ruiseki_lr(a, gcd, 0)

ans = 0
for i in range(n):
    ans = max(gcd(ru.get_left(i), ru.get_right(i + 1)), ans)
print(ans)

Submission status: Accepted

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


class Ruiseki_lr:
    """左右からの畳み込みをそれぞれ計算する"""
    def __init__(self, array, op, e):
        self.op = op
        self.e = e

        n = len(array)
        self.left = [e] * (n + 1)
        self.right = [e] * (n + 1)
        for i in range(n):
            self.left[i + 1] = self.op(self.left[i], array[i])
        for i in reversed(range(n)):
            self.right[i] = self.op(self.right[i + 1], array[i])

    def get_left(self, p):
        """区間[0, p)の畳み込み結果を返す"""
        return self.left[p]

    def get_right(self, p):
        """区間[p, n)の畳み込み結果を返す"""
        return self.right[p]

    def fold(self, p):
        """p番目を除いた区間[0, n)の畳み込み結果を返す"""
        return self.op(self.left[p], self.right[p + 1])


n = int(input())
a = list(map(int, input().split()))
ru = Ruiseki_lr(a, gcd, 0)

ans = 0
for i in range(n):
    ans = max(ru.fold(i), ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from fractions import gcd
L=[0]
R=[]
l=a[0]
r=a[-1]
for i in range(n-1):
    l=gcd(a[i], l)
    L.append(l)
    r=gcd(a[-i-1], r)
    R.append(r)
R=R[::-1]
R.append(0)
M=[]
#print(L,R)
for i in range(n):
    m=gcd(L[i],R[i])
    M.append(m)
print(max(M))

Submission status: Accepted

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

Submission status: Accepted

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

n = int(input())
a = list(map(int,input().split()))
b = [0] * n
c = [0] * n
d = [0] * n
b[1] = a[0]
c[n-2] = a[n-1]
for i in range(2,n):
    b[i] = gcd(b[i-1],a[i-1])
    c[n-1-i] = gcd(c[n-i],a[n-i])
for i in range(n):
    d[i] = gcd(b[i],c[i])
ans = max(d)
print(ans)

Submission status: Accepted

Solution code:

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

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

L = [0]
R = [0]


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

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

print(ans)

Submission status: Accepted

Solution code:
import fractions
 
ans=0
f=[0]
g=[0]
N = int(input())
A = list(map(int,input().split()))
for i in range(N-1):
    f.append(fractions.gcd(f[i],A[i]))
    g.append(fractions.gcd(g[i],A[N-i-1]))
for i in range(N):
    ans = max(ans,fractions.gcd(f[i],g[N-i-1]))
print(ans)

Submission status: Accepted

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

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

L = [0] * (N+1)
R = [0] * (N+2)

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

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

print(ans)

Submission status: Accepted

Solution code:
import fractions
N=int(input())
A=list(map(int,input().split()))
left=[0]
right=[0]
l,r=0,0
ans=0
for i in range(N-1):
    l=fractions.gcd(l,A[i])
    r=fractions.gcd(r,A[N-1-i])
    left.append(l)
    right.append(r)
for i in range(N):
    ans=max(ans,fractions.gcd(left[i],right[N-i-1]))
print(ans)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a_list = [int(x) for x in input().split()]

l_list = [0] * n
temp = a_list[0]
for i in range(n - 1):
    if temp == 1:
        l_list[i] = 1
        continue
    temp = gcd(temp, a_list[i])
    l_list[i] = temp

r_list = [0] * n
temp = a_list[n - 1]
for i in range(n - 1, 0, -1):
    if temp == 1:
        r_list[i] = 1
        continue
    temp = gcd(temp, a_list[i])
    r_list[i] = temp

ans = 0
for i in range(n):
    if i == 0:
        temp = r_list[1]
    elif i == n - 1:
        temp = l_list[n - 2]
    else:
        temp = gcd(l_list[i - 1], r_list[i + 1])
    if temp > ans:
        ans = temp
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())
a = list(myinput())

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

r = [0]*n
for i in reversed(range(n)):
    if i==(n-1):
        r[i] = a[i]
    else:
        r[i] = gcd(r[i+1],a[i])
# print(r)

m = [0]*n
for i in range(n):
    if i==0:
        m[i] = r[1]
    elif i==(n-1):
        m[i] = l[n-2]
    else:
        m[i] = gcd(l[i-1],r[i+1])
# print(m)

ans = max(m)
print(ans)

Submission status: Accepted

Solution code:
# C - GCD on Blackboard
from collections import defaultdict

n = int(input())
a = list(int(x) for x in input().split())

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

# 左から
L = [0]*(n+1)
L[0] = 0
for i in range(n):
    L[i+1] = gcd(L[i], a[i])

# 右から
R = [0]*(n+1)
R[n-1] = a[n-1]
for i in range(1, n)[::-1]:
    R[i-1] = gcd(R[i], a[i-1]) 

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def f(x,y):
  while y!=0:
    x,y=y,x%y
  else:return x
l,r = [0],[0]
for i in range(n-1):
    l.append(f(l[-1],a[i]))
    r.append(f(r[-1],a[n-i-1]))
    
ans = 0
for i in range(n):
    ans = max(ans,f(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()))
tA=list(reversed(A))
l=[0]
r=[0]
m=[]
for i in range(N):
  tmpl = l[i]
  tmpa = A[i]
  tmpta = tA[i]
  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:
#ABC125-C GCD on Blackboard
"""
問題
リストの要素のうち一つだけ変更して、リスト全体のgcdを最大化せよ。
解法
セグ木を用いて、ある1要素を無視してその右側と左側のgcdを取る。
その時の最大値が答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#input
n = int(readline())
lst1 = list(map(int,readline().split()))

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
#####segfunc######
def segfunc(x,y):
    return  gcd(x,y)

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成

init(lst1)

ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans,query(1,n))
    elif i == n-1:
        ans = max(ans,query(0,i))
    else:
        ans = max(ans,gcd(query(0,i),query(i+1,n)))

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
N=int(input())
A=list(map(int,input().split()))

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
Asorted = sorted(A)[:: -1]


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

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

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
Asort = sorted(A)[:: -1]

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N = int(input())
A = inputlist()
from fractions import gcd
L = [0]*N
R = [0]*N
for i in range(1,N):
    L[i] = gcd(L[i-1],A[i-1])
for i in range(1,N):
    j = (N-1)-i
    R[j] = gcd(R[j+1],A[j+1])
ans = 0
for i in range(N):
    k = gcd(L[i],R[i])
    ans = max(k,ans)
print(ans)