Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

3
7 6 8

Sample Output 1

2

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

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Accepted

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

N=int(input().strip())
A=[int(x) for x in input().strip().split()]
# def gcd(a,b):
#     if b==0:
#         return a
    
#     return gcd(b,a%b)

ANS=[]
L=[0]
R=[0]
for i in range(len(A)):
    L.append(gcd(A[i],L[-1]))
    R.append(gcd(A[-1-i],R[-1]))

R.reverse()
for i in range(len(L)-1):
    ANS.append(gcd(L[i],R[i+1]))

print(max(ANS))

Submission status: Accepted

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

def calc_gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def listup_gcm(xlist):
    list_gcm = []
    prev = None
    for a in xlist:
        if prev is None:
            list_gcm.append(a)
            prev = a
            continue
        gcm = calc_gcm(prev, a)
        list_gcm.append(gcm)
        prev = gcm
    return list_gcm


left_gcm = listup_gcm(alist)
alist.reverse()
right_gcm = listup_gcm(alist)
right_gcm.reverse()


maxgcm = 0
for i in range(n):
    if i == 0:
        maxgcm = max(maxgcm, right_gcm[1])
    elif i == n - 1:
        maxgcm = max(maxgcm, left_gcm[n-2])
    else:
        maxgcm = max(maxgcm, calc_gcm(left_gcm[i-1], right_gcm[i+1]))

print(maxgcm)

Submission status: Accepted

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

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

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

# GCDの結合則を利用する
# 左端、右端からの累積GCDを求めておくと、Aiを取り除いた場合のGCDがすぐに計算できる。
# つまり、
# L(i): n=0,...,iまでのGCD 
# R(i): n=i,...,N-1までのGCD
# このとき、Aiを除いた全体のGCDは、GCD(L(i-1), R(i+1))で計算できる。

L = [0]*N
R = [0]*N

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


#残りの N − 1 個の整数の最大公約数
mx = 0
for i in range(N):
	if i == N-1:	#後ろから1個めが抜かれた時
		v = L[N-2]
	elif i == 0:	#前から1個めが抜かれた時
		v = R[1]
	else:		#どれでもない時
		v = gcd(R[i+1], L[i-1])
	mx = max(v, mx)
print(mx)

Submission status: Accepted

Solution code:
from fractions import*
def update(k,x):
    k+=N0-1
    data[k]=x
    while k+1:
        k=~-k//2
        data[k]=gcd(data[2*k+1],data[2*k+2])
def query(l,r):
    L,R=l+N0,r+N0
    s=0
    while L<R:
        if R&1:
            R-=1
            s=gcd(s,data[R-1])
        if L&1:
            s=gcd(s,data[L-1])
            L+=1
        L>>=1
        R>>=1
    return s
n,*a=map(int,open(0).read().split())
N0=2**(n-1).bit_length()
data=[0]*2*N0
for i in range(n):
    update(i,a[i])
print(max(gcd(query(0,i),query(i+1,n))for i in range(n)))

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
L = [0, 0]
for ai in A:
    L.append(gcd(L[-1], ai))
 
R = [0, 0]
for ai in A[::-1]:
    R.append(gcd(R[-1], ai))
 
print(max(gcd(l, r) for l, r in zip(L, reversed(R))))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))

L = []
R = []
k = 0
for i in range(N):
    k = gcd(k, A[i])
    L.append(k)
k = 0
for j in range(N)[::-1]:
    k = gcd(k, A[j])
    R.append(k)
R[:] = R[::-1]

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

Submission status: Accepted

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

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

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

# GCDの結合則を利用する
# 左端、右端からの累積GCDを求めておくと、Aiを取り除いた場合のGCDがすぐに計算できる。
# つまり、
# L(i): n=0,...,iまでのGCD 
# R(i): n=i,...,N-1までのGCD
# このとき、Aiを除いた全体のGCDは、GCD(L(i-1), R(i+1))で計算できる。

L = [0] * N
R = [0] * N

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

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

Submission status: Accepted

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

max_gcd = 1

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

def gcd(a, b):
        if a == 0:
                return b
        elif b == 0:
                return a
        else:
                return fractions.gcd(a,b)

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

print(max(M))

