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 copy

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

N = int(input())
A = list(map(int, input().split()))
F = copy.copy(A)
B = copy.copy(A)
for i in range(N - 1):
  F[i + 1] = gcd(F[i + 1], F[i])
for i in range(N - 2, -1, -1):
  B[i] = gcd(B[i], B[i + 1])
ans = max(F[N-2], B[1])
for i in range(1, N - 1):
  ans = max(ans, gcd(F[i-1], B[i+1]))
print(ans)

Submission status: Accepted

Solution code:
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")

import fractions
from functools import reduce

def gcd(*numbers):
	return reduce(fractions.gcd, numbers)
	#return reduce(math.gcd, numbers)

def gcd_list(numbers):
	return reduce(fractions.gcd, numbers)
	#return reduce(math.gcd, numbers)



N=int(input())
A=[int(i) for i in input().split()]	# 1 2 3 4 5 ...

p("N", N)
p("A", A)


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


L=[0]*(N)		#左側用
R=[0]*(N)		#右側用



L[0]=A[0]		#初項は、Aの左端
p("L", L)
for i in range(1,N):
	L[i]=gcd(L[i-1],A[i])
	p(i, L[i])
p("L", L)



R[N-1]=A[N-1]		#初項は、Aの右端
p("R", R)
for i in range(N-2,-1,-1):
	R[i]=gcd(R[i+1],A[i])
	p(i, R[i+1])
p("R", R)



M=[0]*N
for i in range(1,N-1):
	M[i]=gcd(L[i-1],R[i+1])		#A[i]を起点に、左側(L[i-1])、右側(R[i+1])
p("M", M)

M[0]=R[1]				#左端は、右側のみ
M[N-1]=L[N-2]		#右端は、左側のみ

p("M", M)

print( max(M) )

Submission status: Accepted

Solution code:
import numpy as np
import fractions

N = int(input())
A = [int(i) for i in input().split()]


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

gcd_right = gcd_right[::-1]

value = []
for i in range(N):
    value.append(fractions.gcd(gcd_left[i], gcd_right[i+1]))

print(max(value))

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline


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


N = int(input())
A = list(map(int, input().split()))
# A, B, T = map(int, input().split())
# S = input()

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

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

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

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

print(ans)

Submission status: Accepted

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

def gcd(n, m):
    if n == 0 or m == 0:
        return max(n, m)
    while n % m != 0:
        n, m = m, n % m
    return m

l = [0]
for i in range(N-1):
    l.append(gcd(l[i], A[i]))
r = [0]
for i in range(1, N):
    r.append(gcd(r[i-1], A[N-i]))
m = [gcd(l[i], r[N-1-i]) for i in range(N)]
print(max(m))

Submission status: Accepted

Solution code:

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


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

    index = list(range(N))
    forward = index.copy()
    forward[0] = 0
    for i in index[:-1]:
        forward[i+1] = gcd(A[i], forward[i])

    backward = index.copy()
    backward.append(0)
    for i in reversed(index):
        backward[i] = gcd(A[i], backward[i+1])
    # print(forward)
    # print(backward)
    M = [gcd(f, b) for f, b in zip(forward, backward[1:])]
    # print(M)
    print(max(M))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import *
from math import *

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    gcd_left = [a[0]]
    gcd_right = [a[-1]]
    for i in range(n-1):
        gcd_left += [gcd(gcd_left[-1], a[i+1])]
        gcd_right += [gcd(gcd_right[-1], a[-i-2])]
    gcd_right = gcd_right[::-1]
    ans = 1
    for i in range(n):
        if i == 0:
            ans = max(ans, gcd_right[i+1])
        elif i == n-1:
            ans = max(ans, gcd_left[i-1])
        else:
            ans = max(ans, gcd(gcd_left[i-1], gcd_right[i+1]))

    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import sqrt
inpl = lambda: list(map(int,input().split()))
 
def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P
 
def factorize(n, P=None):
    if P is None:
        P = primes(int(sqrt(n))+1)
    factor = []
    power = []
    for p in P:
        if p * p > n:
            break
        elif n % p == 0:
            k = 0
            while n % p == 0:
                n //= p
                k += 1
            factor.append(p)
            power.append(k)
    if n > 1:
        factor.append(n)
        power.append(1)
    return factor, power
 
class Counter:
    def __init__(self, start=0):
        self.index = start-1
 
    def __call__(self):
        self.index += 1
        return self.index
 
N = int(input())
A = inpl()
 
