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 fractions
 
N = int(input())
A = list(map(int,input().split()))
L = [0] * N
R = [0] * N

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

ans = [0] * N

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

print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

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

def f(l):
    yield 0
    a = 0
    for i in l:
        a = gcd(a, i)
        yield a

L = list(f(A))
R = list(reversed(list(f(reversed(A)))))

print(max([gcd(a, b) for a, b in zip(L, R[1:])]))

Submission status: Accepted

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

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

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

for i in range(2, N+1):
    memo[(0, i)] = gcd(memo[(0, i - 1)], nums[i-1])

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

res = 1
for i in range(1, N-1):
    res = max(res, gcd(memo[(0, i)], memo[(i+1, N)]))

res = max(res, memo[(0, N-1)])
res = max(res, memo[(1, N)])

print(res)

Submission status: Accepted

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

import fractions
gcd_forward  = [A[0]]*N
gcd_backward = [A[N-1]]*N
for i in range(1,N):
    gcd_forward[i]  = fractions.gcd(A[i],gcd_forward[i-1])
for i in range(N-2,0,-1):
    gcd_backward[i] = fractions.gcd(A[i],gcd_backward[i+1])

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

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
n,a,b=int(input()),list(map(int,input().split())),[]
if n==2:print(max(a[0],a[1]))
elif n==3:print(max(gcd(a[0],a[1]),gcd(a[0],a[2]),gcd(a[1],a[2])))
else:
  no,mi=a[0],a[0]
  for i in range(1,n):
    s=gcd(no,a[i])
    if s!=no:
      no=max(s,mi)
      mi=gcd(s,mi)
  print(no)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from functools import reduce
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))

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


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

M = [None] * n
R = R[::-1]
for i in range(n):
	M[i] = gcd(L[i], R[i])

print(max(M))

Submission status: Accepted

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

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

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

for i in range(2, N+1):
    memo[(0, i)] = gcd(memo[(0, i - 1)], nums[i-1])
    # print("{} {} memo:{}".format(0, i, memo[(0,i)]))


for i in reversed(range(0, N-1)):
    memo[(i, N)] = gcd(memo[(i + 1, N)], nums[i])
    # print("{} {} memo:{}".format(i, N, memo[(i,N)]))

res = 1
for i in range(1, N-1):
    res = max(res, gcd(memo[(0, i)], memo[(i+1, N)]))
    # print("gcd:{}".format(gcd(memo[(0, i)], memo[(i+1, N)])))

res = max(res, memo[(0, N-1)])
res = max(res, memo[(1, N)])

print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
def gcd(p,q):
    if p%q: return gcd(q,p%q)
    else: return q
