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

left = [0] * n
right = [0] * n

ans = 0

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

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

print(ans)

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

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

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

ans = 0
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
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
B = list(accumulate(A, gcd))
C = list(accumulate(A[::-1], gcd))[::-1]
C = C[2:] + C[:2]
B[-1] = C[-1]
C[-2] = B[-2]
print(max(map(gcd, B, C)))

Submission status: Accepted

Solution code:
# coding: utf-8
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
l1 = [0] * N
l2 = [0] * N
for i in range(1, N):
    l1[i] = gcd(l1[i-1], A[i-1])
for i in range(N-1)[::-1]:
    l2[i] = gcd(l2[i+1], A[i+1])
ans = 0
for i in range(N):
    ans = max(ans, gcd(l1[i], l2[i]))
print(ans)

Submission status: Accepted

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


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


init(A)
ans = 0
for i in range(N):
    ans = max(ans, fractions.gcd(query(0, i), query(i+1, N)))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

ans=[]

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

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

print(max(ans))

Submission status: Accepted

Solution code:
#ABC-125-C
N = int(input())
A = list(map(int, input().split())) #[0, 1, 2, ..., N-2, N-1]
L = [0] * N #L[0]とL[N-1]は0から変わらない。N=5なら実行終了時にL=[*0*,a,b,c,*0*]となる。
R = [0] * N #R[0]とR[N-1]は0から変わらない。N=5なら実行終了時にR=[*0*,f,e,d,A[4]]となる。

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

ans_gcd = -1

#Lから埋める
L[0] = A[0]
check_gcd = L[0]
for i in range(1, N-1): #N=5のときはi=1~3を実施して最終的にL=[0,a,b,c,0]となる。
    check_gcd = gcd(check_gcd, A[i])
    L[i] = check_gcd

#Rを埋める
R[-1] = A[-1]
check_gcd = R[-1]
for i in reversed(range(1, N-1)):#N=5のときはi=3~1を実施して最終的にR=[0,f,e,d,0]となる。
    check_gcd = gcd(check_gcd, A[i])
    R[i] = check_gcd

#端以外を書き換えの対象とした場合の最大公約数のMaxを探す。
for i in range(1, N-1):
    m = gcd(L[i-1], R[i+1])
    ans_gcd = max(ans_gcd, m)

#端と比べて最終的な答えを出す。N>2のときは数字が低い方を消すだけ。
if N > 2:
    ans_gcd = max(ans_gcd, gcd(A[-2], L[N-3]), gcd(A[1], R[2]))
else:
    ans_gcd = max(A)

print(ans_gcd)

Submission status: Accepted

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

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

# 1個の変える先は他のやつの最大公約数にすればいいので、
# N-1個の最大公約数の最大値を求める
lefts = list(itertools.accumulate(A, gcd))
rights = list(itertools.accumulate(A[::-1], gcd))[::-1]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

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

from fractions import gcd

l_gcd = [0 for _ in range(n)]
r_gcd = [0 for _ in range(n)]

for i in range(n):
    l_gcd[i]=gcd(l_gcd[i-1],a[i])
for i in range(n-1,-1,-1):
    if i == n-1:
        r_gcd[i]=a[i]
    else:
        r_gcd[i]=gcd(r_gcd[i+1],a[i])
ret = 1

for i in range(n):
    if i==0:
        ret = max(ret,gcd(0,r_gcd[i+1]))
    elif i==n-1:
        ret = max(ret,gcd(l_gcd[i-1],0))
    else:
        ret = max(ret,gcd(l_gcd[i-1],r_gcd[i+1]))
print(ret)

Submission status: Accepted

Solution code:
#c
n=int(input())
a=[int(i) for i in input().split()]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
l=[1]*n
r=[1]*n
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-i-1])
if n>=3:
    ans = max(l[-2],r[-2],max(gcd(l[i-1],r[n-i-2]) for i in range(1,n-1)))
    print(ans)
else:
    print(max(a))

Submission status: Accepted

