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

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

left_ = [0] * (n + 1)
right_ = [0] * (n + 1)
ans = []

for i in range(n):
    left_[i] = gcd( left_[i-1], data[i] )

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

for i in range(n):
    ans += [ gcd( left_[i-1], right_[i+1] ) ]

print( max(ans) )

Submission status: Accepted

Solution code:
from math import *
N = int(input())
A = list(map(int,input().split()))
L = (N+1)*[0]
R = (N+1)*[0]
ans = []

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

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

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

print(max(ans))

Submission status: Accepted

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

def gcd_bl(A):

    left = [0 for _ in range(N + 1)]
    right = [0 for _ in range(N + 1)]
    ans = [0 for _ in range(N)]

    left[1] = A[0]
    for i in range(1, N):
        left[i + 1] = gcd_(left[i], A[i])
    right[-1 - 1] = A[-1]
    for i in range(1, N):
        right[-1 - i - 1] = gcd_(right[-1 - i], A[-1 - i])
    for i in range(N):
        ans[i] = gcd_(left[i], right[i + 1])
        
    return ans

def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

N = cin()
A = cin()
ans = 0
g = gcd_bl(A)
print(max(g))

Submission status: Accepted

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

# 以降のGCD
left_gcds = [A[0]]
for a in A[1:]:
    left_gcds.append(gcd(left_gcds[-1], a))

right_gcds = [A[-1]]
for a in A[:n-1][::-1]:
    right_gcds.append(gcd(right_gcds[-1], a))
right_gcds.reverse()

ans = 0
for i in range(n):
    if i == 0:
        tmp = right_gcds[i+1]
    elif i == n-1:
        tmp =left_gcds[i-1]
    else:
        tmp = gcd(left_gcds[i-1], right_gcds[i+1])
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import math
def gcd(a,b):
    return b if not a%b else gcd(b,a%b)
def lcm(a,b):
    return (a*b)//gcd(a,b)

def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    res = 0
    m = 0
    l_g = [0,A[0]]
    r_g = [0,A[-1]]
    ind = 2
    for i in A[1:]:
        l_g.append(gcd(l_g[ind-1],i))
        ind += 1
    ind = 2
    for i in range(n-2,-1,-1):
        r_g.append(gcd(r_g[ind-1],A[i]))
        ind += 1
    r_g = r_g[::-1]
    r_g = r_g[1:]

    for i in range(len(r_g)):
        if(r_g[i]!=0 and l_g[i]!=0):
            res = max(res, gcd(r_g[i],l_g[i]))
        else:
            res = max(r_g[i],l_g[i],res)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

L=[a[0]]
gcdl = a[0]
R=[a[n-1]]
gcdr = a[n-1]
for xi in range(1,n):
    gcdl = math.gcd(gcdl,a[xi])
    L.append(gcdl)

for xi in range(n-2,-1,-1):
    gcdr = math.gcd(gcdr,a[xi])
    R.append(gcdr)

R.reverse()

# print("R", R)
# print("L", L)
m = []
m.append(R[1])
m.append(L[n-2])
# print(m)

if n>2:
    for xi in range(1,n-1):
        m.append(math.gcd(L[xi-1],R[xi+1]))
        # print(xi, R[xi+1],L[xi-1])

# print(m)
print(max(m))

Submission status: Accepted

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

L = list(accumulate(A, gcd))
R = list(accumulate(A[::-1], gcd))[::-1]

ans = max(gcd(l, r) for l, r in zip([0]+L[:-1], R[1:]+[0]))
print(ans)

Submission status: Accepted

Solution code:
import math

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

gcd_l = [0]
gcd_r = [0]


for i in range(N):
    gcd_l.append(math.gcd(gcd_l[i], A[i]))
    gcd_r.append(math.gcd(gcd_r[i], A[-(i+1)]))

gcd_r = gcd_r[::-1]

max_gcd = 0
for i in range(N):
    max_gcd = max(max_gcd, math.gcd(gcd_l[i], gcd_r[i+1]))