P_MAX = 32000
infty = 100
P = primes(P_MAX)
 
np = defaultdict(Counter())
Np = 0
 
lowest_powers = []
bottle_necks = []
primelist = []
all_factors = set()
for n in range(N):
    primes, powers = factorize(A[n],P)
    pp = [0]*Np
    for i in range(len(primes)):
        k = np[primes[i]]
        if k >= Np:
            Np += 1
            pp.append(powers[i])
            primelist.append(primes[i])
            if n > 1:
                lowest_powers.append([0,0])
                bottle_necks.append(-1)
            elif n == 1:
                lowest_powers.append([0,infty])
                bottle_necks.append(0)
            else:
                lowest_powers.append([infty,infty])
                bottle_necks.append(-1)
        else:
            pp[k] = powers[i]
    for k in range(Np):
        lowest = lowest_powers[k]
        if pp[k] == lowest[0]:
            lowest[1] = lowest[0]
            bottle_necks[k] = -1
        elif pp[k] < lowest[0]:
            lowest[1] = lowest[0]
            lowest[0] = pp[k]
            bottle_necks[k] = n
        elif pp[k] < lowest[1]:
            lowest[1] = pp[k]
 
bottleneck_factors = [ [] for _ in range(N) ]
for k in range(Np):
    n = bottle_necks[k]
    if n >= 0:
        lowest = lowest_powers[k]
        bottleneck_factors[n].append([primelist[k],lowest[1]-lowest[0]])
best_n = -1
largest_f = 1
for n in range(N):
    f = 1
    for pp in bottleneck_factors[n]:
        f *= pp[0]**pp[1]
    if f > largest_f:
        largest_f = f
        best_n = n
 
ans = 1
pn = [ s[0] for s in bottleneck_factors[best_n] ]
for k in range(Np):
    p = primelist[k]
    if bottle_necks[k] == best_n:
        ans *= p**lowest_powers[k][1]
    else:
        ans *= p**lowest_powers[k][0]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    def gcd(a,b):
        if b == 0:
            return a
        else:
            return gcd(b,a%b)
    def query(p,q):
        p += num
        q += num
        res=0
        while p<q:
            if q&1:
                q-=1
                res=gcd(res,data[q-1])
            if p&1:
                res=gcd(res,data[p-1])
                p+=1
            p = p//2
            q = q//2
        return res

    n = int(input())
    a = tuple(map(int,input().split()))
    num =2**(n-1).bit_length()
    data=[0]*2*num

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

    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:
import fractions as f,itertools as i;n,*a=map(int,open(0).read().split());b,c=[list(i.accumulate([0]+t,f.gcd))for t in(a,a[::-1])];print(max(f.gcd(b[i],c[-i-2])for i in range(n)))

Submission status: Accepted

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

N = ni()
A = na()

def gcd(x,y):
    r = x%y
    while(r!=0):
        x,y = y,r
        r = x%y
    return y
L = []
R = []
l = A[0]
r = A[-1]
for i in range(N-1):
    l = gcd(l,A[i])
    L.append(l)
for i in range(N-1,0,-1):
    r = gcd(r,A[i])
    R.append(r)
M = 0
M = max(R[-1],L[-1])
for i in range(N-2):
    M = max(M,gcd(L[i],R[-(i+2)]))
print(M)

Submission status: Accepted

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

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


def main():
    n = int(input())
    A = list(map(int, input().split()))
    gcdA = [0]*n
    gcdB = [0]*n
    gcdA[0] = A[0]
    gcdB[n-1] = A[n-1]
    for i in range(1, n):
        gcdA[i] = gcd(A[i], gcdA[i-1])
        gcdB[n-i-1] = gcd(A[n-i-1], gcdB[n-i])
    ans = max(gcdA[n-2], gcdB[1])
    for i in range(1, n-1):
        ans = max(ans, gcd(gcdA[i-1], gcdB[i+1]))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 6))

n = int(input())
alist = list(sorted(map(int, input().split())))

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

l1 = [gcd(0, alist[0])]
l2 = [gcd(alist[-1], 0)]
if n == 2:
  print(max(alist))
else:
  for a in alist[1:]:
    l1.append(gcd(a, l1[-1]))
  for a in alist[::-1][1:]:
    if l2[-1] > a:
      l2.append(gcd(l2[-1], a))
    else:
      l2.append(gcd(a, l2[-1]))
  l2 = l2[::-1]
  maxl = l2[1]
  for i in range(n - 2):
    gcda = gcd(max(l1[i], l2[i+2]), min(l1[i], l2[i+2]))
    if gcda > maxl:
      maxl = gcda
  print(max(maxl, l1[-2]))