Solution code:
import math
from itertools import accumulate
from fractions import gcd

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

L = [0]+list(accumulate(a, gcd))
R = list(accumulate(reversed(a), gcd))[::-1]+[0]


ans = 0

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

if n == 2:
    print(max(a))
else:
    print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
list_ = list(map(int, input().strip().split()))

gcd_from_left = [0]
gcd_from_right = [0]
for i in range(n):
    gcd_from_left.append(gcd(gcd_from_left[i], list_[i]))
    gcd_from_right.append(gcd(gcd_from_right[i], list_[-(i + 1)]))

gcd_from_left.insert(0, 0)
gcd_from_right.insert(0, 0)
gcd_from_right.reverse()

print(max(gcd(gcd_from_left[i], gcd_from_right[i]) for i in range(n + 2)))

Submission status: Accepted

Solution code:
from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    
    ans = 0
    left = [0 for _ in range(N+1)]
    right = [0 for _ in range(N+1)]
    for i in range(N):
        left[i+1] = gcd(left[i], A[i])
    for i in range(N-1, -1, -1):
        right[i] = gcd(right[i+1], A[i])
    for i in range(N):
        ans = max(ans, gcd(left[i], right[i+1]))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def gcd(a,b):
    while b>0:a,b=b,a%b
    return a

def main():
    n=int(input())
    aa=LI()
    gl=[0]*n
    gr=[0]*n
    g=aa[0]
    for i,a in enumerate(aa):
        g=gcd(g,a)
        gl[i]=g
    g=aa[-1]
    for i,a in enumerate(aa[::-1]):
        g=gcd(g,a)
        gr[n-1-i]=g
    ans=max(gl[n-2],gr[1])
    for i in range(1,n-1):
        g=gcd(gl[i-1],gr[i+1])
        if g>ans:ans=g
    print(ans)

main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

g1 = [0]*N
g2 = [0]*N

g1[0] = a[0]
g2[N-1] = a[N-1]

for i in range(1, N):
    g1[i] = gcd(a[i-1], g1[i-1])
    g2[N-1-i] = gcd(a[N-i], g2[N-i])
    
g1[0] = g2[0]
g2[N-1] = g1[N-1]

g = [gcd(g1[i], g2[i]) for i in range(N)]
print(max(g))

Submission status: Accepted

Solution code:
# coding: utf-8
import fractions
N=int(input())
A=list(map(int,input().split()))
GL=[0]*N
GR=[0]*N
#初期値
GL[0]=A[0]
GR[N-1]=A[N-1]
#左から累積gcd
for i in range(N-1):
    GL[i+1]=fractions.gcd(GL[i],A[i+1])
#右から累積gcd
for i in range(N-1,0,-1):
    GR[i-1]=fractions.gcd(GR[i],A[i-1])

#print(GL,GR)

G=0
for i in range(1,N-1):
    G=max(fractions.gcd(GL[i-1],GR[i+1]),G)
    
print(max(G,GR[1],GL[N-2]))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    gcd = fractions.gcd
    N = I()
    A = LI()
    left = [1] * N
    right = [1] * N
    left[0] = A[0]
    right[N-1] = A[N-1]
    ans = -1

    for i in range(1, N):
        left[i] = gcd(A[i], left[i-1])
    for j in range(N-2, -1, -1):
        right[j] = gcd(A[j], right[j+1])
    for i in range(N):
        if i-1<0:
            ans = max(ans, right[i+1])
            continue
        if i+1 >= N:
            ans = max(ans, left[i-1])
            continue
        ans = max(ans, gcd(left[i-1], right[i+1]))

    print(ans)

main()


