Problem:


Score : 300 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, written on the blackboard.

You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.

Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Sample Input 1

3
7 6 8

Sample Output 1

2

If we replace 7 with 4, the greatest common divisor of the three integers on the blackboard will be 2, which is the maximum possible value.

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
#N = 2
#A = [1000000000,1000000000]

def check_yakusuu(n):
    list_yakusuu = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            if i != n//i:
                list_yakusuu.append(i)
                list_yakusuu.append(n//i)
            else:
                list_yakusuu.append(i)
    list_yakusuu.sort(reverse = True)
    return list_yakusuu
ans = []
for i in range(2):
    list_yakusuu = check_yakusuu(A[i])
    for j in list_yakusuu:
        tmp = 0
        for k in range(N):
            if A[k] % j == 0:
                tmp += 1
        if tmp >= N - 1:
            ans.append(j)
            break
print(max(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()))

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

  L = [0 for j in range(N+1)]
  R = [0 for j in range(N+1)]
  
  for j in range(N):
    L[j+1] = gcd(L[j], A[j])
  for j in reversed(range(N)):
    R[j] = gcd(R[j+1], A[j])

    m = -1
  for j in range(N):
    m = max(m, gcd(L[j], R[j+1]))
  print(m)

Submission status: Accepted

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

a = [0] + a + [0]


lef = [0] * (N + 2)
rig = [0] * (N + 2)
def gcd(a, b):
    if a * b == 0:
        return a + b
    elif a % b == 0:
        return b
    else:
        return gcd(b, a % b)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N = ii()
A = lmi()
Leftgcd = list(accumulate(A, gcd))
Rightgcd = list(accumulate(reversed(A), gcd))
Leftgcd.insert(0, 0)
Rightgcd.insert(0, 0)
maxgcd = [1]
for i in range(N):
    maxgcd.append(gcd(Leftgcd[i], Rightgcd[N - 1 - i]))
print(max(maxgcd))

Submission status: Accepted

Solution code:
import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N = ii()
A = lmi()
Leftgcd = list(accumulate(A, gcd))
Rightgcd = list(accumulate(reversed(A), gcd))
Leftgcd.insert(0, 0)
Rightgcd.insert(0, 0)
maxgcd = 1
for i in range(N):
    maxgcd = max(maxgcd, gcd(Leftgcd[i], Rightgcd[N - 1 - i]))
print(maxgcd)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
A = list(map(int,input().split()))
left = [0]*(n+1)
right = [0]*(n+2)
for a,aa,i in zip(A,A[::-1],range(1,n+1)):
    left[i] = gcd(a,left[i-1])
    right[n+1-i] = gcd(aa,right[n-i+2])
ans = 1
for i in range(1,n+1):
    if i ==1:
        if ans < right[i+1]:
            ans = right[i+1]
    elif i == n:
        if ans < left[i-1]:
            ans = left[i-1]
    else:
        if ans < gcd(left[i-1],right[i+1]):
            ans = gcd(left[i-1],right[i+1])

print(ans)

Submission status: Accepted

Solution code:
def gcd(x, y):
    if x * y == 0:
        return (x+y)
    x, y = max(x, y), min(x, y)
    while y > 0:
        r = x % y
        x, y = y, r
    return x

n = int(input())
a = [int(i) for i in input().split()]
l_list = [0]
r_list = [0]
for i in range(n):
    l = gcd(l_list[i], a[i])
    l_list.append(l)
    r = gcd(r_list[-1], a[-i-1])
    r_list.append(r)
r_list = list(reversed(r_list))
r_list = r_list[1:]
l_list = l_list[:n]
c_list = []
for i in range(n):
    c_list.append(gcd(l_list[i], r_list[i]))
print(max(c_list))

Submission status: Accepted

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

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

L = [0]
for i in range(0, N):
  L.append(gcd(A[i], L[-1]))
  
R = [0]
for i in range(N-1, -1, -1):
  R.append(gcd(A[i], R[-1]))
R = list(reversed(R))
#print(L)
#print(R)

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

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
left = [0]*n
right = [0]*n
for i in range(1,n):
    left[i] = gcd(left[i-1],a[i-1])
    right[-1-i] = gcd(right[-i],a[-i])
gcds = []
for i in range(n):
    gcds.append(gcd(left[i],right[i]))
print(max(gcds))

Submission status: Accepted

Solution code:
import fractions

argN = int(input())
argA = list(map(int,input().split()))

aryL = [0] * argN
aryR = [0] * argN
aryL[0] = argA[0]
aryR[argN-1] = argA[argN-1]

for i in range(1,argN):
  aryL[i] = fractions.gcd(aryL[i-1],argA[i])
  aryR[argN-1-i] = fractions.gcd(aryR[argN-i],argA[argN-1-i])

maxGcd = 0
for i in range(argN):
  if i == 0:
    wkGcd = aryR[1]
  elif i == argN - 1:
    wkGcd = aryL[argN - 2]
  else:
    wkGcd = fractions.gcd(aryL[i-1],aryR[i+1])
  if maxGcd < wkGcd:
    maxGcd = wkGcd

print(maxGcd)

Submission status: Accepted

Solution code:
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())
A = [int(x) for x in input().split()]
L = [0]*N
R = [0]*N
ans = 0
for i in range(N):
    if(i==0):
        L[i] = A[0]
        R[i] = A[-1]
    else:
        L[i] = gcd(A[i],L[i-1])
        R[i] = gcd(A[-i-1],R[i-1])

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