Submission status: Accepted

Solution code:
from fractions import gcd

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

left = [0]*N

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

right = [0]*N

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

ans_list = [gcd(l,r) for l, r in zip(left,right)]

ans = max(ans_list)

print(ans)

Submission status: Accepted

Solution code:
n = int(raw_input())
a = raw_input().split()

cnt = 0
for i in a:
    a[cnt] = int(i)
    cnt += 1

chk = {}
chk2 = {}
def make_divisors(k):
    divisors = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            if i in chk:
                chk[i] += 1
            else:
                chk[i] = 1
            if i != k // i:
                key = int(k//i)
                if key in chk:
                    chk[key] += 1
                else:
                    chk[key] = 1
    return divisors

for i in range(2):
    make_divisors(a[i])
cnt = 1
for i in range(2,len(a)):
    k = a[i]
    if k not in chk2:
        chk2[k] = 1
    else:
        if chk2[k] == 1:
            chk2[k] += 1
        elif chk2[k] > 1:
            continue
    del_list = []
    for j in chk:
        if k % j == 0:
            chk[j] += 1
        if chk[j] < cnt+1:
            del_list.append(j)
    for j in del_list:
        del chk[j]
    cnt += 1

answer = 0
for i in chk:
    if int(chk[i]) >= chk[1] - 1 and i > answer:
        answer = i
print answer

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

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

Li = [0]*(N+2)
Ri = [0]*(N+2)
A.append(0)
A.insert(0, 0)

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

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

# print(Li)
# print(Ri)

M = []
for i in range(1, N+1):
	M.append(gcd(Li[i],Ri[i+1]))
# print(M)
print(max(M))

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
gcd_left = [A[0]]
gcd_right = [A[-1]]
for i in range(1, N):
    gcd_left.append(gcd(gcd_left[-1], A[i]))
    gcd_right.append(gcd(gcd_right[-1], A[N-i-1]))
gcd_right = list(reversed(gcd_right))

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

Submission status: Accepted

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

from fractions import gcd

L = [0, 0]
for ai in A:
    L.append(gcd(L[-1], ai))

R = [0, 0]
for ai in A[::-1]:
    R.append(gcd(R[-1], ai))

print(max(gcd(l, r) for l, r in zip(L, reversed(R))))

Submission status: Accepted

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

for i in range(end + 1, 0, -1):
    x = 0
    for j in a:
        if j % i != 0:
            x += 1
        if x >= 2:
            break
    if x <= 1:
        print(i)
        break

Submission status: Accepted

Solution code:
import functools
import fractions


N = int(input())
a = list(map(int, input().split()))
A = list(set(a))
ans = [functools.reduce(fractions.gcd, A)]
if len(A) == 1:
    print(A[0])
    exit()
else:
    for i in A:
        b = sorted(A)
        b.remove(i)
        if a.count(i) == 1:
            ans.append(functools.reduce(fractions.gcd, b))
print(max(ans))

Submission status: Accepted

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

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

Submission status: Accepted

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


gcdL = []
gcdR = []

N = int(input())
A = [int(x) for x in input().split()]
gcdL.append(0)
length_A = len(A)
for i in range(1,length_A):
    gcdL.append(gcd(A[i-1],gcdL[i-1]))


gcdR.append(0)
for i in range(1,length_A):
    gcdR.append(gcd(A[length_A-i],gcdR[i-1]))



list_gcd = []
for i in range(length_A):
        list_gcd.append(gcd(gcdL[i],gcdR[length_A-i-1]))

print(max(list_gcd))

Submission status: Accepted

Solution code:
import sys


def gcd(a, b):
    """Euclidean Algorithm"""
    a, b = max(a, b), min(a, b)
    while b != 0:
        a, b = b, a % b
    return a


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

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

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

    M = [0 for _ in range(N)]
    for i in range(N):
        M[i] = gcd(L[i], R[i+1])

    return max(M)


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N=int(input())
A=list(int(x) for x in input().split())

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

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

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

print(max(ans))

Submission status: Accepted

Solution code:
def c_gcd_on_blackboard(N, A):
    # editorial通り
    from fractions import gcd

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

    return max([gcd(left[i], right[i + 1]) for i in range(N)])

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

Submission status: Accepted

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

kosuu = int(input())
nums = list(map(int,input().split()))

L = []
R = []
for temp in range(kosuu-1):
    if temp == 0:
        L.append(nums[0])
    else:
        L.append(gcd(L[temp-1],nums[temp]))

for temp in range(kosuu-1):
    if temp == 0:
        R.append(nums[kosuu-1])
    else:
        R.append(gcd(R[temp-1],nums[len(nums)-temp-1]))

saidai=[]
for i in range(kosuu):
    if i == 0:
        saidai.append(L[-1])
    elif i == kosuu-1:
        saidai.append(R[-1])
    else:
        saidai.append(gcd(L[i-1],R[-1-i]))

print(max(saidai))

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)