'''

N = int(input())
S = list(input())

ans = 0
s_count = 0
if len(S) == 1:
    print(ans)
elif len(S) == 2:
    if S == ['#', '.']:
        print("1")
    else:
        print("0")
elif len(S) == 3:
    for i in range(len(S)-1):
        if S[i] == '#' and S[i+1] == '.':
            ans += 1
    print(ans)
            
else:
    for c in S[:-1]:
        if c=='#':
            s_count += 1
    for i in range(len(S)-3):
        if S[i:i+4] == ['.','#','.','.']:
            S[i:i+4] = ['.','.','.','.']
            
        elif S[i:i+4] == ['.','#','.','#']:
            S[i:i+4] = ['.','#','#','#']

        elif S[i:i+4] == ['#','#','.','.']:
            S[i:i+4] = ['#','#','#','.']

        elif S[i:i+4] == ['#','#','.','#']:
            S[i:i+4] = ['#','#','#','#']
        else:
            continue
        ans += 1

    print(min(s_count, ans, len(S)-s_count))
print(S)
'''

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = list(map(int, input().split()))
B = [0]*N
B[0] = A[0]
for i in range(1, N-1):
    B[i] = fractions.gcd(A[i], B[i-1])

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

ans = max(B[N-2], C[1])
for i in range(N-2):
    ans = max(ans, fractions.gcd(B[i], C[i+2]))
print(ans)

Submission status: Accepted

Solution code:
# 参考1: https://atcoder.jp/contests/abc125/submissions/8965716
# 参考2: https://qiita.com/hkrutknouch/items/e71488de4a0c8e83ee97

from fractions import gcd
from itertools import accumulate

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

left = list(accumulate(A, gcd))
right = list(accumulate(A[::-1], gcd))[::-1]

ans = 0
for i in range(n):
  if i == 0:
    tmp = right[1]
  elif i == n - 1:
    tmp = left[-2]
  else:
    tmp = gcd(left[i-1], right[i+1])
  ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import fractions
N=int(input())
ls=[int(s) for s in input().split()]
gcd_l=[0 for _ in range(N+1)]
gcd_l[0]=ls[0]
gcd_r=[0 for _ in range(N+1)]
gcd_r[N-1]=ls[N-1]
for i in range(N-1):
  gcd_l[i+1]=fractions.gcd(gcd_l[i],ls[i+1])
  gcd_r[N-i-2]=fractions.gcd(gcd_r[N-i-1],ls[N-i-2])
ans=set()
for i in range(N):
  ans.add(fractions.gcd(gcd_l[i-1],gcd_r[i+1]))
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import accumulate
from fractions import gcd


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

cum_gcd_l = list(accumulate(A, gcd))
cum_gcd_r = list(accumulate(reversed(A), gcd))[::-1]

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from fractions import gcd


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

cum_gcd_l = list(accumulate(A, gcd))
cum_gcd_r = list(accumulate(reversed(A), gcd))

ans = 0
for i in range(N):
    if i == 0:
        tmp = cum_gcd_r[-2]
    elif i == N-1:
        tmp = cum_gcd_l[-2]
    else:
        tmp = gcd(cum_gcd_l[i-1], cum_gcd_r[N-i-2])
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
def gcd(a,b):
  if b == 0:
    return a
  return gcd(b,a%b)
L = [1]*n
R = [1]*n
L[0] = A[0]
R[n - 1] = A[-1]
for i in range(1,n):
  L[i] = gcd(L[i - 1],A[i])
  R[n - i - 1] = gcd(R[n - i],A[-1 - i])
m = 1
for i in range(0,n-2):
  m = max(m,gcd(L[i],R[i + 2]))
print(max(L[n - 2],m,R[1]))

Submission status: Accepted

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

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

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

memo1 = 10**9
memo2 = 10**9

lf = [0 for i in range(n)]
rgt = [0 for i in range(n)]

lf[0] = a[0]
rgt[0] = a[n-1]

for i in range(1,n):
	lf[i] = gcd(lf[i-1],a[i])
	rgt[i] = gcd(rgt[i-1],a[i*(-1)-1])


mx = 0
mx = max(mx,lf[n-2])
mx = max(mx,rgt[n-2])

for i in range(1,n-1):
	mx = max(mx,gcd(lf[i-1],rgt[i*(-1)-2]))

print(mx)