Submission status: Accepted

Solution code:
from functools import reduce
import collections 
import fractions
import math
import copy

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    A = list(int(_) for _ in input().split())
    ans = 0
    R = [0]*N
    R[0] = A[0]
    L = [0]*N
    L[N-1] = A[N-1]
    for i in range(1,N):
        R[i] = fractions.gcd(R[i-1],A[i])
    for i in range(N-1,0,-1):
        L[i-1] = fractions.gcd(L[i],A[i-1])        
    X = []
    for i in range(N):
        if i == 0:
            X.append(L[1])
        elif i == N-1:
            X.append(R[N-2])
        else:
            X.append(fractions.gcd(R[i-1],L[i+1]))
    print(max(X))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from fractions import gcd
gcds_ascendant = [-1, a[0]]
for i in range(1, N-1):
    gcds_ascendant.append(gcd(gcds_ascendant[-1], a[i]))

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

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

print(ans)

# print(gcds_ascendant)
# print(gcds_descendant)

Submission status: Accepted

Solution code:
#最大公約数を求める再帰関数-->計算量O(log(max(x))
def gcd1(x, y):
    if x < y:
        x, y = y, x
    if y == 0:
        return x
    return gcd(x-y, y)

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


#本文
N = int(input())
list_A = list(map(int, input().split()))

#配列初期化
list_gcd = [0] * N
list_gcd_rev = [0] * N

#以下　間違いを発見できず

##配列の最初のgcdを求める。定義
#list_gcd[0] = list_A[0]
#list_gcd_rev[N-1] = list_A[N-1]
##print (list_gcd, list_gcd_rev)

##配列にgcdを代入していく
#for i in range(1,N):
#    list_gcd[i] = gcd(list_gcd[i-1], list_A[i])
##print (list_gcd)
#for j in range(1,N):
#    list_gcd_rev[N-1-j] = gcd(list_gcd_rev[N-j], list_A[N-1-j])
##print (list_gcd_rev)

##print (list_gcd, list_gcd_rev)

##k番目までの両端からのgcdを求める
#if N == 2:
#    ans = gcd(list_gcd[0], list_gcd_rev[1])
#else:
#    ans = max(list_gcd[N-2], list_gcd_rev[1]) #両端の文字を除いたときの答え
##print (ans)
#for k in range(1,N-1):
#    a = list_gcd[k-1]
#    b = list_gcd_rev[k+1]
#    ans = max(ans, gcd(a, b))
#print (ans)

#以下、正答

for i in range(1,N):
    list_gcd[i]=gcd(list_gcd[i-1],list_A[i-1])
for i in range(N-1)[::-1]:
    list_gcd_rev[i]=gcd(list_gcd_rev[i+1],list_A[i+1])
Z = [gcd(list_gcd[i], list_gcd_rev[i]) for i in range(N)]
print (max(Z))

Submission status: Accepted

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

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

l = []
r = []

for i in range(n):
    if i == 0:
        l.append(a[0])
        r.append(a[n-1])
    else:
        l.append(gcd(l[i-1],a[i]))
        r.append(gcd(r[i-1],a[n-i-1]))

r.reverse()
ans = max(l[n-2],r[1])

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

print(ans)

Submission status: Accepted

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

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

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

merge = [gcd(left[i],right[-i-1]) for i in range(n)]

print(max(merge))

Submission status: Accepted

Solution code:
import fractions


def solute(n, a):
    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]

    ans = []
    for i in range(n):
        ans.append(fractions.gcd(gcd_left[i], gcd_right[i+1]))
    return max(ans)


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

Submission status: Accepted

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

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

# 入力
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])
for i in reversed(range(n)):
    right[i] = gcd(right[i+1], a[i])