L = [0] * (N + 1)
R = [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):
    ans = max(ans, gcd(L[i], R[i+1]))

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

l = [0 for _ in range(n+1)]
r = [0 for _ in range(n+1)]
ans = []

for i in range(n):
    l[i+1] = gcd(l[i],A[i])

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

Submission status: Accepted

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

from fractions import gcd

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

R = [0, 0]
for i in range(N - 1, -1, -1):
    R.append(gcd(R[-1], A[i]))
R.reverse()

print(max(gcd(l, r) for l, r in zip(L, R)))

Submission status: Accepted

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

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

X = [0 for i in range(N)]
Y = [0 for i in range(N)]

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

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

Z = [gcd(X[i], Y[i]) for i in range(N)]
print(max(Z))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
divisors = []
for j in range(2):
    for i in range(1, int(a[j]**0.5)+1):
        if a[j] % i == 0:
            divisors.append(i)
            if i != a[j] // i:
                divisors.append(a[j]//i)
divisors = list(set(divisors))
divisors.sort(reverse=True)

if n == 2:
    print(max(divisors))
else:
    for i in divisors:
        judge = 0
        for j in range(n):
            if judge > 0 and a[j] % i !=0:
                judge += 1
                break
            elif a[j] % i != 0:
                judge += 1
        if judge < 2 :
            print(i)
            break

Submission status: Accepted

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


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


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

for i in range(1, N):
    X[i] = gcd(X[i-1], A[i-1])
for i in range(N-1)[::-1]:
    Y[i] = gcd(Y[i+1], A[i+1])
for i in range(N):
    if gcd(X[i], Y[i]) > ans:
        ans = gcd(X[i], Y[i])

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
##  input functions for me
def ria(sep = ''):
    if sep == '' :
        return list(map(int, input().split())) 
    else: return list(map(int, input().split(sep)))
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

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

## main ##
N = ri()
A = ria()

L = [0] * N
R = [0] * N

L[0] = A[0]
for i in range(1, N): L[i] = gcd(A[i], L[i - 1])
R[N-1] = A[N-1]
for i in range(1, N): R[N - 1 - i] = gcd(A[N - 1 - i], R[N - 1 - i + 1])
if N > 2 : ma = max(R[1], L[N-2])
else: ma = max(A)
for i in range(1, N - 1): ma = max(ma, gcd(L[i - 1], R[i + 1]))
#print(L)
#print(R)


print(ma)

Submission status: Accepted

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))

P_MAX = 32000
sieve = [1]*P_MAX
sieve[0] = sieve[1] = 0
P = []
for i in range(2,P_MAX):
    sieve = 1
    for p in P:
        if p*p > i:
            break
        elif i % p == 0:
            sieve = 0
            break
    if sieve == 0:
        continue
    else:
        P.append(i)

def factorize(n):
    primes = []
    powers = []
    for p in P:
        if p * p > n:
            break
        elif n % p == 0:
            k = 0
            while n % p == 0:
                n //= p
                k += 1
            primes.append(p)
            powers.append(k)
    if n > 1:
        primes.append(n)
        powers.append(1)
    return primes, powers