if n==2: print(max(a))
else:
    num,x,num2 = a[2],[],gcd(a[0],a[1])
    for i in range(3,n): num = gcd(num,a[i])
    ans = max(gcd(num,a[0]),gcd(num,a[1]))
    for i in range(1,int(num2**0.5)+1):
        if num2%i==0:
            x.append(i)
            if i**2!=num2: x.append(num2//i)
    x = sorted(x)[::-1]
    for i in x:
        m = 0
        for j in a[2:]:
            if j%i: m+=1
            if m>1: break
        if m<2: break
    print(max(ans,i))

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
dp = [0] * (N+1)
dpr = [0]*(N+1)
for i in range(N):
    dp[i+1] = gcd(dp[i], A[i])
    dpr[N-i-1] = gcd(dpr[N-i],A[N-i-1])
ans = 0
for i in range(N):
    tmp = gcd(dp[i],dpr[i+1])
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from fractions import*
from numpy import*

def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

n,*a=map(int,open(0).read().split())
a=array(a)
l=[1]
for i in set(dv(a[0])+dv(a[1])):
    if sum(a%i==0)>=n-1:
        l.append(i)
print(max(l))

Submission status: Accepted

Solution code:
n=int(input())
left=list(map(int,input().split()))
right=list(left)
right.reverse()
gcds=[]
gcdleft=[]
gcdright=[]

gcdleft.append(left[0])
gcdright.append(right[0])

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

if n==2:
    gcds.append(gcdleft[0])
    gcds.append(gcdright[0])
else:
    for i in range(1,n-1):
        gcdleft.append(gcd(gcdleft[i-1],left[i]))
        gcdright.append(gcd(gcdright[i-1],right[i]))
    gcds.append(gcdright[-1])
    for i in range(0,n-2):
    	gcds.append(gcd(gcdleft[i],gcdright[n-3-i]))
    gcds.append(gcdleft[-1])

print(max(gcds))

Submission status: Accepted

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

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

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

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

ans=max(r[1],l[N-2])
for i in range(1,N-1):
    tmp=gcd(l[i-1],r[i+1])
    if tmp>ans: ans=tmp

print(ans)

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 125
# https://atcoder.jp/contests/abc125
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

cache = {}


def gcdr(a, b):
    if a not in cache:
        cache[a] = {}
    if b in cache[a]:
        return cache[a][b]
    if b == 0:
        cache[a][b] = a
        return a
    n = gcdr(b, a % b)
    cache[a][b] = n
    return n

def gcd(a, b):
    if a >= b:
        return gcdr(a, b)
    else:
        return gcdr(b, a)

def main_lte(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn = [An[0]] * N
    nn[0] = An[1]
    for i in range(1, N):
        for j in range(N):
            if i == j:
                continue
            nn[j] = gcd(nn[j], An[i])
    print(int(max(nn)))

def main_ok(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn0 = gcd(An[0], An[1])
    nn1 = set((An[0], An[1]))
    for i in range(2, N):
        t1 = nn0
        nn0 = gcd(nn0, An[i])
        t2 = [gcd(n, An[i]) for n in nn1]
        nn1 = set(t2)
        nn1.add(t1)
    n = max(nn1)
    print(int(n))

def main(N, An):
    nnl = [0] * N
    nnr = [0] * N
    nnl[0] = An[0]
    nnr[N-1] = An[N-1]
    for i in range(1, N):
        nnl[i] = gcd(nnl[i-1], An[i])
    for i in range(N-2, -1, -1):
        nnr[i] = gcd(nnr[i+1], An[i])
    nn = [0] * N
    nn[0] = nnr[1]
    nn[N-1] = nnl[N-2]
    for i in range(1, N-1):
        nn[i] = gcd(nnl[i-1], nnr[i+1])
    n = max(nn)
    print(int(n))

N = i2n()
An = i2nn()
main(N, An)

Submission status: Accepted

Solution code:
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return a

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import fractions
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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])
for i in reversed(range(n)):
    right[i] = fractions.gcd(right[i + 1], a[i])
mx = 0
for i in range(n):
    l = left[i]
    r = right[i + 1]
    mx = max(mx, fractions.gcd(l, r))
print(mx)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
A = list(set(a))
ans = [reduce(gcd, A)]

if len(A) == 1:
    print(A[0])
    exit()
for i in A:
    b = sorted(A)
    b.remove(i)
    if a.count(i) == 1:
        ans.append(reduce(gcd, b))

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

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

Submission status: Accepted

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

from fractions import gcd

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

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

print(max(gcd(l, r) for l, r in zip(L[:N], R[1:])))

Submission status: Accepted

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

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

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

m=[]
for i in range(n):
    m.append(gcd(l[i],r[i+1]))

print(max(m))

Submission status: Accepted

Solution code:
import functools
import copy

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

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

l = [0] * N  #L_i, i = 0, 1, 2, ..., N-1
for i in range(N):
    if i == 0:
        continue
    else:
        l[i] = gcd(l[i-1], A[i-1])

r = [0] * N #R_i, i = 0, 1, 2, ..., N-1
for j in range(N):
    if j == 0:
        continue
    else:
        r[N-j-1] = gcd(r[N-j], A[N-j])

m = [0] * N
for i in range(N):
    m[i] = gcd(l[i], r[i])

print(max(m))

Submission status: Accepted

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


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

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

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

R.reverse()

M = [0] * n
for i in range(n):
    if i == 0:
        M[i] = R[0]
    elif i == n-1:
        M[i] = L[-1]
    else:
        M[i] = gcd(L[i-1],R[i])

#print(L,R)
print(max(M))

Submission status: Accepted

Solution code:
# 解けなかった...orz

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

def gcd(i, j):
    if i <= 0:
        return j
    elif j <= 0:
        return i

    while i != j:
        if i < j:
            j %= i
            if j == 0: return i
        else:
            i %= j
            if i == 0: return j
    return i

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

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

res = max(gcd(L[i], R[i+1]) for i in range(N))
print(res)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from collections import deque

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

L=deque()

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

R=deque()

for i in range(N-1,-1,-1):
	if i==N-1:
		R.appendleft(A[i])
	else:
		R.appendleft( gcd(A[i],R[0]) )

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

print ans

Submission status: Accepted

Solution code:
import fractions
 
n = int(input())
li = list(map(int,input().split()))
 
leftgcd = [0 for i in range(n)]
rightgcd = [0 for i in range(n)]
 
leftgcd[0] = li[0]
rightgcd[n - 1] = li[n - 1]
 
if n == 2:
  print(max(li[0], li[1]))
else:
  for j in range(1, n):
    leftgcd[j] = fractions.gcd(li[j], leftgcd[j - 1])
    rightgcd[n - 1 - j] = fractions.gcd(li[n - 1 - j], rightgcd[n - j])
 
  ans = max(leftgcd[n - 2], rightgcd[1])
  for k in range(1, n - 1):
    g = fractions.gcd(leftgcd[k - 1], rightgcd[k + 1])
    if g > ans:
      ans = g
  print(ans)

Submission status: Accepted

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

import fractions
from functools import reduce

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

L = [0 for i in range(N+1)]
R = [0 for j in range(N+1)]

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

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

print(M)

Submission status: Accepted

Solution code:
# C
import functools
# 3.4以前は math の gcd が対応していないので fractions のものを使う
# from fractions import gcd
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)


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

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