print(max_gcd)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[*map(int,input().split())]
from math import *
l,r=[0]*n,[0]*n
for i in range(1,n):
  l[i]=gcd(l[i-1],a[i-1])
  r[~i]=gcd(r[-i],a[-i])
m=0
for i in range(n):
  m=max(m,gcd(l[i],r[i]))
print(m)

Submission status: Accepted

Solution code:
n=int(input())
a=[*map(int,input().split())]
from math import *
l=a.copy()
r=a.copy()
for i in range(n-1):
  l[i+1]=gcd(l[i],l[i+1])
  r[-i-2]=gcd(r[-i-1],r[-i-2])
a=max(l[-2],r[1])
for i in range(1,n-1):
  a=max(a,gcd(l[i-1],r[i+1]))
print(a)

Submission status: Accepted

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

front = [0] * N
front[0] = A[0]
for i in range(1,N):
    front[i] = gcd(front[i-1],A[i])
back = [0] * N
back[-1] = A[-1]
for i in reversed(range(N-1)):
    back[i] = gcd(back[i+1],A[i])

ans = max(front[-2],back[1])
for i in range(N-2):
    ans = max(ans,gcd(front[i],back[i+2]))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
l = list(map(int,input().split()))
mi = 1
gcd_l = [l[0]]
gcd_r = [l[-1]]
for i in range(1,n):
  gcd_l.append(gcd(l[i],gcd_l[-1]))
for i in range(n-2,-1,-1):
  gcd_r.append(gcd(l[i],gcd_r[-1]))
  
for i in range(0,n-2):
  t = gcd(gcd_l[i], gcd_r[n-3-i])
 # print(t)
  mi = max(mi,t)
#print(gcd_l)
#print(gcd_r)
mi = max(mi,gcd_r[-2])
mi = max(mi,gcd_l[-2])
print(mi)

Submission status: Accepted

Solution code:
import math

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

gcd_l = [0]
gcd_r = [0]

for n in range(N):
    gcd_l.append(math.gcd(gcd_l[n], A[n]))
    gcd_r.append(math.gcd(gcd_r[n], A[-(n + 1)]))
#print(gcd_r)
#print(gcd_l)

gcd_r = gcd_r[::-1]
#print(gcd_r)

ans = []
for n in range(N):
    ans.append(math.gcd(gcd_l[n], gcd_r[n + 1]))
print(max(ans))
#print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

if n == 2:
    print(max(A))
else:
    # 最初の3個のうちの2個を選んで、最大の最大公約数
    # 最大公約数に選ばれなかったものを交換（rがaより大きいとき）
    r = max(gcd(A[0], A[1]), gcd(A[1], A[2]), gcd(A[2], A[0]))
    # リストaの最初3個の最大公約数
    a = gcd(A[0], gcd(A[1], A[2]))

    for i in range(3, n):
        r = max(gcd(A[i], r), a)
        a = gcd(A[i], a)

    print(r)

Submission status: Accepted

Solution code:
from math import gcd

def init(init_val):
    for i in range(N):
        seg[i+num-1] = init_val[i]
    for i in range(num-2, -1, -1):
        seg[i] = gcd(seg[2*i+1], seg[2*i+2])