N = int(input())
A = inpl()
infty = 100
lowest_powers = defaultdict(lambda: [infty,infty])
bottle_necks = defaultdict(lambda: -1)
all_factors = set()
for n in range(N):
    primes, powers = factorize(A[n])
    prev_primes = list(bottle_necks.keys())
    done = defaultdict(int)
    for i in range(len(primes)):
        done[primes[i]] = 1
        if not primes[i] in all_factors:
            all_factors.add(primes[i])
            if n == 1:
                lowest_powers[primes[i]] = [0,powers[i]]
                bottle_necks[primes[i]] = 0
            elif n == 0:
                lowest_powers[primes[i]] = [powers[i],infty]
                bottle_necks[primes[i]] = 0
        lowest = lowest_powers[primes[i]]
        if powers[i] == lowest[0]:
            lowest[1] = lowest[0]
            bottle_necks[primes[i]] = -1
        elif powers[i] < lowest[0]:
            lowest[1] = lowest[0]
            lowest[0] = powers[i]
            bottle_necks[primes[i]] = n
        elif powers[i] < lowest[1]:
            lowest[1] = powers[i]
    for p in all_factors:
        if done[p] == 0:
            lowest = lowest_powers[p]
            if lowest[0] == 0:
                lowest[1] = 0
                bottle_necks[p] = -1
            else:
                lowest[1] = lowest[0]
                lowest[0] = 0
                bottle_necks[p] = n

bnl = defaultdict(lambda: [])
for p,n in bottle_necks.items():
    if n >= 0:
        lowest = lowest_powers[p]
        bnl[n].append([p,lowest[1]-lowest[0]])
best_n = -1
largest_f = 1
for n in range(N):
    f = 1
    for pp in bnl[n]:
        f *= pp[0]**pp[1]
    if f > largest_f:
        largest_f = f
        best_n = n

ans = 1
bn = bnl[best_n]
pn = [ s[0] for s in bn]
for p in all_factors:
    if p in pn:
        ans *= p**lowest_powers[p][1]
    else:
        ans *= p**lowest_powers[p][0]
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)


def m():
    left, right = A.copy(), A.copy()
    for i in range(1, N):
        left[i] = gcd(A[i], left[i-1])

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

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


print(m())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,fractions
from functools import reduce
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    N = int(lines.pop(0))
    A = list(map(int, lines.pop(0).split(' ')))

    _l = 0
    L = []
    for i in range(N-1):
        _l = fractions.gcd(_l, A[i])
        L.append(_l)
    L.insert(0,0)

    _r = 0
    R = []
    for i in range(N-1):
        _r = fractions.gcd(_r, A[N-i-1])
        R.append(_r)
    R.reverse()
    R.append(0)

    print(max([fractions.gcd(l,r) for l, r in zip(L,R)]))



lines = [x.strip() for x in sys.stdin.readlines()]

#
# solve !!
#
solve(lines)

Submission status: Accepted

Solution code:
#C問題
N=int(input())
A=list(map(int,input().split()))
def gcd(GCD1,GCD2):
    x = min(GCD1,GCD2)
    y = max(GCD1,GCD2)
    if y%x == 0:
        return x
    else:
        return gcd(x,y%x)
def gcdlist(xlist):
    xlen=len(xlist)
    GCD=0
    for i in range(xlen-1):
        GCD=gcd(xlist[i],xlist[i+1])
        xlist[i+1]=GCD
    return GCD
MAX=0
kari=0
gcdf=[]
for i in range(N):
    if i == 0:
        gcdf.append(A[i])
    else:
        gcdf.append(gcd(A[i],gcdf[-1]))
gcdb=[]
for i in range(N):
    if i == 0:
        gcdb.append(A[-1])
    else:
        gcdb.append(gcd(A[-1-i],gcdb[-1]))
MAX=0
gcdb=gcdb[::-1]
for i in range(N):
    if i == 0:
        kari=gcdb[1]
    elif i == N-1:
        kari=gcdf[-2]
    else:
        f=gcdf[i-1]
        b=gcdb[i+1]
        kari=gcd(f,b)
    MAX=max(kari,MAX)
print(MAX)

Submission status: Accepted

Solution code:
import numpy as np

def gcd(a,b):    
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
    
N = int(input())
A_list = list(map(int, input().split()))

# =====
# initialize L and R
# =====
L = np.zeros(N+1)
R = np.zeros(N+1)

for idx, element in enumerate(A_list):
    if L[idx] == 0:
        L[idx+1] = element
    else:
        L[idx+1] = gcd(L[idx], element)