Submission status: Accepted

Solution code:
N = int(input())
rawA = list(map(int, input().split()))
A = [rawA[0],] + rawA + [rawA[N-1],]
#要素数A+2。A[0]とA[N+1]はcumsum計算用

def gcd(a, b):
  if b > a: a,b = b,a
  #これでa >= bになったので、互除法適用可
  if a % b == 0: return b
  else: return gcd(b, a % b)
  
#cfl: cumsum from left
#[0]~[N-1] 
#cfl[0]は計算不要（gcdでなくgd(A0)=A0でいいから）
cfl = []
cfl.append(A[1]) #A[1]位置のcflはcfl[0]=A[1]
for i in range(2, N): #残りの2~N-1位置について
#あわせて1~N-1位置をcflに格納した
#2~N-1はAの添字なので注意
  cfl.append(gcd(cfl[i-2], A[i]))
  
#cfr: cumsum from right
#[0]~[N-1] 右端は0, 左端はN-1で取り出す
cfr = []
cfr.append(A[N]) #A[N]位置のcfrはcfr[0]=A[N]
for i in range(N-1, 1, -1): #残りの2~N-1位置について
#あわせて2~N位置をcfrに格納した
#N-1~2について。やはりAの添字なので注意
  cfr.append(gcd(A[i], cfr[abs(i-N+1)]))


#maxをansにメモしながら取り除くべき箇所を探す
ans = max(cfl[-1], cfr[-1]) #端っこを取り除いた場合
for nowcfl, nowcfr in zip(cfl[0:-1],cfr[::-1][1:]):
#N=2(cfl, cfrの要素数1)のときは0と-1が一致する
#→よって実行されないので問題なし
  ans = max(ans, gcd(nowcfl, nowcfr))

print(ans)

Submission status: Accepted

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

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

l = [0]*N
r = [0]*N

l[0] = A[0]
r[-1] = A[-1]

for x in range(1,N):
    y = N - 1 - x
    l[x] = gcd(A[x],l[x-1])
    r[y] = gcd(A[y],r[y+1])

l.insert(0,0)
l.append(0)
r.insert(0,0)
r.append(0)

o = 1

for x in range(N):
    o = max(o,gcd(l[x],r[x+2]))

print(o)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

N = int(input())

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


if len(A) < 3:
    print(max(A))
    sys.exit()


left_side = [0 for _ in range(N)]
left_side[0] = A[0]

right_side = [0 for _ in range(N)]
right_side[-1] = A[-1]



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

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


max_gcd = 1 

# left 
max_gcd = max(max_gcd, right_side[1])
# right
max_gcd = max(max_gcd, left_side[-2])

for i in range(1, N -1 ):
    left = left_side[i - 1]
    right = right_side[i + 1]
    max_gcd = max(max_gcd, gcd(left, right))




print(max_gcd)

Submission status: Accepted

Solution code:
from fractions import gcd
def main():
    n = int(input())
    a = list(map(int, input().split()))
    left = [0]
    right = [0]
    for l in a[:-1]:
        g = gcd(left[-1], l)
        left.append(g)
    for r in a[n:0:-1]:
        g = gcd(right[-1], r)
        right.append(g)
    right.reverse()
    m = 0
    for i in range(n):
        m = max(m, gcd(left[i], right[i]))
    print(m)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
X = [0] * N
Y = [0] * N
sum_gcd = []
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

x = A[0]
y = A[N-1]
X[0] = x
Y[N-1] = y
for i in range(1, N):
    x = gcd(x, A[i])
    y = gcd(y, A[len(A)-i-1])
    X[i] = x
    Y[N-i-1] = y

sum_gcd.append(max(Y[1], X[N-2]))
for i in range(N-2):    
    sum_gcd.append(gcd(X[i], Y[i+2]))

print(max(sum_gcd))

Submission status: Accepted

Solution code:
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)


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

#取り除く候補
del_list = [0]

#a[0]~a[i]までのgcd
g = a[0]
for i,x in enumerate(a):
    p = gcd(g,x)
    if p<g:
        g = p
        del_list.append(i)

res = -1
for ind in del_list:
    kouho = -1
    for i,x in enumerate(a):
        if i==ind:
            continue
        if kouho < 0:
            kouho = x
            continue
        kouho = gcd(kouho,x)
    res = max(res,kouho)