def update(k, x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = gcd(seg[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 = gcd(res, seg[p])
        if q&1 == 1:
            res = gcd(res, seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = gcd(res, seg[p])
    else:
        res = gcd(gcd(res, seg[p]), seg[q])
    return res

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

ide_ele = 0
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)

Submission status: Accepted

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

a.sort()
g=a[0]

for i in range(1,n):
  g=math.gcd(g,a[i])

d=[set(),set()]
for i in range(2):
  b=a[i]//g
  f=1
  while f*f<b+1:
    if b%f==0:
      d[i].add(f)
      d[i].add(b//f)
    f+=1

an=d[0]&d[1]
an.remove(1)
xo=d[0]^d[1]

for i in range(2,n):
  e1=set()
  e2=set()
  for m in xo:
    if a[i]%m!=0:
      e1.add(m)
  for m in an:
    if a[i]%m!=0:
      e2.add(m)
      xo.add(m)
  for m in e1:
    xo.remove(m)
  for m in e2:
    an.remove(m)
an.add(1)
xo.add(1)
print(max(max(xo),max(an))*g)

Submission status: Accepted

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

a.sort()
g=a[0]

for i in range(1,n):
  g=math.gcd(g,a[i])

d=[set(),set()]
for i in range(2):
  b=a[i]//g
  f=1
  while f*f<b+1:
    if b%f==0:
      d[i].add(f)
      d[i].add(b//f)
    f+=1

an=d[0]&d[1]
xo=d[0]^d[1]

for i in range(2,n):
  e1=set()
  e2=set()
  for m in xo:
    if a[i]%m!=0:
      e1.add(m)
  for m in an:
    if a[i]%m!=0:
      e2.add(m)
      xo.add(m)
  for m in e1:
    xo.remove(m)
  for m in e2:
    an.remove(m)
an.add(0)
xo.add(0)
print(max(max(xo),max(an))*g)

Submission status: Accepted

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

N=int(input())
array=sorted([int(x) for x in input().split()])
prefix_GCD=[0]*(N)
suffix_GCD=[0]*(N)
currentGCD=array[0]

for i in range(N):
	prefix_GCD[i]=gcd(currentGCD,array[i])
	currentGCD=gcd(currentGCD,(array[i]))
currentGCD=array[N-1]

for i in range(N-1,-1,-1):
	suffix_GCD[i]=gcd(currentGCD,(array[i]))
	currentGCD=gcd(currentGCD,(array[i]))
	
highest=0
for i in range(N):
	if i==0:
		gcdwithout=suffix_GCD[1]
	elif i==N-1:
		gcdwithout=prefix_GCD[-2]
	else:
		gcdwithout=gcd(prefix_GCD[i-1],suffix_GCD[i+1])
	highest=max(highest,gcdwithout)
print(highest)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i == 0:
			cnt = 0
			while tmp%i == 0:
				cnt += 1
				tmp //= i
			arr.append([i, cnt])
	if tmp != 1:
		arr.append([tmp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

N = INT()
A = LIST()

def max_gcd(n):
	g = []
	for p, q in factorization(n):
		g += [p]*q
	g.sort(reverse = True)
	cnt = [0]*len(g)
	cnt_memo = [-1]*len(g)
	for i in range(N):
		a = A[i]
		for j in range(len(g)):
			if a%g[j] == 0:
				cnt[j] += 1
				a //= g[j]
			elif cnt_memo[j] == -1:
				cnt_memo[j] = i

	ans = 1
	flg = True
	for i in range(len(g)):
		if cnt[i] == N:
			ans *= g[i]
		elif cnt[i] == N-1 and flg:
			ans *= g[i]
			flg = False
			tmp = cnt_memo[i]
		elif cnt[i] == N-1 and cnt_memo[i] == tmp:
			ans *= g[i]

	return ans

print(max(max_gcd(A[0]), max_gcd(A[1])))

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
r ,l = [0] * (n),[0] * (n)
l[0] = 0
r[n-1] = 0
for i in range(1,n):
    l[i] = math.gcd(l[i-1],a[i-1])
    r[n-i-1] = math.gcd(r[n-i],a[n-i])
m = [0] * n
for i in range(n):
    m[i] = math.gcd(l[i],r[i])
print(max(m))

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
A=sorted(list(map(int,input().split())))
B = A[-1::-1]

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

m=[]
for i in range(N):
    m.append(math.gcd(GCA[i],GCB[i+1]))
print(max(m))

Submission status: Accepted

Solution code:
from math import gcd

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

if N == 2:
    print(max(A))
else:
    r = max(gcd(A[0], A[1]), gcd(A[1], A[2]), gcd(A[2], A[0]))
    a = gcd(A[0], gcd(A[1], A[2]))

    for i in range(3, N):
        r = max(gcd(A[i], r), a)
        a = gcd(A[i], a)
        
    print(r)

Submission status: Accepted

Solution code:
from math import gcd
class SEGTree:
    def __init__(self,n):
        self.Unit=0
        i=1
        while(i<n):
            i*=2
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]=x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=gcd(self.SEG[i*2+1],self.SEG[i*2+2])
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return gcd(c1,c2)
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)

N=int(input())
SEG=SEGTree(N)
A=list(map(int,input().split()))
for i in range(N):
    SEG.update(i,A[i])
ans=1
for i in range(N):
    l,r=SEG.get(0,i),SEG.get(i+1,N)
    ans=max(ans,gcd(l,r))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd


def main():
    n = int(input())
    a = list(map(int, input().split()))
    left_accumulate_gcd = [0 for _ in range(n + 2)]
    right_accumulate_gcd = [0 for _ in range(n + 2)]
    for i in range(n):
        left_accumulate_gcd[i + 1] = gcd(a[i], left_accumulate_gcd[i])
    for i in range(n - 1, -1, -1):
        right_accumulate_gcd[i] = gcd(a[i], right_accumulate_gcd[i + 1])
    ans = 1
    for i in range(n + 1):
        ans = max(ans, gcd(left_accumulate_gcd[i], right_accumulate_gcd[i + 1]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())
a = [int(x) for x in input().split()]
pref = [x for x in a]
suff = [x for x in a]
for i in range(1,n):
	pref[i] = gcd(pref[i-1],a[i])
for i in range(n-2,-1,-1):
	suff[i] = gcd(suff[i+1],a[i])

print(max([pref[-2],suff[1]]+[gcd(pref[i-1],suff[i+1]) for i in range(1,n-1)]))

Submission status: Accepted

Solution code:
import math

MAXN = 2 ** 17

ide_ele = 0

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

num = 2**(n-1).bit_length()
seg = [ide_ele] * 2 * num

def init(init_val):
    for i in range(n):
        seg[i+num-1] = init_val[i]
    for i in range(num-2 ,-1, -1) :
        seg[i] = math.gcd(seg[2*i+1],seg[2*i+2])
        
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = math.gcd(seg[k*2+1] , seg[k*2+2])

init(a)
ans = 0
for i in range(n):
    update(i,0)
    ans = max(ans,seg[0])
    update(i,a[i])
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = [-1] + list(map(int, input().split()))

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

left_gcd = [0] + [0] * n + [-1]
right_gcd = [-1] + [0] * n + [0]

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

ans = 1
for i in range(1, n+1):
    ans = max(ans, gcd(left_gcd[i-1], right_gcd[i+1]))
print(ans)

Submission status: Accepted

Solution code:
import math

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

gcd_left = []
gcd_right = []
for i in range(n):
    if i == 0:
        gcd_left.append(a[i])
        gcd_right.append(a[n - 1 - i])
    else:
        gcd_left.append(math.gcd(a[i], gcd_left[i - 1]))
        gcd_right.append(math.gcd(a[n - 1 - i], gcd_right[i - 1]))
gcd_right.reverse()

gcd_ex = []
for i in range(n):
    if i == 0:
        gcd_ex.append(gcd_right[i + 1])
    elif i == n - 1:
        gcd_ex.append(gcd_left[i - 1])
    else:
        gcd_ex.append(math.gcd(gcd_left[i - 1], gcd_right[i + 1]))
print(max(gcd_ex))

Submission status: Accepted

Solution code:
import math

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

ar = a[::-1]
l = [0]
r = []

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

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

Submission status: Accepted

Solution code:
import math
def main():
    n = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    gcdl, gcdr = [0, ], [0, ]
    for i in range(1, n):
        gcdl.append(g := math.gcd(g, A[i - 1]))
    g = A[-1]
    for i in range(n - 2, -1, -1):
        gcdr.append(g := math.gcd(g, A[i + 1]))
    gcdr = gcdr[::-1]
    ans = [math.gcd(l, r) for l, r in zip(gcdl, gcdr)] + [math.gcd(gcdl[-1], A[-1]), ]
    print(max(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()


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


def main():
    l, r = [None] * N, [None] * N
    l[0] = A[0]
    r[0] = A[-1]
    for i in range(1, N):
        l[i] = gcd(l[i - 1], A[i])
        r[i] = gcd(r[i - 1], A[-i - 1])
    
    ans = 1
    for i in range(N):
        if i == 0:
            x = r[-2]
        elif i == N - 1:
            x = l[-2]
        else:
            x = gcd(l[i - 1], r[N - i - 2])
        ans = max(ans, x)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np


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


input = sys.stdin.buffer.readline
N = int(input())
A = np.array(sorted(list(map(int, input().split()))))
# print(f'{A=}')

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

for i in range(N):
    L[i + 1] = gcd(L[i], A[i])
# print(f'{L=}')

for i in range(N - 1, -1, -1):
    R[i] = gcd(R[i + 1], A[i])
# print(f'{R=}')

for i in range(N):
    M[i] = gcd(L[i], R[i + 1])
# print(f'{M=}')
ans = max(M)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N = ii()
    A = list(mi())

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

    M = [0]*N

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

    for i in range(N):
        if L[i] == 0:
            M[i] = R[i]
        elif R[i] == 0:
            M[i] = L[i]
        else:
            M[i] = gcd(R[i], L[i])
    
    print(max(M))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

left = []
right = []

left.append(A[0])
for a in A[1:]:
    left.append(gcd(left[-1], a))

right.append(A[-1])
for a in A[-2::-1]:
    right.append(gcd(right[-1], a))

right = list(reversed(right))

ans = [left[-2], right[1]]

for i in range(1, len(left) - 1):
    ans.append(gcd(left[i - 1], right[i + 1]))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import Counter
from functools import lru_cache
from math import gcd


@lru_cache(maxsize=None)
def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


@lru_cache(maxsize=None)
def lcm(a, b):
    """
    aとbの最小公倍数を計算する
    """

    return a * b // gcd(a, b)


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

counter = Counter()
for a in A:
    counter.update(get_dividers(a))

ans = 1
candidates = []
for key, value in counter.items():
    if value == N:
        ans = lcm(ans, key)
    elif value == N - 1:
        candidates.append(key)

if candidates:
    ans = max([lcm(ans, c) for c in candidates])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from math import gcd

N = int(input())
a = list(map(int, input().split()))
l = [0]

for ai in a:
    l.append(gcd(l[-1], ai))

r = [0]

for ai in a[::-1]:
    r.append(gcd(r[-1], ai))

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from math 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]
P=0
for i in range(N):
  P=max(P,gcd(L[i],R[i+1]))
print(P)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = [int(X) for X in input().split()]
Left  = [0]*(N+1)
Right = [0]*(N+1)
GCDLR = [0]*(N+1)
for T in range(0,N):
    Left[T+1] = math.gcd(Left[T],A[T])
    Right[N-T-1] = math.gcd(Right[N-T],A[N-T-1])
    
for T in range(0,N):
    GCDLR[T] = math.gcd(Left[T],Right[T+1])
print(max(GCDLR))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
from math import gcd
def main():
    n, *a = map(int, read().split())
    if n == 1:
        print(a[0])
        sys.exit()
    l = [0] * (n + 1)
    for i1 in range(n):
        l[i1 + 1] = gcd(l[i1], a[i1])
    r = [0] * (n + 1)
    for j1 in range(n - 1, -1, -1):
        r[j1] = gcd(r[j1 + 1], a[j1])
    m = [0] * (n + 1)
    for k1 in range(n):
        m[k1] = gcd(l[k1], r[k1 + 1])
    r = max(m)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n,ans=int(input()),1
A=list(map(int,input().split()))
gcd_l,gcd_r=[],[]
l,r=A[0],A[n-1]

for i in range(n-1):
  l,r=gcd(l,A[i]),gcd(r,A[n-i-1])
  gcd_l.append(l)
  gcd_r.append(r)

for i in range(n-2):
  v=gcd(gcd_l[i],gcd_r[n-3-i])
  if v > ans:
    ans = v

if gcd_l[n-2] > ans:
  ans=gcd_l[n-2]
if gcd_r[n-2] > ans:
  ans=gcd_r[n-2]
  
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
num = list(map(int, input().split()))

gL = [0]*(N+2)
gR = [0]*(N+2)

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

    while (a > b) and (a % b > 0):
        a = a - b
        if a < b:
            a, b = b, a

    return b

gL[0] = 0
gR[N] = 0
for i in range(1, N+1):
    gL[i] = gdc(gL[i-1], num[i-1])

for i in range(N-2, -1, -1):
    gR[i] = gdc(gR[i+1], num[i+1])

ans = 0
for i in range(0, N):
    gg = gdc(gL[i], gR[i])
    if ans < gg:
        ans = gg

print(ans)

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
lst=sorted(map(int,input().split()))

p=make_divisors(lst[0])
q=make_divisors(lst[1])
pq=set(p+q)
pq=sorted(pq)
for i in range(len(pq)-1,-1,-1):
    out=0
    for j in lst:
        if j%pq[i]!=0:
            out+=1
    if out<=1:
        print(pq[i])
        exit()

Submission status: Accepted

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

Submission status: Accepted

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

left = [0]
gcd_left = 0
for a in A:
    gcd_left = math.gcd(gcd_left, a)
    left.append(gcd_left)
right = [0]
gcd_right = 0
for a in reversed(A):
    gcd_right = math.gcd(gcd_right, a)
    right.append(gcd_right)
right.append(0)
right = list(reversed(right))
# print(left)
# print(right)

max_gcd = 0
for i in range(1, N+1):
    sub_gcd = math.gcd(left[i-1], right[i+1])
    max_gcd = max(max_gcd, sub_gcd)
print(max_gcd)

Submission status: Accepted

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

import math
l_gcd = []
r_gcd = []

c = a[0]
for i in a[:-1]:
  c = math.gcd(c, i)
  l_gcd.append(c)
  
c = a[-1]
for j in a[1:][::-1]:
  c = math.gcd(c, j)
  r_gcd.append(c)
  
ans = max(r_gcd[-1], l_gcd[-1])
for r, l in zip(r_gcd[:-1], l_gcd[:-1][::-1]):
  c = math.gcd(r, l)
  ans = max(ans, c)
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
dp_left=[0]*(N+1)
dp_right=[0]*(N+1)
for i in range(N):#左から累積GCD
  dp_left[i+1]=math.gcd(dp_left[i],A[i])
  dp_right[N-i-1]=math.gcd(dp_right[N-i],A[N-1-i])#右から累積GCD

ans = 0
for i in range(N):
  ans = max(ans,math.gcd(dp_left[i],dp_right[i+1]))
print(ans)

Submission status: Accepted

Solution code:
import math

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

L = [0] * (n+1)
R = [0] * (n+1)
for i in range(n):
  if L[i] == 0:
    L[i+1] = a[i]
  else:
    L[i+1] = math.gcd(L[i], a[i])
  
  #print(n, i, n-i-1)
  if R[n-i] == 0:
    R[n-i-1] = a[n-i-1]
  else:
    R[n-i-1] = math.gcd(R[n-i], a[n-i-1])
M = [0] * (n+1)
for i in range(n):
  M[i] = math.gcd(L[i], R[i+1])
print(max(M))

Submission status: Accepted

Solution code:
import math
#####segfunc#####
def segfunc(x, y):
    if x*y == 0:
        return max(x,y)
    return math.gcd(x,y)
#################

#####ide_ele　単位元#####
ide_ele = 0
#################



class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

"""使用例"""

n=int(input())
A=[int(i) for i in input().split()]
tre=SegTree([0 for i in range(n)],segfunc,ide_ele)
for i in range(n):
    tre.update(i,A[i])

ans=0
for i in range(n):
    dat=segfunc(tre.query(0,i),tre.query(i+1,n))
    ans=max(dat,ans)
print(ans)

Submission status: Accepted

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

from math import gcd
L=[A[0]]*N
R=[A[-1]]*N

for a_idx in range(1,len(A)):
    L[a_idx]=gcd(L[a_idx-1],A[a_idx])
    R[len(A)-a_idx-1]=gcd(R[len(A)-a_idx],A[len(A)-a_idx-1])

ans_list=[0]*N
ans_list[0] = R[1]
ans_list[-1] = L[-2]

for a_idx in range(1,len(A)-1):
    ans_list[a_idx] = gcd(L[a_idx-1],R[a_idx+1])
    
print(max(ans_list))