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:
import fractions

N=int(input())

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

M=[2]
while M[-1]<N:
    M.append(M[-1]*2)

A=A+[0]*(M[-1]-len(A))
A=A[::-1]

for i in range(len(A)-1):
    A.append(fractions.gcd(A[2*i],A[2*i+1]))

A=A[::-1]

#print(A)

ans=0
for index in range(len(A)-M[-1],len(A)-M[-1]+N):
    temp=A[index+1] if index%2==1 else A[index-1]
    index=((index-1) if index%2==1 else (index-2))//2
    #print(index)
    while index!=0:
        if index%2==1:
            temp=fractions.gcd(temp,A[index+1])
            index=(index-1)//2
        else:
            temp=fractions.gcd(A[index-1],temp)
            index=(index-2)//2
        #print("temp"+str(temp))
    ans=max(temp,ans)
    #print("=======================")
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
M=[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])
for i in range(N):
  if i == 0:
    M[i]=R[i+1]
  elif i == N-1:
    M[i]=L[i-1]
  else:
    M[i]=gcd(L[i-1],R[i+1])
print(max(M))

Submission status: Accepted

Solution code:
import fractions as f

n = int(input())
a = [int(_) for _ in input().split()]

left = [0] * (n+1)
left[0] = 0
for i in range(1, n+1):
    left[i] = f.gcd(left[i-1], a[i-1])

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

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

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 for _ in range(n)]
R = [0 for _ in range(n)]
L[0] = A[0]
R[-1] = A[-1]

for i in range(1, n):
    L[i] = gcd(L[i-1], A[i])
    R[n - i - 1] = gcd(R[n - i], A[n - i - 1])
ans = 1
for i in range(n):
    if i == 0:
        ans = R[i + 1]
    elif i == n-1:
        ans = max(ans, L[i-1])
    else:
        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()))
ans = 0
l = [0]*(n+1)
r = [0]*(n+1)
for i in range(n):
    l[i+1] =  fractions.gcd(l[i],a[i])
for i in range(n-1,0,-1):
    r[i] =  fractions.gcd(r[i+1],a[i])
for i in range(n):
    L = l[i]
    R = r[i+1]
    ans = max(ans,fractions.gcd(L,R))
print(ans)

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""

n=int(input())
a=[int(i) for i in input().split()]
a.sort()

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)
    divisors.sort()
    return divisors

l=make_divisors(a[0])
l2=make_divisors(a[1])
le=len(l)
le2=len(l2)         
an=[0]*le
an2=[0]*le2
for i in range(n):
    for j in range(le):
        if a[i]%l[j]==0:
            an[j]+=1
    for j in range(le2):
        if a[i]%l2[j]==0:
            an2[j]+=1
ans=1
ans2=1
for i in range(le):
    if an[i]>=n-1:
        ans=max(ans,l[i])
for i in range(le2):
    if an2[i]>=n-1:
        ans2=max(ans2,l2[i])

print(max(ans,ans2))