print(res)

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 i in range(N)]
R = [0 for i in range(N)]
T = [0 for i in range(N)]
 
for i in range(N):
    if i == 0:
        L[i] = 0
    else:
        L[i] = gcd(L[i-1], A[i-1])
for i in range(N-1, -1, -1):
    if i == N-1:
        R[i] = 0
    else:
        R[i] = gcd(R[i+1], A[i+1])
for i in range(N):
    T[i] = gcd(L[i], R[i])
 
print(max(T))

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
curr1, curr2 = [0], [0]
for i in range(N):
  curr1 += [gcd(A[i],curr1[-1])]
  curr2 += [gcd(A[N-1-i],curr2[-1])]

if N ==2:
  print(max(A[0],A[1]))
else:
  ans = []
  for i in range(N):
    ans += [gcd(curr1[i],curr2[N-1-i])]
    
  print(max(ans))

Submission status: Accepted

Solution code:
import fractions

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

for x in range(1,N):
    right = fractions.gcd(right, A[-x-1])
    left = fractions.gcd(left, A[x])
    R.append(right)
    L.append(left)

answer = max(R[N-2], L[N-2])

for x in range(N-2):
    test = fractions.gcd(R[x], L[-x-3])
    answer = max(answer, test)

print(answer)

Submission status: Accepted

Solution code:
from fractions import gcd

def main():
    n = int(input())
    a = list(map(int, input().split()))
    left = [0]
    right = [0]
    for i in range(1, n):
        g = gcd(left[-1], a[i - 1])
        left.append(g)
    for i in range(n - 2, -1, -1):
        g = gcd(right[-1], a[i + 1])
        right.append(g)
    right.reverse()
    m = 0
    for i in range(0, n):
        m = max(m, gcd(left[i], right[i]))
    print(m)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

w_min = A[1]

for i in range(w_min,0,-1):
    count = 0
    for j in A:
        if j%i != 0:
            count = count + 1
            if count > 1:
                break
    if count < 2:
        print(i)
        break

Submission status: Accepted

Solution code:
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

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

#b[i]:a[0]~a[i]までのgcd,c[i]:a[i]~a[-1]までのgcd
b = [0]*n
c = [0]*n
for i in range(n):
    if i == 0:
        b[0] = a[0]
        c[-1] = a[-1]
        continue
    b[i]=gcd(b[i-1],a[i])
    c[n-1-i]=gcd(c[n-i],a[n-1-i])

res = max(b[n-2],c[1])
for i in range(1,n-1):
    res = max(res,gcd(b[i-1],c[i+1]))
print(res)

Submission status: Accepted

Solution code:
#coding:utf-8
import fractions

def main():
    N=int(input())
    num=list(map(int,input().split()))
    gcd=0
    gcd_list_front=[]
    gcd_list_back=[]
    gcd_list_front.append(num[0])
    gcd_list_back.append(num[-1])

    for  i in range(1,N-1):
        gcd_list_front.append(fractions.gcd(gcd_list_front[i-1],num[i]))
        gcd_list_back.append(fractions.gcd(gcd_list_back[i-1],num[-i-1]))
    gcd_list_back.reverse()

    gcd=max(gcd_list_back[0],gcd_list_front[-1])
    for i in range(0,N-2):
       temp_gcd=fractions.gcd(gcd_list_front[i],gcd_list_back[i+1])
       if temp_gcd>gcd:
           gcd=temp_gcd
    print(gcd)


if  __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import fractions

N = int(input())
A = np.array([int(i) for i in (input()).split(" ")])

maxA = np.max(A)


if(maxA == np.min(A)):
    print(maxA)
elif(N==2):
    print(maxA)
else:
    R=np.zeros((N))
    L=np.zeros((N))
    M=np.zeros((N))

    L[0] = 0
    R[N-1] = 0
    for i in range(1,N):
        #0~i-1番目までの最大公約数
        L[i] = fractions.gcd(A[i-1],L[i-1])
        #i~N番
        R[N-1-i] = fractions.gcd(A[N-1-i+1],R[N-1-i+1])

    M[0] = R[0]
    M[-1] = L[-1]
    for i in range(1,N-1):
        M[i] = fractions.gcd(L[i],R[i])

    print("{}".format(int(np.max(M))))

Submission status: Accepted

Solution code:
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


N = int(input())
A = sorted([int(x) for x in input().split()])