for i in range(1,n):
    if gcd_right[i-1] != 1:
        res = gcd(gcd_right[i-1], a[-(i+1)])
    else:
        res = 1
    gcd_right.append(res)
gcd_right = gcd_right[::-1]


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

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

N=int(input())
A=list(map(int,input().split()))
x=A[0]
y=A[1]
D=sorted(list(set(make_divisors(x))|set(make_divisors(y))))[::-1]
for d in D:
    if sum([a%d==0 for a in A])>=N-1:
        break
print(d)

Submission status: Accepted

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


def gcd_on_blackboard(N: int, A: list)->int:
    L, R = [0] * N, [0] * N

    L[0] = A[0]
    for i, a in enumerate(A[1:]):
        L[i+1] = gcd(L[i], a)

    R[-1] = A[-1]
    for i, a in enumerate(reversed(A[:-1])):
        R[N-i-2] = gcd(R[N-i-1], a)

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

    return max_diff


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]

    ans = gcd_on_blackboard(N, A)
    print(ans)

Submission status: Accepted

Solution code:
import sys

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

input = sys.stdin.readline
n = int(input())
a_list = list(map(int, input().split()))
l_list = [0]
r_list = [0]
l_gcd, r_gcd = 0, 0
for i in range(n-1):
    l_gcd = gcd(l_gcd, a_list[i])
    l_list.append(l_gcd)
    r_gcd = gcd(r_gcd, a_list[-i-1])
    r_list.append(r_gcd)
ans = 1
for i in range(n):
    ans = max(ans, gcd(l_list[i], r_list[-i-1]))
print(ans)

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.extend([i,int(n/i)])
    return divisors

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

p = make_divisors(l[0])
p.extend(make_divisors(l[1]))

p.sort(reverse=True)
for i in p:
    ans = 1
    flag = 0
    for j in l:
        if j%i != 0:
            if flag == 1:
                ans = 0
                break
            flag = 1
    if ans:
        print(i)
        exit()

Submission status: Accepted

Solution code:
from math import ceil, sqrt
from fractions import gcd

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