"""))

Submission status: Accepted

Solution code:


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

from fractions import gcd
def lcm(x, y):
    return x * y // gcd(x, y)

gcds = [0] * N
gcds[0] = A[0]
rev_gcds = [0] * N
rev_gcds[-1] = A[-1]

for i in range(1, N):
    gcds[i] = gcd(A[i], gcds[i-1])
    rev_gcds[N-1-i] = gcd(A[N-1-i],  rev_gcds[N-i])

ans = 1
for i in range(N):
    if i == 0:
        tmp = rev_gcds[i+1]
    elif i == N-1:
        tmp = gcds[i-1]
    else:
        tmp = gcd(gcds[i-1], rev_gcds[i+1])
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import fractions
import itertools
from functools import reduce

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

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

    def pleaceAC():
        left = list(accumulate([0]+A, gcd))
        right = list(accumulate(reversed(A+[0]), gcd))
        for i in range(N):
            yield gcd(left[i], right[~(i+1)])

    print(max(pleaceAC()))


main()

Submission status: Accepted

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

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

# left[p] := 区間[0, p)までの最大公約数
for i in range(N):
    left[i+1] = gcd(left[i], A[i])

# right[p] := 区間[p, N)までの最大公約数
for i in reversed(range(N)):
    right[i] = gcd(right[i+1], A[i])

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

Submission status: Accepted

Solution code:
import fractions
#from functools import reduce
N,*a=map(int,open(0).read().split())
L=[]
L_base=a[0]
b=a[:]
b.reverse()
R=[]
R_base=b[0]
for i in range(N-1):
    L_base=fractions.gcd(L_base,a[i])
    L.append(L_base)
    R_base=fractions.gcd(R_base,b[i])
    R.append(R_base)
LR=[R[-1]]
for i in range(N-2):
    LR.append(fractions.gcd(L[i],R[-2-i]))
LR.append(L[-1])
print(max(LR))

Submission status: Accepted

Solution code:
from fractions import gcd

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

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.ide, self.func = ide, func
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def get(self, i):
        return self.data[self.n + i]

s = SegmentTree(n, lambda x, y: gcd(x, y), 0)
s.build(a)
ans = 0
for i in range(n):
    ans = max(ans, gcd(s.query(0, i), s.query(i+1, n)))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(1000000)

def main():

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

def main():
    @lru_cache(maxsize=None)
    def gcd(a, b):
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def main():

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

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def main():

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

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def main():

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

    N, *A = map(int, sys.stdin.read().split())
    L = [0] * (N + 2)
    R = [0] * (N + 2)
    for i in range(N):
        L[i + 2] = gcd(L[i + 1], A[i])
        R[-i - 2] = gcd(R[-i - 1], A[-i - 1])

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

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


N, *A = map(int, sys.stdin.read().split())
L = [0] * (N + 2)
R = [0] * (N + 2)
for i in range(N):
    L[i + 2] = gcd(L[i + 1], A[i])
    R[-i - 2] = gcd(R[-i - 1], A[-i - 1])

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

left = [0] * (n + 1)
right = [0] * (n + 1)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
def gcdf(a):
    a.sort()
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

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

if n==2:
    print(max(a))
elif n<2**8:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n/100)
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
#        print(mi,gcdf(am),len(am),gcdf(rgcd1))
        for i in range(len(am)):
            acpy=list(am)
#            del acpy[i]
#            acpy.append(gcdrg1)
            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)

Submission status: Accepted

Solution code:
def gcdf(a):
    a.sort()
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

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

if n==2:
    print(max(a))
elif n<2**8:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(2/3))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
#        print(mi,gcdf(am),len(am),gcdf(rgcd1))
        for i in range(len(am)):
            acpy=list(am)
#            del acpy[i]
#            acpy.append(gcdrg1)
            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
配列の値を書き換える＝＝削除すると同義
削除する値を一つ決め、それを区切りに右と左の配列に分け、GCDを求める
更に左右のGCDをマージしGCDを求め、最大値が答え
"""
import functools, fractions

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] = fractions.gcd(L[i], A[i])

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

Submission status: Accepted

Solution code:
import fractions
import sys

def chmax(a, b):
  if (a > b):
    return a

  return b

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

if N == 2:
  if li[0] > li[1]:
    print(li[0])
  else:
    print(li[1])
  sys.exit()

left = []
right = []

for index, i in enumerate(li):
  if index == 0:
    left.append(i)
    continue

  left.append(fractions.gcd(left[index-1], i))

for index, i in enumerate(reversed(li)):
  if index == 0:
    right.append(i)
    continue

  right.append(fractions.gcd(right[index-1], i))

ans = 0

for n in range(N):
  if n == 0:
    ans = chmax(ans, right[-2])
    continue
  
  if n == N-1:
    ans = chmax(ans, left[-2])
    continue

  ans = chmax(ans, fractions.gcd(left[n-1], right[N-n-2]))

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