Submission status: Accepted

Solution code:
import copy
import fractions
N=int(input())
A=list(map(int,input().split()))
ans=[]
L=[0 for i in range(N)]
R=[0 for i in range(N)]
for i in range(N):
  if i != 0:
    L[i]=fractions.gcd(L[i-1],A[i-1])
    R[N-1-i]=fractions.gcd(R[N-i],A[N-i])

for i in range(N):
  ans.append(fractions.gcd(L[i],R[i]))

print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
def gc(a,b):
  if a==0 or b==0:
    return max(a,b)
  else:
    return gcd(a,b)
n=int(input())
a=list(map(int,input().split()))
a=[0]+a+[0]
lgcd=[0]
rgcd=[0]
for i in range(1,n):
  lgcd.append(gc(a[i],lgcd[-1]))
  rgcd.append(gc(a[-i-1],rgcd[-1]))
GCD=0
for i in range(n):
  GCD=max(GCD,gc(lgcd[i],rgcd[-i-1]))
print(GCD)

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
b=[0]*n
c=[0]*n
b[0]=a[0]
c[-1]=a[-1]
for i in range(1,n):b[i]=gcd(b[i-1],a[i])
for i in range(n-2,-1,-1):c[i]=gcd(c[i+1],a[i])
ans=max(c[1],b[-2])
for i in range(1,n-1):ans=max(ans,gcd(b[i-1],c[i+1]))
print(ans)

Submission status: Accepted

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


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

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

ans = gcd_from_right[1]
gcd_from_left = A[0]
for i in range(1, N-1):
    ans = max(ans, gcd(gcd_from_left, gcd_from_right[i+1]))
    gcd_from_left = gcd(gcd_from_left, A[i])
ans = max(ans, gcd_from_left)
print(ans)

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
def init(init_val,n):
    #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 segfunc(x,y):
    return gcd(x,y)

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
N = int(input())
a = list(map(int,input().split()))
#####単位元######
ide_ele = 0

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

init(a,N)
res = 0
for i in range(N):
    tmp = gcd(query(0,i),query(i+1,N))
    if tmp >= res:
        res = tmp
print(res)

Submission status: Accepted

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

gl=[0]*n
gl[0]=a[0]
gr=[0]*n
gr[-1]=a[-1]
for i in range(1,n):
    gl[i]=gcd(gl[i-1],a[i])
    gr[-i-1]=gcd(gr[-i],a[-i-1])
ans=max(gr[1],gl[-2])
for i in range(1,n-1):
    ans=max(ans,gcd(gl[i-1],gr[i+1]))
print(ans)

Submission status: Accepted

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

gl=[0]*n
gl[0]=a[0]
gr=[0]*n
gr[-1]=a[-1]
for i in range(1,n):
    gl[i]=gcd(gl[i-1],a[i])
    gr[-i-1]=gcd(gr[-i],a[-i-1])
ans=0
for i in range(n):
    if i==0:
        ans=gr[1]
    elif i==n-1:
        ans=max(ans,gl[i-1])
    else:
        ans=max(ans,gcd(gl[i-1],gr[i+1]))
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

N = int(input()) 
A = [0] + list(map(int, input().split()))

# L[i]: gcd(A1,...,Ai)
# R[i]: gcd(Ai,...,AN)
L = [0]*(N+2)
R = [0]*(N+2)

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

res = 0
for i in range(1, N+1):
    rm_i = gcd(L[i-1], R[i+1])
    if res < rm_i:
        res = rm_i
print(res)

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import fractions as f

N = int(input())
A = [int(i) for i in input().split()]
L = [A[0]]
for i in range(1, N):
    L.append(f.gcd(L[-1], A[i]))
A.reverse()
R = [A[0]]
for i in range(1, N):
    R.append(f.gcd(R[-1], A[i]))