divisors = sorted(set(make_divisors(A[0]) + make_divisors(A[1])), reverse=True)
ans = 1

for divisor in divisors:
    indivisible_count = 0
    for i in range(N):
        if A[i] % divisor != 0:
            indivisible_count += 1

    if indivisible_count <= 1:
        ans = divisor
        break

print(ans)

Submission status: Accepted

Solution code:
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


N = int(input())
A = sorted([int(x) for x in input().split()])

ans = 1
divisors = make_divisors(A[0]) + make_divisors(A[1])
divisors = sorted(set(divisors), reverse=True)

for divisor in divisors:
    indivisible_count = 0
    for i in range(N):
        if A[i] % divisor != 0:
            indivisible_count += 1

    if indivisible_count <= 1:
        ans = divisor
        break

print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
try:
    from math import gcd
except:
    from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
AL = [0] * N  # 左からGCD
AR = [0] * N  # 右からGCD
for i in range(1, N):
    AR[i] = gcd(AR[i-1], A[i-1])
for i in range(N-1)[::-1]:
    AL[i] = gcd(AL[i+1], A[i+1])
A_list = [gcd(AL[i], AR[i]) for i in range(N)]
print(max(A_list))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 28 15:46:33 2019

@author: Yamazaki Kenichi
"""

N = int(input())
A = list(map(int,input().split()))
 
def eg(x,y):
    if y == 0:
        return x
    x, y = y, x%y
    return eg(x,y)

L, R = [0 for i in range(N)],[0 for i in range(N)]
L[0], R[N-1] = A[0], A[N-1]
for i in range(1,N):
    L[i] = eg(L[i-1], A[i])
    R[N-1-i] = eg(R[N-i], A[N-1-i])
ans = [0 for i in range(N)]
for i in range(N):
    if i == 0:
        ans[i] = R[i+1]
    elif i == N-1:
        ans[i] = L[i-1]
    else:
        ans[i] = eg(L[i-1],R[i+1])

print(max(ans))

Submission status: Accepted

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


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

def solve(N: int, A: "List[int]"):
    l = [0] * (N+2)
    r = [0] * (N+2)
    l[1] = A[0]
    r[N] = A[N-1]
    for i in range(2, N+1):
        l[i] = gcd(l[i-1], A[i-1])
    for i in reversed(range(1, N)):
        r[i] = gcd(r[i+1], A[i-1])
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(l[i], r[i+2]))
    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, _n, func, inf=float('inf')):
        '''
        _n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(_n-1).bit_length()
        self.inf = inf
        self.data = [inf]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のminを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.inf
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


N = int(input())
L = list(map(int, input().split()))
T = SegmentTree(N, gcd, 0)
for i, l in enumerate(L):
    T.set(i, l)
T.build()

ans = 0
for i in range(N):
    l = i
    r = i+1
    ans = max(ans, gcd(T.query(0, l), T.query(r, N)))
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if b==0:
    return a
  else:
    return gcd(b,a%b)
  
n=int(input())
arr=list(map(int,input().split()))
lgcd=[arr[0]]
rgcd=[arr[-1]]

if n==2:
  print(max(arr[0],arr[1]))
elif n==3:
  print(max(gcd(arr[0],arr[1]),gcd(arr[1],arr[2]),gcd(arr[2],arr[0])))
else:
  tmp=arr[0]
  for i in range(1,n-1):
    lgcd.append(gcd(tmp,arr[i]))
    tmp=gcd(tmp,arr[i])
  tmp=arr[-1]
  for i in range(n-2,0,-1):
    rgcd.append(gcd(tmp,arr[i]))
    tmp=gcd(tmp,arr[i])
  rgcd=rgcd[::-1]
  ans=0
  for i in range(n):
    if i==0:
      tmp=rgcd[0]
    elif i==n-1:
      tmp=lgcd[-1]
    else:
      tmp=gcd(rgcd[i],lgcd[i-1])
    if tmp>ans:
      ans=tmp
  print(ans)

Submission status: Accepted

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


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

l = [0]*len(a)
r = [0]*len(a)

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

ans = [0]*n

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

print(max(ans))

Submission status: Accepted

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

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

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 range(n - 1, -1, -1):
    right[i] = gcd(right[i + 1], a[i])

k = 0

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

    if g > k:
        k = g

print(k)

Submission status: Accepted

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

import sys
import copy

sys.setrecursionlimit(1000000)


# input = sys.stdin.readline

# ~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~

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


N = int(input())

A = [int(x) for x in input().split()]
B = list(reversed(A))

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

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

for i in range(N):
    R[i + 1] = gcd(R[i], B[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:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    RMQ　の実装
    '''

    def __init__(self, n, inf=float('inf')):
        '''
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.inf = inf
        self.data = [inf]*(2*self.n)

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        for k in reversed(range(self.n-1)):
            self.data[k] = gcd(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = gcd(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のminを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.inf
        while L < R:
            if R & 1:
                R -= 1
                ret = gcd(ret, self.data[R-1])
            if L & 1:
                ret = gcd(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


N = int(input())
L = list(map(int, input().split()))
T = SegmentTree(N, 0)
for i, l in enumerate(L):
    T.set(i, l)
T.build()

ans = 0
for i in range(N):
    l = i
    r = i+1
    ans = max(ans, gcd(T.query(0, l), T.query(r, N)))
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  #左からi番目までのgcdをメモった配列
R = [0] * N  #右からi番目までのgcdをメモった配列
L[0] = A[0]
R[0] = A[N - 1]
for i in range(1, N):
	L[i] = gcd(L[i - 1], A[i])
	R[i] = gcd(R[i - 1], A[N - 1 - i])
ans = max(L[N - 2], R[N - 2])
for j in range(1, N - 1):
	ans = max(ans, gcd(L[j - 1], R[N - j - 2]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


N = int(input())
lstA = list(map(int, input().split()))
lstL = [0] * N
lstR = [0] * N


for i in range(1, N):
    lstL[i] = gcd(lstL[i-1], lstA[i-1])
for i in range(N-1)[::-1]:
    lstR[i] = gcd(lstR[i+1], lstA[i+1])
lstGcd = [gcd(lstL[i], lstR[i]) for i in range(N)]
ans = max(lstGcd)


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 i in range(N)]
R = [0 for i in range(N)]
T = [0 for i in range(N)]

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

print(max(T))

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 i in range(N)]
R = [0 for i in range(N)]
T = [0 for i in range(N)]

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

print(max(T))

Submission status: Accepted

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

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

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

# L: list
# boundary: L[0] = 0, L[N-1] = 0
# L[i]: previous (i-1)-th gcd value, i = [0, ..., N-2]
for i in range(N-1):
    L[i+1] = gcd(L[i], A[i])

# R: list
# boundary: R[0] = 0, R[N-1] = 0
# R[i]: last (N-i)-th gcd value, i = [N-1, ..., 1]
for i in range(N-1, 0, -1):
    R[i] = gcd(R[i+1], A[i])

max_gcd = 0
for i in range(N):
    if gcd(L[i], R[i+1]) > max_gcd:
        max_gcd = gcd(L[i], R[i+1])

print '{}'.format(max_gcd)

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
 
 
def gcd_ab(a,b):
  a,b = sorted([a,b])
  if a == 0:
    return b
  return gcd_ab(b%a, a)
 
if __name__ == "__main__": 
  N = int(input())
  An = list(map(int, sys.stdin.readline().rstrip().split()))
  cum = [[0,0] for i in range(N+2)]
 
  for i in range(N):
    cum[i+1][0] = gcd_ab(cum[i][0], An[i])
    cum[N-i][1] = gcd_ab(cum[N-i+1][1], An[N-i-1])
 
  ans = [0 for i in range(N)]
  for i in range(1,N+1):
    ans[i-1] = gcd_ab(cum[i-1][0], cum[i+1][1])
  print(max(ans))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
def gcd(a,b):
  if a<=b:
    a,b=b,a
  if a%b==0:
    return b
  else:
    return gcd(b,a%b)
L,R=[],[]
ld,rd=A[0],A[n-1]
for i in range(n):
  ld=gcd(ld,A[i])
  rd=gcd(rd,A[n-1-i])
  L.append(ld)
  R.append(rd)
ans=max(L[-2],R[-2])
for i in range(1,n-1):
  ans=max(ans,gcd(L[i-1],R[n-i-2]))
print(ans if n!=2 else max(A))

Submission status: Accepted

Solution code:
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(reverse=True)
    return divisors


N = int(input())
A = sorted([int(x) for x in input().split()])

ans = 1
for i in range(2):
    div_list = make_divisors(A[i])

    for div_i in div_list:
        wrong_count = 0

        for A_i in A:
            if A_i % div_i != 0:
                wrong_count += 1

        if wrong_count <= 1 and div_i > ans:
            ans = div_i

print(ans)