for idx, element in enumerate(A_list[-1::-1]):
    idx = N-idx
    if R[idx] == 0:
        R[idx-1] = element
    else:
        R[idx-1] = gcd(R[idx], element)

ans = 0
for i in range(N):
    if L[i] == 0:
        M = R[i+1]
    elif R[i+1] == 0:
        M = L[i]
    else:
        M = gcd(L[i], R[i+1])
    if ans < M:
        ans = M

print(int(ans))

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from functools import reduce
from itertools import combinations

sys.setrecursionlimit(200000)


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


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    N = ii()
    A = il()
    b = [0] * N
    c = [0] * N
    for i in range(1, N):
        b[i] = gcd(b[i - 1], A[i - 1])
    for i in range(N - 1)[::-1]:
        c[i] = gcd(c[i + 1], A[i + 1])
    d = [gcd(b[i], c[i]) for i in range(N)]
    return max(d)


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

N=int(input())
A=list(map(int,input().split()))
L=[0]*100000
R=[0]*100000
L[0]=A[0]
for i in range(N-1):
    L[i+1]=gcd(L[i],A[i+1])
R[N-1]=A[N-1]
for i in reversed(range(N-1)):
    R[i]=gcd(R[i+1],A[i])
Ans=max(L[N-2],R[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:
n=int(input())
l=[int(i) for i in input().split()]
l.extend(l)
from fractions import gcd
lst1=[l[0]]
lst2=[l[-1]]
for i in range(1,n):
    lst1.append(gcd(lst1[-1],l[i]))
for i in range(n-1,-1,-1):
    lst2.append(gcd(lst2[-1],l[i]))
lst2=lst2[::-1]
lst=[]
for i in range(n):
    if i==0:
        lst.append(lst2[1])
    if i==n-1:
        lst.append(lst1[-2])
    else:
        lst.append(gcd(lst1[i-1],lst2[i+1]))
print(max(lst))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
import copy

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

fValueList = []
lValueList = []
maxList = []

if n == 2:
  print(max(a[0], a[1]))
else:
  fValueList.append(a[0])
  lValueList.append(a[n-1])
  for i in range(1,n-1):
    g = fValueList[i-1]
    fValueList.append(gcd(g, a[i]))

  for i in range(1,n-1):
    g = lValueList[i-1]
    lValueList.append(gcd(g, a[n-1-i]))
  
  maxList.append(fValueList[n-2])
  maxList.append(lValueList[n-2])
  for k in range(n-2):
    g = gcd(fValueList[k], lValueList[n-3-k])
    maxList.append(g)
    
  print(max(maxList))

Submission status: Accepted

Solution code:
import sys
N = int(input())
A_arr = list(map(int, input().split()))

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

gcd_l = [A_arr[0]]
gcd_r = [A_arr[N-1]]

for i in range(0,N-1):
    gcd_l.append(gcd(gcd_l[i], A_arr[i+1]))

for i in range(0,N-1):
    gcd_r.append(gcd(gcd_r[i], A_arr[N-2-i]))

gcd_list = []
for i in range(0, N):
    if i == 0:
        gcd_list.append(gcd_r[N-1-i-1])
    elif i == N-1:
        gcd_list.append(gcd_l[i-1])
    else:
        gcd_list.append(gcd(gcd_l[i-1], gcd_r[N-1-i-1]))

print(max(gcd_list))

Submission status: Accepted

Solution code:
 
#from functools import reduce
def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  while y!=0:
    x,y=y,x%y
  return x
 
a=int(input())
li=list(map(int,input().split()))
left_gcd=[0]
#left_gcd.append(li[0])
right_gcd=[0]
#right_gcd.append(li[a-1])

for i in range(a):
    left_gcd.append(gcd(li[i],left_gcd[i]))
    right_gcd.append(gcd(li[a-1-i],right_gcd[i]))
    #k=k+1
# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)
#print(right_gcd)
#print(left_gcd)
num_li=[]
#num_li.append(right_gcd[a-2])
#num_li.append(left_gcd[a-2])
#s=2
for i in range(a):
    ans=gcd(left_gcd[(a-1)-i],right_gcd[i])
    #print(left_gcd[(a-3-i)],right_gcd[i])
  
    #print(ans)
    num_li.append(ans)
    

print(max(num_li))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
def gcd(x,y):
  while y != 0:
    k = x
    x = y
    y = k%y
  return  x
L = [0]*(N+2)
R = [0]*(N+2)
for i in range(N):
  if L[i] == 0:
    L[i+1] = A[i]
  else:
    L[i+1] = gcd(max(L[i],A[i]),min(L[i],A[i]))
for i in range(N,-1,-1):
  if i == N:
    R[i+1] = 0
  elif i == N-1:
    R[i+1] = A[N-1] 
  else:
    R[i+1] = gcd(max(R[i+2],A[i]),min(R[i+2],A[i]))
ans = 1
for i in range(N):
  if L[i] == 0 or R[i+2] == 0:
    k = max(L[i],R[i+2])
    ans = max(ans,k)
  else:
    ans = max(ans,gcd(max(L[i],R[i+2]),min(L[i],R[i+2])))
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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

def solve(N, As):
    Lgcd = [0 for _ in range(len(As) + 1)]
    Rgcd = [0 for _ in range(len(As) + 1)]
    for i in range(len(As)):
        Lgcd[i + 1] = gcd(Lgcd[i], As[i])
    for i in reversed(range(len(As))):
        Rgcd[i] = gcd(Rgcd[i + 1], As[i])
    ans = 1
    for i in range(len(As)):
        ans = max(ans, gcd(Lgcd[i], Rgcd[i + 1]))
    print(ans)


if __name__ == '__main__':
    N = int(input()) # ignore
    As = list(map(int, input().split()))
    solve(N, As)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

q = [a[-1]]
for i in range(n - 1):
    q.append(gcd(q[i], a[n - 2 - i]))
q = q[::-1]

res = 1
for i in range(n):
    if i - 1 < 0:
        res = max(res, q[i + 1])
    elif i + 1 >= n:
        res = max(res, p[i - 1])
    else:
        res = max(res, gcd(p[i - 1], q[i + 1]))

print(res)

Submission status: Accepted

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

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

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

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

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

print(w)

Submission status: Accepted

Solution code:
import fractions

def gcd(n1,n2):
  if n1 == 0:
    return n2
  elif n2 == 0:
    return n1
  else:
    return fractions.gcd(n1,n2)

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

Submission status: Accepted

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

ans = max(ans, l[N - 2], r[N - 2])

print(ans)

Submission status: Accepted

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

from functools import reduce
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
"""
def gcds(*numbers):
    return reduce(gcd, numbers)
"""
l = [0 for _ in range(n)]

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

Submission status: Accepted

Solution code:
def GCD(a, b):
    if a == 0 and b == 0:
        return 0
    elif a == 0:
        return b
    elif b == 0:
        return a

    while a % b != 0:
        r = a % b
        a, b = b, r
    return b

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

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

for i in range(1,N):
    X[i] = GCD(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i] = GCD(Y[i+1],A[i+1])

for i in range(N):
    ans = max(ans,GCD(X[i],Y[i]))

print(ans)

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

if n==2:
    print(max(a))
    exit()
'''
L = [gcd(a[0], a[1])]
R = [gcd(a[n-2], a[n-1])]
'''
L = [0 for i in range(n+1)]
R = [0 for i in range(n+1)]
for i in range(1,n+1):
    L[i] = gcd(L[i-1], a[i-1])

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

m = [0 for i in range(n)]

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

print(max(m))

Submission status: Accepted

Solution code:
import sys,collections as cl
import fractions
from functools import reduce
import copy
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())

a = l()

m = gcd_list(a[1:])
m = max(m,gcd_list(a[:n-1]))
aa = [a[0]]
aaa = [a[-1]]
for i in range(n-1):
	aa.append(gcd(aa[-1],a[i+1]))
	aaa.append(gcd(aaa[-1],a[-(i+1)]))

for i in range(n-1):
	m = max(m,gcd(aa[i],aaa[-(i+2)]))
print(m)

Submission status: Accepted

Solution code:
import math

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

gcd_list = [0 for _ in range(N)]

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

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

print(max(gcd_list))