D = set()
for x in A[:2]:
  for i in range(1, ceil(sqrt(x))+2):
    if x % i == 0:
      D.add(i)
      D.add(x//i)

D = list(D)
D.sort(reverse=True)
for d in D:
  count = 0
  for a in A:
    if a % d != 0:
      count += 1
    if count >= 2:
      break
  else:
    print(d)
    break

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_l = [0]
gcd_r = [0]

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

for i in range(N - 1, -1, -1):
    gcd_r.append(gcd(gcd_r[-1], a[i]))
gcd_r += [0]
gcd_r = gcd_r[::-1]
# gcd_x[idx]:=idx番目までの累積gcd, 1-indexed
# [0] + [gcd] + [0]
# index: 0, 1, ..., N, N+1

g = 1
for i in range(1, N + 1):
    # i: 1-indexed
    g_l = gcd_l[i - 1]
    g_r = gcd_r[i + 1]
    g = max(g, gcd(g_l, g_r))
print(g)

Submission status: Accepted

Solution code:
import fractions

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

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

for i in range(1, N):
    L[i] = fractions.gcd(L[i - 1], A[i - 1])
for j in range(0, N-1)[::-1]:
    R[j] = fractions.gcd(R[j + 1], A[j + 1])
ans = 0
for k in range(N):
    ans = max(ans, fractions.gcd(L[k], R[k]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import*
n,*a=map(int,open(0).read().split())
*b,=a=a+[0]
r=range(n)
for i in r:a[i]=gcd(a[i],a[i-1]);b[n-i-1]=gcd(b[n-i-1],b[n-i])
print(max(gcd(a[i-1],b[i+1])for i in r))

Submission status: Accepted

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

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
fromLeft = [0] * n
fromLeft[0] = a[0]
fromRight = [0] * n
fromRight[0] = a[n - 1]
for i in range(1, n):
    fromLeft[i] = gcd(fromLeft[i - 1], a[i])
    fromRight[i] = gcd(fromRight[i - 1], a[n - i - 1])
ret = fromLeft[n - 1]
for i in range(n):
    if i == 0:
        curGcd = fromRight[n - 2]
    elif i == n - 1:
        curGcd = fromLeft[n - 2]
    else:
        curGcd = gcd(fromLeft[i - 1], fromRight[n - i - 2])
    ret = max(ret, curGcd)
print(ret)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(x, y):
    if x<y:x,y=y,x
    while x % y != 0:
        x, y = y, x % y
    return y
left=[]
right=[]
for i in range(n):
    if i==0:
        left.append(a[i])
        right.append(a[-i-1])
    else:
        left.append(gcd(a[i],left[i-1]))
        right.append(gcd(a[-i-1],right[i-1]))
ans=max(left[n-2],right[n-2])
for i in range(n-2):
    ans=max(ans,gcd(left[i],right[n-i-3]))
print(ans)

Submission status: Accepted

Solution code:
import fractions


'''

最大公約数を求める
最大公約数を最大にするには何を変えれば良いか

最大値との最大公約数を求めて、最大になれば良い?

'''

n = list(map(int, input().split()))
A = list(map(int, input().split()))
right = []
left = []
for i,a in enumerate(A):
    if i ==0 :
        right.append(a)
    else:
        right.append(fractions.gcd(right[i-1],a))

for i,b in enumerate(reversed(A)):
    if i ==0 :
        left.append(b)
    else:
        left.append(fractions.gcd(left[i-1],b))

result = []

for i,r in enumerate(A):
    if i ==0:
        result.append(right[len(right)- 2])
    if i == len(A) -1:
        result.append(left[len(left) - 2])

    result.append(fractions.gcd(left[i -1], right[len(right) - i -2]))

print(max(result))

Submission status: Accepted

Solution code:
def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x % y) #再帰定義
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
r=[0]*n
for i in range(1,n):
  if i==1:
    l[1]=a[0]
    r[-2]=a[-1]
  else:
    l[i]=gcd(l[i-1],a[i-1])
    r[-i-1]=gcd(r[-i],a[-i])
g=[0]*n
for i in range(n):
  if l[i]==0 or r[i]==0:
    g[i]=l[i]+r[i]
  else:
    g[i]=gcd(l[i],r[i])
print(max(g))

Submission status: Accepted

Solution code:
import fractions

n = int(input())
a = [int(i) for i in input().split()]
ans = a[0]
x = a[0]

if n==2:
  print(max(a[0],a[1]))
  exit()
elif n==3:
  print(max(fractions.gcd(a[0],a[1]),fractions.gcd(a[0],a[2]),fractions.gcd(a[1],a[2])))
  exit()

for i in range(n):
  temp = fractions.gcd(ans,a[i])
  if temp != ans:
    ans = max(temp,x)
    x= fractions.gcd(temp,x)

print(ans)

Submission status: Accepted

Solution code:
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(A[i], left[i])

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

max_gcd = 1

for i in range(N):

    l = left[i]
    r = right[i + 1]

    gcd_num = fractions.gcd(l, r)

    max_gcd = max(max_gcd, gcd_num)

print(max_gcd)

Submission status: Accepted

Solution code:
import fractions
 
n = int(input())
a = [int(value) for value in input().split(" ")]
 
from_right_gcd = []
from_left_gcd = []
 
# 左から
for index in range(a.__len__()):
    if index == 0:
        from_left_gcd.append(a[index])
        continue
    from_left_gcd.append(fractions.gcd(from_left_gcd[index - 1], a[index]))
 
# 右から
for index in range(a.__len__() - 1, -1, -1):
    if index == a.__len__() - 1:
        from_right_gcd.append(a[index])
        continue
    from_right_gcd.append(fractions.gcd(from_right_gcd[a.__len__() - index - 1 - 1], a[index]))
 
maybe_answer_list = []
 
for index in range(a.__len__()):
    if index == 0:
        maybe_answer_list.append(from_right_gcd[a.__len__() - 1 - 1])
        continue
    if index == a.__len__() - 1:
        maybe_answer_list.append(from_left_gcd[index - 1])
        continue
    maybe_answer_list.append(fractions.gcd(from_left_gcd[index - 1], from_right_gcd[a.__len__() - index - 1 - 1]))
 
print(max(maybe_answer_list))

Submission status: Accepted

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

L = [0]
R = [0]

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

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import*
n,*a=map(int,open(0).read().split())
b=a[:]
for i in range(1,n):
    a[i]=gcd(a[i],a[i-1])
    b[n-i-1]=gcd(b[n-i-1],b[n-i])
a=[0]+a
b+=0,
print(max(gcd(a[i],b[i+1])for i in range(n)))

Submission status: Accepted

Solution code:
def gcd(a,b):
	while b:
		a,b=b,a%b
	return a
n=int(input())
l = list(map(int, input().split()))
ans=1;
m=[0]*(n+1)
o=[0]*(n+1)
for i in range(n):
	m[i+1]=gcd(m[i],l[i])
	o[i+1]=gcd(o[i],l[n-i-1])
for i in range(n):
	ans=max(gcd(m[i],o[n-i-1]),ans)
print(ans)

Submission status: Accepted

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

# 約数
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

devs = make_divisors(As[0])
devs.extend(make_divisors(As[1]))
devs = list(set(devs))
cnt = 1
for dev in sorted(devs)[::-1]:
    a = sum([a%dev==0 for a in As])
    if N - a == 0 or N -a == 1:
        print(dev)
        break

Submission status: Accepted

Solution code:
import fractions

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] = fractions.gcd(l[i-1], A[i-1])
for i in range(1, N+1):
    r[N-i] = fractions.gcd(r[N-i+1], A[N-i])

ans = 0
for i in range(N):
    kouyaku = fractions.gcd(l[i], r[i+1])
    ans = max(ans, kouyaku)

print(ans)

Submission status: Accepted

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

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

ans = max(L[-1],R[-1])
for i in range(1, N-1):
    g = gcd(L[i-1],R[-i-1])
    if g > ans:
        ans = g
print(ans)

Submission status: Accepted

Solution code:
import fractions
 
n = int(input())
a = [int(value) for value in input().split(" ")]

from_right_gcd = []
from_left_gcd = []

# 左から
for index in range(len(a)):
    if index == 0:
        from_left_gcd.append(a[index])
        continue
    from_left_gcd.append(fractions.gcd(from_left_gcd[index - 1], a[index]))

# 右から
for index in range(len(a) - 1, -1, -1):
    if index == len(a) - 1:
        from_right_gcd.append(a[index])
        continue
    from_right_gcd.append(fractions.gcd(from_right_gcd[len(a) - index - 1 - 1], a[index]))

maybe_answer_list = []

for index in range(len(a)):
    if index == 0:
        maybe_answer_list.append(from_right_gcd[len(a) - 1 - 1])
        continue
    if index == len(a) - 1:
        maybe_answer_list.append(from_left_gcd[index - 1])
        continue
    maybe_answer_list.append(fractions.gcd(from_left_gcd[index - 1], from_right_gcd[len(a) - index - 1 - 1]))

print(max(maybe_answer_list))

Submission status: Accepted

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

def factor(n):
	factors = [1, n]
	i=2
	while i*i <= n:
		if n%i==0:
			factors.append(i)
			factors.append(n//i)
		i+=1

	return factors

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

if n==2:
	print(max(A))
	quit()

gcd1 = 0
fac1 = sorted(factor(A[0]),reverse=True)
for i in range(len(fac1)):
	count = 0
	for j in range(1, n):
		if A[j]%fac1[i]!=0:
			count += 1
			if count >= 2:
				break
	if count <= 1:
		gcd1 = fac1[i]
		break

fac2 = sorted(factor(A[1]),reverse=True)
gcd2 = 0
for i in range(len(fac2)):
	count = 0
	for j in range(2, n):
		if A[j]%fac2[i]!=0:
			count += 1
			break
	if count <= 0:
		gcd2 = fac2[i]
		break

print(max(gcd1, gcd2))

Submission status: Accepted

Solution code:
import fractions
# import math
from functools import reduce
 
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
 
n = int(input())
a = [int(value) for value in input().split(" ")]

from_right_gcd = []
from_left_gcd = []

# 左から
for index in range(len(a)):
    if index == 0:
        from_left_gcd.append(a[index])
        continue
    from_left_gcd.append(fractions.gcd(from_left_gcd[index - 1], a[index]))

# 右から
for index in range(len(a) - 1, -1, -1):
    if index == len(a) - 1:
        from_right_gcd.append(a[index])
        continue
    from_right_gcd.append(fractions.gcd(from_right_gcd[len(a) - index - 1 - 1], a[index]))

maybe_answer_list = []

for index in range(len(a)):
    if index == 0:
        maybe_answer_list.append(from_right_gcd[len(a) - 1 - 1])
        continue
    if index == len(a) - 1:
        maybe_answer_list.append(from_left_gcd[index - 1])
        continue
    maybe_answer_list.append(fractions.gcd(from_left_gcd[index - 1], from_right_gcd[len(a) - index - 1 - 1]))

print(max(maybe_answer_list))

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

list1=[0]
L=0
for a in A:
    L=gcd(L,a)
    list1.append(L)

list2=[0]
R=0
for a in reversed(A):
    R=gcd(R,a)
    list2.append(R)

list2.reverse()

ans=[]

for i in range(N):
    ans.append(gcd(list1[i],list2[i+1]))

print(max(ans))

Submission status: Accepted

Solution code:
from copy import deepcopy
def gcd(a,b):
    while b != 0:
        a, b = b, a % b
    return(a)

def factors(n):
    Ret = []
    for i in range(2, int( n**(1/2))+1):
        if n%i == 0:
            Ret.append([])
            t = i
            while n%i == 0:
                Ret[-1].append(t)
                n //= i
                t *= i
    if n != 0:
        Ret.append([n])
    return Ret
    
N = int( input())
A = list( map( int, input().split()))
ans = A[1]
for i in range(1,N):
    ans = gcd(ans, A[i])
Fact = factors(A[0])
C = [1]
for F in Fact:
    D = deepcopy(C)
    for f in F:
        for d in D:
            C.append(d*f)
for g in C:
    check = 0
    for i in range(1,N):
        if A[i]%g != 0:
            check += 1
    if check <= 1:
        if ans < g:
            ans = g
print(ans)

Submission status: Accepted

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


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

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

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

M = [gcd(L[i],R[i]) for i in range(n)]

print(max(M))

Submission status: Accepted

Solution code:
import sys,math,copy
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))