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

def mygcd(x, y):
    if x == 0 or y == 0:
        return max(x, y)
    return gcd(x, y)

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

    L = [0]; R = [0]
    for i in range(len(A)):
        Lbase = mygcd(L[-1], A[i])
        L.append(Lbase)
        Rbase = mygcd(R[-1], A[-i-1])
        R.append(Rbase)
    
    ans = 0
    R.reverse()
    for i in range(len(A)):
        tmp = mygcd(L[i], R[i+1])
        ans = max(ans, tmp)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from fractions import gcd
    input=sys.stdin.readline
    n=int(input())
    a=tuple(map(int,input().split()))
    ide_ele=0
    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]=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=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

    init(a)
    ans=-1
    for i in range(n):
        ans=max(ans,gcd(query(0,i),query(i+1,n)))
    print(ans)
main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

fgcd, ftmp = [], a[0]
for i in a:
    ftmp = gcd(ftmp, i)
    fgcd.append(ftmp)

bgcd, btmp = [], a[-1]
for i in a[::-1]:
    btmp = gcd(btmp, i)
    bgcd.append(btmp)
bgcd = bgcd[::-1]

egcd = [bgcd[1]] + [0] * (n - 2) + [fgcd[n - 2]]
for i in range(1, n - 1):
    egcd[i] = gcd(fgcd[i - 1], bgcd[i + 1])
print(max(egcd))

Submission status: Accepted

Solution code:
from fractions import gcd

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

fgcd, ftmp = [], a[0]
for i in a:
    ftmp = gcd(ftmp,i)
    fgcd.append(ftmp)

bgcd, btmp = [], a[-1]
for i in a[::-1]:
    btmp = gcd(btmp, i)
    bgcd.append(btmp)
bgcd=bgcd[::-1]

egcd = [bgcd[1]] + [0] * (n - 2) + [fgcd[n - 2]]
for i in range(1, n - 1):
    egcd[i] = gcd(fgcd[i - 1], bgcd[i + 1])
print(max(egcd))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
l = a[0]
r = a[-1]
ll = deque([l])
rl = deque([r])
for i in range(1,n-1):
    l = gcd(l,a[i])
    r = gcd(r,a[-(i+1)])
    ll.append(l)
    rl.appendleft(r)

llas = ll.pop()
rlas = rl.popleft()

res = max(llas,rlas)
for i in range(n-2):
    res = max(res, gcd(ll.pop(), rl.pop()))
print(res)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
GCD= a[0]
dp = [set() for i in range(n)]
dp[1].add(a[0])
dp[1].add(a[1])
for i in range(1,n):
    x = a[i]
    for j in dp[i-1]:
            dp[i].add(gcd(j,x))
    if x % GCD != 0:
        dp[i].add(GCD)
        GCD = gcd(GCD,x)
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
GCD= a[0]
dp = [set() for i in range(n)]
dp[0].add(a[0])
dp[0].add(a[1])
for i in range(1,n):
    x = a[i]
    for j in dp[i-1]:
            dp[i].add(gcd(j,x))
    if x % GCD != 0:
        dp[i].add(GCD)
        GCD = gcd(GCD,x)
print(max(dp[n-1]))

Submission status: Accepted

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

left.append(a[0])
for i in range(1,n-1):
    left.append(gcd(left[-1],a[i]))
a = a[::-1]
right.append(a[0])
for i in range(1,n-1):
    right.append(gcd(right[-1],a[i]))
ans = 1
for i in range(n-1):
    ans = max(ans,gcd(left[i],right[n-i-3]))
ans = max(ans,left[n-2],right[n-2])
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

# 配列aで初期化
def init(a):
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = gcd(seg[2*i+1], seg[2*i+2]) 


# a[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 % 2 == 0:
            res = gcd(res, seg[p])
        if q % 2 == 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()))

ide_ele = 0
num = 2 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

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

print(res)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
left = a[:]
right = a[:]
for i in range(1, n):
  left[i] = gcd(left[i], left[i-1])
  right[n-i-1] = gcd(right[n-i], right[n-i-1])
maximum = max(left[n-2], right[1])
for i in range(n-2):
  common_divisor = gcd(left[i], right[i+2])
  if common_divisor > maximum:
    maximum = common_divisor
print(maximum)

Submission status: Accepted

Solution code:
#前からと後ろ側から最大公約数を求めていけば途中で抜くべき値がある。2つ直すことはできないのでどちらかは最大になる。
#0と何かの数字xの最大公約数はx

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