# print(left)
# print(right)

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


def main():
    N = int(input())
    A = list(map(int, input().split()))
    left = [0] * N
    right = [0] * N
    for i in range(1, N):
        left[i] = gcd(left[i-1], A[i-1])
        right[-1-i] = gcd(right[-i], A[-i])
    gcds = []
    for i in range(N):
        gcds.append(gcd(left[i], right[i]))
    print(max(gcds))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


def solve(N: int, A: "List[int]"):
    tmp = A[0]
    l = []
    for a in A:
        tmp = gcd(tmp, a)
        l.append(tmp)
    tmp = A[-1]
    r = []
    for a in A[::-1]:
        tmp = gcd(tmp, a)
        r.append(tmp)
    r.reverse()
    ret = 0
    for i in range(N):
        if i < 1:
            tmp = r[i + 1]
        elif i >= N - 1:
            tmp = l[i - 1]
        else:
            tmp = gcd(l[i - 1], r[i + 1])
        ret = max(ret, tmp)
    print(ret)
    return


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:
# -*- coding: utf-8 -*-
import fractions

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


gcd = fractions.gcd


left = [0] * N
right = [0] * N
for i in range(N):
    if i == 0:
        left[0] = A[0]
        right[N-1] = A[-1]
        continue

    left[i] = gcd(left[i-1], A[i])
    right[N-i-1] = gcd(right[N-i], A[N-i-1])

max_gcd = right[1]
for i in range(N):
    if i == 0:
        continue
    elif i == N - 1:
        if max_gcd < left[-2]:
            max_gcd = left[-2]
    else:
        target = gcd(left[i-1], right[i+1])
        if max_gcd < target:
            max_gcd = target

print(max_gcd)

Submission status: Accepted

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


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

import sys
import math
p=10
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[j]%i!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[j]%x!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and x>ans: ans=x

R=a[p]
for i in range(p+1,N):
    R=gcd(R,a[i])

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

print(ans)

Submission status: Accepted

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

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

import sys
p=40
N=int(input())
if p>N: p=N
a=list(map(int,input().split()))

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

print(ans)

Submission status: Accepted

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

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

import sys
p=50
N=int(input())
if p>N: p=N
a=list(map(int,input().split()))

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

print(ans)

Submission status: Accepted

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

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

import sys
p=50
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()

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

print(ans)

Submission status: Accepted

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

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

import sys
p=100
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()

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

print(ans)

Submission status: Accepted

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


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

import sys
import math
p=100
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

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

print(ans)

Submission status: Accepted

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


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

import sys
import math
p=100
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0


R=a[p]
for i in range(p,N):
    r=gcd(R,a[i])

if r>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Accepted

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