R.reverse()
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:
        ans = max(ans, f.gcd(L[i - 1], R[i + 1]))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def euclid(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        a,b=b,a%b
        return euclid(a,b)

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

org_A=A[:]
#左から最大公約数作る右もね
A=A[::-1]
l=[A.pop(-1)]
while A:
    l.append(euclid(l[-1],A.pop(-1)))

A=org_A
r=[A.pop(-1)]
while A:
    r.append(euclid(r[-1],A.pop(-1)))
r=r[::-1]

ans=0
#print(l,r)
for i in range(N):
    temp=euclid(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    #print(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    ans=max(ans,temp)

print(ans)

Submission status: Accepted

Solution code:
import fractions
import functools
n = int(input())
*a, = map(int, input().split())

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

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

print(ans)

Submission status: Accepted

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

    if N == 2:
        if A[0] <= A[1]:
            return print(A[1])
        else:
            return print(A[0])
    # 以下 3<=N

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

    ans = 1
    nonneed_idx = -1
    if gcd(A[0], A[1]) > gcd(A[1], A[2]) and gcd(A[0], A[1]) > gcd(A[0], A[2]):
        ans = gcd(A[0], A[1])
        nonneed_idx = 2
    elif gcd(A[0], A[2]) > gcd(A[1], A[2]) and gcd(A[0], A[2]) > gcd(A[0], A[1]):
        ans = gcd(A[0], A[2])
        nonneed_idx = 1
    else:
        ans = gcd(A[1], A[2])
        nonneed_idx = 0

    for i in range(3, N):
        if gcd(ans, A[nonneed_idx]) < gcd(ans, A[i]):
            ans = gcd(ans, A[i])
        else:
            ans = gcd(ans, A[nonneed_idx])
            nonneed_idx = i
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import fractions


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    ls = [[0] * (n + 1) for _ in range(2)]
    for i in range(1, n + 1):
        ls[0][i] = fractions.gcd(ls[0][i-1], a[i-1])
        ls[1][-i-1] = fractions.gcd(ls[1][-i], a[-i])
    mt = 0
    for i in range(n):
        mt = max(mt, fractions.gcd(ls[0][i], ls[1][i+1]))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
i=a[1]
while i > 0:
  flg=0
  for j in a:
    if j%i!=0:
      flg+=1
      if flg>1:
        break
  if flg<=1:
    print(i)
    break
  else:
    i-=1

Submission status: Accepted

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

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

from fractions import gcd
from functools import reduce
import numpy as np

new_gcd = np.frompyfunc(gcd, 2, 1)

a = np.array(a)
left = new_gcd.accumulate(a, dtype=np.object).astype(np.int)
right = new_gcd.accumulate(a[::-1], dtype=np.object).astype(np.int)[::-1]
left = np.append([0], left[:-1])
right = np.append(right[1:], 0)

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

Submission status: Accepted

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
def gcd_l(a):
  tmp=a[0]
  for i in range(len(a)):
    tmp=gcd(tmp,a[i])
  return tmp
tmp=gcd_l(a[1:])
p=set()
for i in range(1,int(a[0]**0.5)+1):
  if a[0]%i==0:
    if i>tmp:
      p.add(i)
    if a[0]//i>tmp:
      p.add(a[0]//i)
if len(p)==0:
  print(tmp)
  exit()
p=sorted(list(p),reverse=True)
for x in p:
  b=[not a[i]%x for i in range(n)]
  if sum(b)==n-1:
    print(x)
    exit()
print(tmp)

Submission status: Accepted

Solution code:
N = int(input())
import fractions

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

gcd_start = [0]
gcd_end = [0]

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

ans = a[-1]
gcd_end.append(ans)
for i in range(-2, -N, -1):
    ans = fractions.gcd(ans, a[i])
    gcd_end.append(ans)

ans_max = 0
for i in range(N):
    ans = fractions.gcd(gcd_end[-i-1], gcd_start[i])
    ans_max = max(ans, ans_max)

print(ans_max)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
gl = [0]
gr = [0]

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

for i in range(N):
    gl.append(gcd(gl[-1],A[i]))
    gr.append(gcd(gr[-1],A[-i-1]))
ans = 1
for i in range(N):
    g = gcd(gl[i],gr[-i-2])
    if ans < g:
        ans = g
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))
L = [1]*n
R = [1]*n
L[0] = A[0]
R[n-1] = A[n-1]
for i in range(1, n):
  L[i] = gcd(L[i-1], A[i])
  R[n-i-1] = gcd(R[n-i], A[n-i-1])
m = 1
for i in range(n-2):
  m = max(m, gcd(L[i], R[i+2]))
print(max(L[n-2], m, R[1]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from fractions import *
def print_ans(N, a_list):
    """Test Case
    >>> print_ans(3, [0, 7, 6, 8, 0])
    2
    >>> print_ans(3, [0, 12, 15, 18, 0])
    6
    >>> print_ans(2, [0, 1000000000, 1000000000,0])
    1000000000
    """
    l_list = [0 for _ in range(N + 2)]
    r_list = [0 for _ in range(N + 2)]
    for i in range(1, N + 1):
        l_list[i] = gcd(l_list[i-1], a_list[i])
    for i in range(N, 0, -1):
            r_list[i] = gcd(r_list[i + 1], a_list[i])
    m_list = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        m_list[i] = gcd(l_list[i - 1],r_list[i+ 1])
    print(max(m_list))

if __name__ == '__main__':
    N = int(input().rstrip())
    a_list = [0] + list(map(int, input().rstrip().split())) + [0]
    print_ans(N, a_list)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 2:
    print(max(a))
    exit()
x = [a[0], gcd(a[0], a[1])]
for i in range(n - 3):
    x.append(gcd(x[i + 1], a[i + 2]))
ans = x[-1]
y = a[-1]
for i in range(1, n - 1):
    z = gcd(y, a[-i])
    ans = max(ans, gcd(x[-i - 1], z))
    y = z
print(max(ans, gcd(y, a[1])))

Submission status: Accepted

Solution code:
from fractions import gcd


def p_c():
    n = int(input())
    *a, = map(int, input().split())
    L = [0] * n
    R = [0] * n
    for i in range(n - 1):
        L[i] = gcd(L[i - 1], a[i])
        R[n - 1 - i] = gcd(R[(n - i) % n], a[n - 1 - i])
    ans = [gcd(L[i - 1], R[(i + 1) % n]) for i in range(n)]
    print(max(ans))

p_c()

Submission status: Accepted

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

L = [0]
R = [0]
gcd_l = a[0]
gcd_r = a[-1]
for i in range(n):
    gcd_l = gcd(a[i],gcd_l)
    L.append(gcd_l)
    gcd_r = gcd(a[n-i-1],gcd_r)
    R.append(gcd_r)
#R.append(0)
#print(n)
#print(*L)
#print(*R)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
a = A.copy()
b = A.copy()
for i in range(1, N):
  a[i] = gcd(a[i-1], a[i])
for i in range(N - 1, 0, -1):
  b[i - 1] = gcd(b[i], b[i-1])
r = 0
for i in range(1, N - 1):
  r = max(r, gcd(a[i-1], b[i+1]))
r = max(r, b[1], a[-2])
print(r)

Submission status: Accepted

Solution code:
#14:10
n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
  if i == 0:
    b.append(a[i])
  else:
    big = b[-1]
    sml = a[i]
    while sml != 0:
      big,sml = sml,big%sml
    b.append(big)
c = []
for j in range(n)[::-1]:
  if j == n-1:
    c.append(a[j])
  else:
    big = c[-1]
    sml = a[j]
    while sml != 0:
      big,sml = sml,big%sml
    c.append(big)
c.reverse()
d = []
for i in range(n):
  if i == 0:
    d.append(c[1])
  elif i == n-1:
    d.append(b[n-2])
  else:
    big = b[i-1]
    sml = c[i+1]
    while sml != 0:
      big,sml = sml,big%sml
    d.append(big)
#print(b)
#print(c)
#print(d)
print(max(d))