L, R = [0] * (n + 1), [0] * (n + 1)
for i in range(n):
    L[i + 1] = gcd(L[i], A[i])
    R[n - i - 1] = gcd(R[n - i], A[n - 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:
import fractions
# input
n = int(input())
A = [0] + [int(i) for i in input().split()] + [0]

# define
L = [0 for i in range(n+1)]
R = [0 for i in range(n+1)]
M = [0 for i in range(n)]

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

# output  
print(max(M))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

#####MakeDivisors######
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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

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

kake1 = A[0]
kake2 = A[1]
zenbu = gcd(A[0],A[1])

for a in A[2:]:
  kake1 = max(gcd(kake1,a),zenbu)
  kake2 = max(gcd(kake2,a),zenbu)
  zenbu = gcd(zenbu,a)
print(max(kake1,kake2,zenbu))

Submission status: Accepted

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

'''
'init(a)': 配列aで初期化。O(N)
'update(k,x)': a[k]をxに変更 O(logN)
'query(p,q)': [p,q)について "segfunc" したものを返す O(logN)
'ide_ele' : 単位元。
'''


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


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

# num:n以上の最小の2のべき乗
num = 2**(N-1).bit_length()
seg = [ide_ele]*2*num

init(A)

# print(query(0, 2))

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

Submission status: Accepted

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

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

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

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

left = [None] * N
left[0] = A[0]
for i in range(1, len(A)):
  left[i] = gcd(left[i - 1],A[i])

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

ans = max(left[-2],right[1])
for i in range(1, len(A) - 1):
  g = gcd(left[i - 1],right[i + 1])
  if ans < g:
    ans = g
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

# 配列aで初期化
def init(a):
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = gcd(seg[2*i+1], seg[2*i+2]) 


# a[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()))

ide_ele = 0
num = 2 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

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

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
N = int(input())
A = list(map(int,input().split()))
#累積GCD
left = [0]*(N+1)
right = [0]*(N+1)
for i in range(N):
  left[i+1] = (fractions.gcd(left[i],A[i]))
  right[N-i-1] = (fractions.gcd(right[N-i],A[N-1-i]))

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

n=int(input())
a=[int(i) for i in input().split()]
a1=[a[0]]
for i in range(1,n-1):
    a1.append(gcd(a1[-1],a[i]))
a2=[a[-1]]
for i in range(n-2,0,-1):
    a2.append(gcd(a2[-1],a[i]))
m=[]
for i in range(n-2):
    m.append(gcd(a1[i],a2[-i-2]))
m.append(a1[-1])
m.append(a2[-1])
print(max(m))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
size=len(a)
def gcd(a,b):
    while True:
        r=a%b
        if r==0:
            return b
        a,b=b,r
forward=[]
backward=[]
temp=a[0]
for ele in a:
    temp=gcd(temp,ele)
    forward.append(temp)

temp=a[len(a)-1]
for ele in reversed(a):
    temp=gcd(temp,ele)
    backward.append(temp)
backward.reverse()
ans=max(backward[1],forward[len(a)-2])
for i in range(len(a)-2):
    temp=gcd(forward[i],backward[i+2])
    ans=max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

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

def gcd(x,y):
    if x==0 or y==0:
        return max(x,y)
    return fractions.gcd(x,y)

for i in range(N):
    j=N-i

    L[i+1]=gcd(L[i],A[i])
    R[j-1]=gcd(R[j],A[j-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())
a = list(map(int, input().split()))

import fractions
left, right = [], []
for arr, l in zip([a, a[::-1]], [left, right]):
    l.append(arr[0])
    for i in range(1, n):
        l.append(fractions.gcd(l[-1], arr[i]))

left = [right[-1], right[-2]] + left
right = right[::-1] + [left[-2], left[-1]]

ans = 0
for (l, r) in zip(left, right):
    ans = max(ans, fractions.gcd(l, r))

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

N = getN()
A = getList()

course = []
x1 = A[0]
for i in A:
    x2 = i
    opt = gcd(x1, x2)
    course.append(opt)
    x1 = opt

reverse = []
y1 = A[-1]
for i in A[::-1]:
    y2 = i
    opt = gcd(y1, y2)
    reverse.append(opt)
    y1 = opt
reverse.sort()

ans = 0
for i in range(N):
    res = 0
    if i == 0:
        res = reverse[1]
    elif i == N - 1:
        res = course[-2]
    else:
        res = gcd(course[i - 1], reverse[i + 1])
    ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import fractions

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


left_gcd = [0 for _ in range(n)]
right_gcd = [0 for _ in range(n)]

left_gcd[0] = a[0]
right_gcd[-1] = a[-1]

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

for i in range(n-2, -1, -1):
    right_gcd[i] = fractions.gcd(right_gcd[i+1], a[i])
# print(left_gcd)
# print(right_gcd)

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

ans = max(ans, right_gcd[1], left_gcd[-2])
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
n = int(input())
a = list(map(int, input().split()))

# 愚直解(TLE)
# ans_stupid = 0
# for i in range(n):
    # ans_stupid = (ans_stupid, gcd_list(a[:i] + a[i + 1:]))
# print(ans_stupid)

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

gcd_left = [gcd_right[-1]] + gcd_left
gcd_right = gcd_right + [gcd_left[1]]
ans = 1
for i in range(N):
    ans = max(ans, gcd(gcd_left[i], gcd_right[i + 1]))
print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

N = int(input())
input = sys.stdin.readline().rstrip()
A = list(map(int, input.split()))

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 = 0
for i in range(N - 2):
    ans = max(ans, gcd(L[i], R[N - i - 3]))
ans = max(ans, R[N - 2])
ans = max(ans, L[N - 2])
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
arr = 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],arr[i])
  right[-i-2] = gcd(right[-i-1], arr[-i-1])

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

print(ans)

Submission status: Accepted

Solution code:
"""参考
@ct158603292321　　2019年05月03日に更新
qiita AtCoder ABC125 解説
https://qiita.com/ct158603292321/items/4cddafa5c2500a657ccf
"""
#約数
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

# 初期入力
import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A_np =np.array(A)

#list(A)の内、任意で2つ選び約数の和集合（公約数ではない）
div_A_2 =make_divisors(A[0]) + make_divisors(A[1])
ans =[]
for i in div_A_2:
    aa= np.count_nonzero(A_np %i ==0) #iで割り切れる要素を数える
    if aa >=N-1:
        ans.append(i)
print(max(ans))

Submission status: Accepted

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
A.sort()
MIN=A[1]
for i in range(MIN,0,-1):
  miss=0
  for k in range(N):
    if A[k]%i != 0:
      miss+=1
      if miss==2:
        break
    if k==N-1:
      ans=i
      print(ans)
      sys.exit()

Submission status: Accepted

Solution code:
import math
import fractions
from functools import reduce

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

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

N = int(input())

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

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


p = 0
for i in range(N):
  if i == 0:
    ans = R[N-2]
  elif i == N-1:
    ans = L[-2]
  else:
    a = L[i-1]
    b = R[N-i-2]
    ans = gcd(a,b)
  p = max(p,ans)
  
print(int(p))

Submission status: Accepted

Solution code:
n = int(input())
As = list(map(int, input().split()))
# from math import gcd
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a
# 左からの累積GCDと
g = As[0]
left = []
for a in As:
    g = gcd(g, a)
    left.append(g)
# 右からの累積GCD
As_r = As[::-1]
g_r = As_r[0]
right = []    
for a in As_r:
    g_r = gcd(g_r, a)
    right.append(g_r)
    
l = left
r = right[::-1]
ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans, r[1])
    elif i == n-1:
        ans = max(ans, l[n-2])
    else:     
        g = gcd(l[i-1],r[i+1])
        ans = max(ans, g)