d = set()
for aa in a[0], a[1]:
    for i in range(1, int(aa ** 0.5) + 1):
        if aa % i == 0:
            d.add(i)
            d.add(aa // i)  # i == aa//iのときは重複する
# aの2要素の約数全列挙

# print(d)

g = 1
for dd in d:
    cnt = 0
    for aa in a:
        if aa % dd == 0:
            cnt += 1
    if cnt >= N - 1:
        # N-1個以上の要素を割るなら、求める最大公約数足り得る
        g = max(g, dd)
print(g)


# def is_p(x):
#     if x <= 1: return False
#     for i in range(2, int(x ** 1 / 2) + 1):
#         if x % i == 0:
#             return False
#     else:
#         return True
#
#
# b = (i for i in range(100) if is_p(i))
# t = 1
# for i, bb in enumerate(b, 1):
#     t *= bb
#     t, i
#     if t > 10 ** 9:
#         bb
#         break
# (2, 1)
# (6, 2)
# (30, 3)
# (210, 4)
# (2310, 5)
# (30030, 6)
# (510510, 7)
# (9699690, 8)
# (223092870, 9)
# (6469693230, 10)
# 29
# 小さい方から9個の素数の積で、10**9以内の最大数となる

# 数列で最小の値が素数9個の積で、
# 次に小さい値も重複しない素数9個の積の場合でも、
# 全約数は、
# 2 * 2 ** 9個なので、
# 10**5個の要素に対する全探索が間に合う

Submission status: Accepted

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

d = set()
for aa in a[0], a[1]:
    for i in range(1, int(aa ** 0.5) + 1):
        if aa % i == 0:
            d.add(i)
            d.add(aa // i)  # i == aa//iのときは重複する
# aの2要素の約数全列挙

# print(d)

g = 1
for dd in d:
    cnt = 0
    for aa in a:
        if aa % dd == 0:
            cnt += 1
    if cnt >= N - 1:
        # N-1個以上の要素を割るなら、求める最大公約数足り得る
        g = max(g, dd)
print(g)


# def is_p(x):
#     if x <= 1: return False
#     for i in range(2, int(x ** 1 / 2) + 1):
#         if x % i == 0:
#             return False
#     else:
#         return True
#
#
# b = (i for i in range(100) if is_p(i))
# t = 1
# for i, bb in enumerate(b, 1):
#     t *= bb
#     t, i
#     if t > 10 ** 9:
#         bb
#         break
# (2, 1)
# (6, 2)
# (30, 3)
# (210, 4)
# (2310, 5)
# (30030, 6)
# (510510, 7)
# (9699690, 8)
# (223092870, 9)
# (6469693230, 10)
# 29
# 小さい方から9個の素数の積で、10**9以内の最大数となる

# 数列で最小の値が素数9個の積で、
# 次に小さい値も重複しない素数9個の積の場合、
# それら素数18個からなる全約数は、
# 2 ** (9 * 2)個あり、
# これら全てについて、10**5個の要素に対し、割り切れるかを試すとTLEになる。
# ただ、10**5個の要素の素因数分解で現れる素数が全く重ならないということは、
# 鳩ノ巣から考えられないんだと思う
# 配列aから2つの要素を取り出したときの、それぞれの約数を全列挙したものの和集合の要素数は、
# 具体的に幾つと見積もればいいのだろうか

Submission status: Accepted

Solution code:
import unittest
import fractions


def solution(n, a):
    gcd_left = [0]
    gcd_right = [0]
    for i in range(n):
        gcd_left.append(fractions.gcd(gcd_left[i], a[i]))
        # 順に(0とa[-1]), (a[-1]とa[-2]),...の比較
        # 要は右端から順にgcdを求めている
        gcd_right.append(fractions.gcd(gcd_right[i], a[-(i + 1)]))

    gcd_right = gcd_right[::-1]  # gcd_right[i]がi番目以降のgcdとなるように反転

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


    return max(ans)


class MyTestCase(unittest.TestCase):
    def test1(self):
        self.assertEqual(solution(3, [7, 6, 8]), 2)

    def test2(self):
        self.assertEqual(solution(3, [12, 15, 18]), 6)

    def test3(self):
        self.assertEqual(solution(2, [1000000000, 1000000000]), 1000000000)




if __name__ == '__main__':

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

    unittest.main()

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.append(math.gcd(left[i],a[i]))
    left[i + 1] = (fractions.gcd(left[i],a[i]))
    #right.insert(0,math.gcd(right[0],a[n - 1 - i]))
    right[n - i - 1] = (fractions.gcd(right[n - i],a[n - 1 - i]))
#print(left)
#print(right)

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

Submission status: Accepted

Solution code:
from sys import exit
from fractions import gcd


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

# List if length of 2 or shorter
if len(A) <= 2:
    print(max(A))
    exit()

# Left Side = [A0, 0, 0, 0, 0]
left_side = [0 for _ in range(N)]
left_side[0] = A[0]

# Right Side = [0, 0, 0, 0, An]
right_side = [0 for _ in range(N)]
right_side[-1] = A[-1]

for i in range(N - 1):  # DP: L1 = gcd(L0, A1); Maximum GCD on very RIGHT of list  (Dir -->)
    left_side[i + 1] = gcd(left_side[i], A[i + 1])

for i in range(1, N):   # DP: Rn-2 = gcd(An-2, Rn-1); Maximum GCD on very LEFT of list  (Dir <--)
    right_side[-1 * (i+1)] = gcd(A[-1*(i+1)], right_side[-1*i])

max_gcd = 1

# Left
max_gcd = max(max_gcd, right_side[1])
# Max of Right and Left
max_gcd = max(max_gcd, left_side[-2])

for i in range(1, N - 1):
    left = left_side[i - 1]
    # We exclude the number at i here, and compare whether new gcd is greater than previous
    right = right_side[i + 1]

    max_gcd = max(max_gcd, gcd(left, right))

print(max_gcd)

Submission status: Accepted

Solution code:
from sys import stdin, exit
from fractions import gcd


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

# List if length of 2 or shorter
if len(A) <= 2:
    print(max(A))
    exit()

# Left Side = [A0, 0, 0, 0, 0]
left_side = [0 for _ in range(N)]
left_side[0] = A[0]

# Right Side = [0, 0, 0, 0, An]
right_side = [0 for _ in range(N)]
right_side[-1] = A[-1]

for i in range(N - 1):  # DP: L1 = gcd(L0, A1); Maximum GCD on very RIGHT of list  (Dir -->)
    left_side[i + 1] = gcd(left_side[i], A[i + 1])

for i in range(1, N):   # DP: Rn-2 = gcd(An-2, Rn-1); Maximum GCD on very LEFT of list  (Dir <--)
    right_side[-1 * (i+1)] = gcd(A[-1*(i+1)], right_side[-1*i])

max_gcd = 1

# Left
max_gcd = max(max_gcd, right_side[1])
# Max of Right and Left
max_gcd = max(max_gcd, left_side[-2])

for i in range(1, N - 1):
    left = left_side[i - 1]
    # We exclude the number at i here, and compare whether new gcd is greater than previous
    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
N = int(input())
A = list(map(int, input().split()))
B, C = [A[0]], [A[N - 1]]

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

AA = list(reversed(A))
for i in range(1, N):
    C.append(gcd(C[i - 1], AA[i]))
C.reverse()
ans = 0
for i in range(1, N - 1):
    ans = max(ans, gcd(B[i - 1], C[i + 1]))
ans = max(ans, B[N - 2], C[1])
print(ans)

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:
try:
    from fractions import gcd
except:
    from math import gcd
N = int(input())
A = list(map(int, input().split()))


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


def get(n, change_dict):
    if n < 0 or N <= n:
        return 0
    if n in change_dict:
        return
    else:
        return A[n]


gcd_left = [0]  # i番目以下の最大公約数
gcd_tmp_val = 0
for i in range(N):
    gcd_tmp_val = gcd_custom(gcd_tmp_val, A[i])
    gcd_left.append(gcd_tmp_val)

gcd_right_reversed = [0]  # 右からi番目==(N-1-i)番目 の最大公約数
gcd_tmp_val = 0
for i in range(N - 1, -1, -1):
    gcd_tmp_val = gcd_custom(gcd_tmp_val, A[i])
    gcd_right_reversed.append(gcd_tmp_val)

ans = 1
for i in range(N):
    ans = max(ans,
              gcd_custom(gcd_left[i], gcd_right_reversed[N - 1 - i])
              )
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float('inf')
MOD = 10**9+7

n = int(input())
A = list(map(int,input().split()))
ass = set()
def div(x):
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            ass.add(i)
            ass.add(x//i)
    return ass
a0 = A[0]
a1 = A[1]
div(a0)
div(a1)
ans = []
for i in ass:
    cnt = 0
    for a in A:
        if a%i == 0:
            cnt += 1
    if cnt >= n-1:
        ans.append(i)
print(max(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float('inf')
MOD = 10**9+7

n = int(input())
A = list(map(int,input().split()))
ass = set()
def div(x):
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            ass.add(i)
            ass.add(x//i)
    return ass
a0 = A[0]
a1 = A[1]
div(a0)
div(a1)
ans = 1
for i in ass:
    cnt = 0
    for a in A:
        if a%i == 0:
            cnt += 1
    if cnt >= n-1:
        ans = max(ans,i)
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)
    #[p,q)のgcd
    def query(p,q):
        if p>n-1 or q<1:
            return 0
        if abs(q-p)<=1:
            return a[p]
        p += num-1
        q += num-2
        res=0
        while q>p:
            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
        res = gcd(res,seg[p])
        return res

    n = int(input())
    a = tuple(map(int,input().split()))
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[0]*2*num

    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]) 

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

ass = set()
def div(x):
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            ass.add(i)
            ass.add(x//i)
    return ass

a0 = A[0]
a1 = A[1]
div(a0)
div(a1)
ans = []
for i in ass:
    cnt = 0
    for a in A:
        if a%i == 0:
            cnt += 1
    if cnt >= n-1:
        ans.append(i)
print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

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

# 先頭から連続する要素の最大公約数の列
L = list(accumulate(A, gcd))
# 末尾から連続する要素の最大公約数
R = list(accumulate(reversed(A), gcd))

# Aの各要素について、それを使用しない場合の最大公約数の最大値をL, Rを用いて求める
ans = max(
    L[-2],
    R[-2],
    max(
        (
            gcd(L[k], R[-(k + 3)])
            for k in range(N - 2)
        ),
        default=L[-1]
    )
)

# 出力
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

N = int(input())
A = [i for i in map(int,input().split())]
L = [0]
R = [0]
for i in range(N):
    L.append(gcd(L[-1],A[i]))
for i in range(N-1,-1,-1):
    R.append(gcd(R[-1],A[i]))
R.reverse()
g = []
for i in range(N):
    g.append(gcd(L[i],R[i+1]))
print(max(g))