for i in reversed(range(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:
# import math
n = int(input())
s = list(map(int,input().split()))

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

lm = [0] *(n+1)
rm = [0] *(n+1)
for i in range(1,n):
    lm[i+1] = gcd(lm[i],s[i-1])
for i in range(n-1,0,-1):
    rm[i] = gcd(rm[i+1],s[i])

ans = float('-inf')
for i in range(1,n+1):
    ans = max(ans,gcd(lm[i],rm[i]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
right,left=[a[n-1]],[a[0]]
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=max(left[n-2],right[n-2])
for i in range(1,n-1):
  ans=max(ans,gcd(left[i-1],right[n-i-2]))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    A = Scanner.map_int()
    L = [0] * N
    R = [0] * N
    for i in range(N-1):
        L[i+1] = Math.gcd(L[i], A[i])
    for i in reversed(range(N-1)):
        R[i] = Math.gcd(R[i+1], A[i+1])
    M = [0] * N
    for i in range(N):
        M[i] = Math.gcd(L[i], R[i])
    print(max(M))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions
#####segfunc######
def segfunc(x,y):
    return fractions.gcd(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        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):
    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
#input
n = int(input())
a = list(map(int, input().split()))

#####単位元######
ide_ele = 0
num =2**(n-1).bit_length() 
seg=[ide_ele]*(2*num - 1)
init(a)
ans = 0
for i in range(n):
    ans = max(ans, fractions.gcd(query(0,i), query(i+1, n)))
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline
    #配列’init_val’で初期化
    def init(init_val):
        #set_val
        for i in range(n):
            seg[i+num-1]=init_val[i]    
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=gcd(seg[2*i+1],seg[2*i+2]) 
    #init_val[k]をxに変更
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = gcd(seg[k*2+1],seg[k*2+2])
    #[p,q)について"segfunc"したものを返す   
    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 = gcd(res,seg[p])
            if q&1 == 1:
                res = gcd(res,seg[q])
                q -= 1
            p = 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 = list(map(int,input().split()))
    #単位元
    #最小値のセグ木　float('inf')
    #和 or gcdのセグ木　0
    #積のセグ木　1
    ide_ele = 0
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*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:
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
left = [0] * (n + 1)
right = [0] * (n + 1)
middle = [0] * (n + 1)

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

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

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

print(max(middle))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

ll, lr = [0]*n, [0]*n
ll[0], lr[n-1] = a[0], a[n-1]
for i in range(1,n):
  ll[i] = gcd(ll[i-1], a[i])
  lr[n-i-1] = gcd(lr[n-i], a[n-i-1])

print(max(ll[n-2], lr[1], *[gcd(l,r) for l,r in zip(ll[:n-2], lr[2:])]))

Submission status: Accepted

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

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

ll, lr = [0]*n, [0]*n
ll[0], lr[n-1] = a[0], a[n-1]
for i in range(1,n):
  ll[i] = gcd(ll[i-1], a[i])
  lr[n-i-1] = gcd(lr[n-i], a[n-i-1])

print(max(ll[n-2], lr[1], *[gcd(l,r) for l,r in zip(ll[:n-2], lr[2:])]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
L = [0]
R = [0]
import fractions
def GCD(a,b):
    if a*b != 0:
        return fractions.gcd(a,b)
    else:
        return max(a,b)
for i in range(N-1):
    x = A[i]
    y = A[-i-1]
    L.append(GCD(L[i],x))
    R.append(GCD(R[i],y))
ans = 0
for i in range(N):
    x = L[i]
    y = R[-i-1]
    ans = max(GCD(x,y),ans)
print(ans)

Submission status: Accepted

Solution code:
def gcd(xxx,yyy):
    if xxx<yyy:
        xxx,yyy=yyy,xxx
    if yyy==0:
        return xxx
    else:
        return gcd(yyy,xxx%yyy)

def seg_tree_update(n,x):
    ind=2**m-1+n
    tree[ind]=x
    ind=(ind-1)//2
    while ind>=0:
        tree[ind]=gcd(tree[2*ind+1],tree[2*ind+2])
        ind=(ind-1)//2

def seg_tree_find_gcd(L,R):
    qqq=A[L]
    L,R=2**m-1+L,2**m-1+R
    while L<R:
        if L%2==0:
            qqq=gcd(qqq,tree[L])
        if R%2==1:
            qqq=gcd(qqq,tree[R])
        L//=2
        R=R//2-1
        
    if L==R:
        qqq=gcd(qqq,tree[L])
    return qqq

N=int(input())
A=list(map(int,input().split()))
inf=float("inf")
m=0
while pow(2,m)<N:
    m+=1
tree=[0]*(pow(2,m+1)-1)

for i in range(N):
    seg_tree_update(i,A[i])
    
ans=max(seg_tree_find_gcd(1,N-1),seg_tree_find_gcd(0,N-2))
for i in range(1,N-1):
    ddd=gcd(seg_tree_find_gcd(0,i-1),seg_tree_find_gcd(i+1,N-1))
    ans=max(ans,ddd)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = sorted(map(int, input().split()))

    if N == 2:
        print(max(A))
        exit()

    A0, A1, A2 = A[:3]
    A_min_sq = int(math.sqrt(A2)) + 1
    
    gcd_ls = set()
    for i in range(A_min_sq, 0, -1):
        div = set()
        c = 0
        if A0 % i == 0:
            div.add(A0 // i)
            c += 1
        if A1 % i == 0:
            div.add(A1 // i)
            c += 1
        if A2 % i == 0:
            div.add(A2 // i)
            c += 1
        if c < 2:
            continue
        gcd_ls.add(i)

        for j in div:
            if A0 % j == 0 and (A1 % j == 0 or A2 % j == 0):
                gcd_ls.add(j)
            elif A1 % j == 0 and A2 % j == 0:
                gcd_ls.add(j)
    gcd_ls = sorted(gcd_ls, reverse=True)

    for i in gcd_ls:
        wa = False
        for j in A:
            if j % i != 0:
                if wa:
                    break
                wa = True
        else:
            print(i)
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

GCD = [1] * n
GCD[0], GCD[-1] = GCD_right[1], GCD_left[-2]
for i in range(1, n - 1):
    GCD[i] = gcd(GCD_left[i - 1], GCD_right[i + 1])

print(max(GCD))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def gcd(a, b):
# 例外処理
    if a == 0:
        return b
    if b == 0:
        return a

    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b

def main():
    N = INT()
    A = LIST()
    A.insert(0, 0)
    A.append(0)
    L = [0] * (N + 2)
    R = [0] * (N + 2)
    L[0] = 0
    # R[]
    R[N + 1] = 0
    for i in range(0, N + 1):
        L[i + 1] = gcd(L[i], A[i])
    for i in range(N, -1, -1):
        R[i] = gcd(R[i + 1], A[i])

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

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

def main():
    l_gcd = [None] * n
    r_gcd = [None] * n
    l_gcd[1] = a[0]
    r_gcd[n-2] = a[-1]

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

    res = max(r_gcd[0], l_gcd[n-1])
    for i in range(1, n-1):
        res = max(res, gcd(l_gcd[i], r_gcd[i]))
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
from fractions import gcd
l,r = [0]*(n+1),[0]*(n+1)
for i in range(n):
    l[i+1] = gcd(l[i],a[i])
for i in range(n,0,-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:
n=int(input())
al=list(map(int,input().split()))

import fractions
ans=0
left=[0]
for i in range(1,n):
    ans=fractions.gcd(ans,al[i-1])
    left.append(ans)
#print(left)
right=[0 for i in range(n+1)]
for i in range(1,n+1):
    right[n-i]=fractions.gcd(right[n-i+1],al[n-i])
#print(right)

ans=0

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
A = inpl()

if len(A) <= 2:
    ans = max(A)
else:
    gcd_left = [A[0]]
    gcd_right = [A[N-1]] 
    for i in range(N-1):
        gcd_left.append(gcd(gcd_left[i],A[i+1]))
        gcd_right.append(gcd(gcd_right[i],A[N-2-i]))
    p_ans1 = max([gcd(gcd_left[i], gcd_right[N-i-3]) for i in range(N-2)])
    p_ans2 = gcd_left[N-2]
    p_ans3 = gcd_right[N-2]
    ans = max(p_ans1, p_ans2, p_ans3)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
def gcd(m, n):
  while n != 0:
    m, n = n, m % n
  return m
gl = [A[0]]
gr = [A[N-1]]
x, y = A[0], A[N-1]
for i in range(1, N):
  x = gcd(x, A[i])
  gl.append(x)
  y = gcd(y, A[N-i-1])
  gr.append(y)
gg = [gr[N-2]]
for i in range(1, N-1):
  gg.append(gcd(gl[i-1], gr[N-i-2]))
gg.append(gl[N-2])
if N != 2:
  print(max(gg))
else:
  print(max(A[0], A[1]))

Submission status: Accepted

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

GCDF, GCDB = [0]*N, [0]*N
GCDF[1],GCDB[-2] = A[0], A[N-1]
for i in range(2, N):
    GCDF[i] = gcd(GCDF[i-1],A[i-1])
    GCDB[-(i+1)] = gcd(GCDB[-i], A[-i])
GCDm = [0]*N
GCDm[0] = GCDB[0]
GCDm[N-1] = GCDF[N-1]
for i in range(1, N-1):
    GCDm[i] = gcd(GCDF[i],GCDB[i])
ans = max(GCDm)
print(ans)