print(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 b == 0:    return a
    return gcd_(b, a % b)

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

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

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

Submission status: Accepted

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

X = [0]*N
Y = [0]*N

import fractions

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

Y[N-1]=A[N-1]
for i in range(1,N):
    Y[N-1-i] = fractions.gcd(Y[N-i], A[N-1-i])

cand = []
cand.append(X[N-2])
cand.append(X[N-1])#=Y[0]
cand.append(Y[1])
for i in range(1,N-1):
    cand.append(fractions.gcd(X[i-1],Y[i+1]))

print(max(cand))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

n = int(input())
aaa = list(map(int, input().split()))
cnt_l = [0] * (n - 1)
cnt_r = [0] * (n - 1)

cnt_l[0] = aaa[0]
for i in range(1, n - 1):
    cnt_l[i] = gcd(cnt_l[i - 1], aaa[i])

aaa.reverse()
cnt_r[0] = aaa[0]
for i in range(1, n - 1):
    cnt_r[i] = gcd(cnt_r[i - 1], aaa[i])

cnt_l = [cnt_r[-1]] + cnt_l
cnt_r = [cnt_l[-1]] + cnt_r
cnt_r.reverse()

ans = 1
for i in range(n):
    tmp = gcd(cnt_l[i], cnt_r[i])
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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

# 累積GCD
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:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))

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

Submission status: Accepted

Solution code:
from fractions import gcd
import numpy as np
n=int(input())
data=list(map(int,input().split()))
left=np.zeros(n+1,dtype=np.int)
right=np.zeros(n+1,dtype=np.int)
kotae=1
for i in range(n):
    left[i+1]=gcd(left[i],data[i])
    right[n-i-1]=gcd(right[n-i],data[n-i-1])
for j in range(n):
    num=gcd(left[j],right[j+1])
    kotae=max(num,kotae)
print(kotae)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
l = [a[0]] * n
r = [a[n-1]] * n
for i in range(1, n):
    l[i] = gcd(l[i-1], a[i-1])
for i in range(n-2, -1, -1):
    r[i] = gcd(r[i+1], a[i+1])
l[0] = r[0]
r[n-1] = l[n-1]
ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i], r[i]))
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])
    r[n-i-1] = gcd(r[n-i],a[n-i-1])

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