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
from functools import reduce

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

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

res1 = [gcd(A[-1],a) for a in A]

min_res = min(res1)
index = res1.index(min_res)

res1 = [A[i] for i in range(N) if i != index]
res2 = A[:N-1]

res1 = gcd_list(res1)
res2 = gcd_list(res2)

print(max(res1,res2))

Submission status: Accepted

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

if N == 2:
    print(max(A_array[0], A_array[1]))
    exit()

remove_index = []
for i, A in enumerate(A_array):
    if i == 0:
        gcd_max = A
        remove_index.append(i)
        continue
    gcd = fractions.gcd(gcd_max, A)
    # print(i, gcd_max, gcd)
    if gcd_max > gcd:
        gcd_max = gcd
        remove_index.append(i)
# print(remove_index)
# print(gcd_max, remove_index)

gcd_ans = gcd_max
for index in remove_index:
    gcd = 0
    for i, A in enumerate(A_array):
        if i == index:
            continue
        if gcd == 0:
            gcd = A
            continue
        # print(gcd,A)
        gcd = fractions.gcd(gcd, A)
        if gcd_ans >= gcd:
            break
    # print(gcd_ans,gcd)
    gcd_ans = max(gcd_ans, gcd)
print(gcd_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.sort()

inf = int(2e9)

m = inf
check = 0
for i in range(N):
    check1 = gcd(A[0], A[i])
    if check1 < m:
        m = check1
        check = i

# A[0]以外
check2 = A[1]
for i in range(1,N):
    check2 = gcd(check2, A[i])

ans = check2

# check以外
if check != 0:
    check3 = A[0]
    for i in range(N):
        if i == check:
            continue
        check3 = gcd(check3, A[i])
    ans = max(check2, check3)

print(ans)

Submission status: Accepted

Solution code:
import fractions
import numpy as np

N = int(input())
A = np.array(sorted([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

divisors=make_divisors(A[0])
divisors_1=make_divisors(A[1]) 
divisors.extend(divisors_1)

def gcd(l):
    ans = l[0]
    for j in range(1, N-1):
        ans = fractions.gcd(ans, l[j])
    return ans

#res = 1
for i in sorted(list(set(divisors))):
#    print("{} / {}".format(i, A%i))
#    print(np.where(A%i != 0))
#    print((A%i != 0))
    if(np.sum(A%i != 0)<=1):
        #print(i)
        res = i


print(res)

Submission status: Accepted

Solution code:

n = int(input())

a = list(map(int, input().split()))
a.sort(reverse=True)


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def gcd_list(li):
    if len(li) == 1:
        return li[0]
    g = gcd(li[0], li[1])
    for i in range(2, len(li)):
        g = gcd(g, li[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list([li[0]] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, li[i]) == 1:
            if i == n - 1:
                return gcd_list(li[:i])
            gg = gcd_list(li[i+1:])
            bb = [gcd(li[x], gg) for x in range(i+1)]
            bb.sort()
            return bb[1]
        else:
            g = gcd(g, li[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]
    m = gcd_list_2(a)
    print(g * m)


max_gcd(a)

Submission status: Accepted

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

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

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

if n < 1000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 500))
    if ans < t:
      ans = t

print(ans)

Submission status: Accepted

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

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

lgcd = [0]
rgcd = [0]
for i in a:
    lgcd.append(gcd(lgcd[-1], i))

for i in a[::-1]:
    rgcd.append(gcd(rgcd[-1], i))

rgcd = rgcd[::-1]

ans = 1 << 60
print(max([gcd(lgcd[i],rgcd[i+1]) for i in range(n)]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from collections import defaultdict
import copy

N = int(input())
A = sorted(list(map(int, input().rstrip().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)
                
    divisors.sort()
    return divisors
    
max_divisor = 0
for a in A[:2]:
    divisors = make_divisors(a)
    
    for divisor in divisors:
        if divisor > max_divisor:
            nondivisable = 0
            for a in A:
                if a % divisor != 0:
                    nondivisable += 1
                if nondivisable > 2:
                    break
                
            if nondivisable <= 1:
                max_divisor = divisor
            
            
print(max_divisor)

Submission status: Accepted

Solution code:
from fractions import gcd

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

gcd_all = as_.pop()
set_ = {as_[0]}
for a in as_:
    set_ = set(gcd(s, a) for s in set_)
    set_.add(gcd_all)
    gcd_all = gcd(gcd_all, a)

print(max(set_))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
 
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
 
def gcds(n):
    return reduce(gcd, n)
 
n=int(input())
a=list(map(int, input().split()))
a=sorted(a)
# print(a)
m1=a[0]
m2=a[1]
ans=1
divm2=make_divisors(m2)
divm2.reverse()
divm1=make_divisors(m1)
divm1.reverse()
divs=list(set(divm1+divm2))
divs.sort()
divs.reverse()
ans=1
for i in divs:
    count=0
    for j in a:
        if j%i != 0:
            count+=1
        if count>=2:
            break
    if count<=1:
        ans=i
        break
print(ans)

Submission status: Accepted

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

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

gcd_l = []
d = A[0]
for a in A:
    d = gcd(d,a)
    gcd_l.append(d)

gcd_r = []
d = A[-1]
for a in reversed(A):
    d = gcd(d,a)
    gcd_r.append(d)
gcd_r = list(reversed(gcd_r))

gcd_a = [gcd_r[1]]
for i in range(1,N-1):
    gcd_a.append(gcd(gcd_l[i-1], gcd_r[i+1]))
gcd_a.append(gcd_l[N-2])

print(max(gcd_a))

Submission status: Accepted

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

N=int(input())
A=[int(s)for s in input().split()]
A=sorted(A)
if N==2:
  print(A[1])
  exit()
r=[]
for i in range(1,N):
  r.append(gcdf(A[i],A[0]))
r=sorted(r)
gcd=r[1]
for i in range(2,N-1):
  gcd=gcdf(r[i],gcd)
  
gcd2=A[1]
for i in range(2,N):
  gcd2=gcdf(A[i],gcd2)
print(max((gcd,gcd2)))

Submission status: Accepted

Solution code:
import functools
import fractions


N = int(input())
a = list(map(int,input().split()))
ans = 1
gcd = functools.reduce(fractions.gcd,a)
s_front = [1]*N
s_back = [1]*N
s_front[0] = a[0]
s_back[0] = a[N-1]

for i in range(N):
	if i > 0:
		s_front[i] = fractions.gcd(s_front[i-1],a[i])
		s_back[i] = fractions.gcd(s_back[i-1],a[N-i-1])
for i in range(N):
	if i == 0:
		gcd_new = s_back[N-2]
	elif i == N-1:
		gcd_new = s_front[N-2]
	else:
		gcd_new = fractions.gcd(s_front[i-1],s_back[N-i-2])
	ans = max(ans,gcd_new)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def cd(a, b):
  if a == 1 or b == 1:
    return 1

  while a != 0 and b != 0:
    if a < b:
      b %= a
    else:
      a %= b

  return a if a != 0 else b


def main():
  input()
  prevs = list(map(int, input().split()))
  posts = prevs[::-1]

  for i in range(1, len(prevs)):
    prevs[i] = cd(prevs[i - 1], prevs[i])
    posts[i] = cd(posts[i - 1], posts[i])

  posts = posts[::-1]

  gcd = max(prevs[-2], posts[1])

  for i in range(1, len(prevs) - 1):
    gcd = max(cd(prevs[i - 1], posts[i + 1]), gcd)

  print(gcd, flush=True)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
import math
import fractions

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


def inl():
    return list(map(int, input().split()))


def inls():
    return input().split()


def Yesif(cond):
    print('Yes' if cond else 'No')


def YESIF(cond):
    print('YES' if cond else 'NO')


def yesif(cond):
    print('yes' if cond else 'no')


N = inp()
A = inl()

ans = {A[1]}
gcd = A[0]
for a in A[1:]:
    ans = {fractions.gcd(r, a) for r in ans}
    ans.add(gcd)
    gcd = fractions.gcd(gcd, a)

print(max(ans))

Submission status: Accepted

Solution code:
import math
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
from_left = [0 for i in range(N)]
from_right = [0 for i in range(N)]
from_left[0] = A[0]
from_right[-1] = A[-1]
for i in range(1, N):
    from_left[i] = fractions.gcd(A[i], from_left[i-1])
for i in range(N-2, -1, -1):
    from_right[i] = fractions.gcd(A[i], from_right[i+1])
# print(from_left)
# print(from_right)
ans = max(from_left[-2], from_right[1])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(from_left[i-1], from_right[i+1]))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
import queue
import re
import math
import functools
import numpy

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

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


N = int_raw()
As = ints_raw()


def main():
    f_gcds = [As[0]]
    for i in range(1,N):
        f_gcds.append(gcd(As[i],f_gcds[-1]))
    b_gcds = [0]*(N-1)+[As[-1]]
    for i in range(N-2,-1,-1):
        b_gcds[i] = gcd(As[i],b_gcds[i+1])
    ans = max(b_gcds[1],f_gcds[-2])
    for i in range(1,N-1):
        ans = max(ans,gcd(f_gcds[i-1],b_gcds[i+1]))
    return ans

print(main())

Submission status: Accepted

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

n = input()
a_list = map(int, raw_input().split())

gs1 = [None] * n
gs1[0] = a_list[0]
for i in xrange(1, n):
    gs1[i] = gcd(gs1[i - 1], a_list[i])

gs2 = [None] * n
gs2[n - 1] = a_list[n - 1]
for i in reversed(xrange(n - 1)):
    gs2[i] = gcd(gs2[i + 1], a_list[i])

max_g = 0
for exclude in xrange(n):
    if exclude == 0:
        g = gs2[1]
    elif exclude == n - 1:
        g = gs1[n - 2]
    else:
        g = gcd(gs1[exclude - 1], gs2[exclude + 1])
    if g > max_g:
        max_g = g
print(max_g)

Submission status: Accepted

Solution code:
from functools import reduce
inf = 10**10
import sys
input = sys.stdin.readline


def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
def gcd_list(numbers):
    return reduce(gcd,numbers)
n = int(input())
a = list(map(int,input().split()))
index = inf
if n == 2:
    print(max(a))
else:
    a.sort()
    if gcd(a[0],a[n-1]) == 1:
        print(max(gcd_list(a[1:n]),gcd_list(a[0:n-1])))
    else:
        ans = gcd(a[0],a[n-1])
        for i in range(1,n-1):
            if gcd(a[i]-a[0],a[n-1]-a[i]) <= ans:
                index = i
                ans = gcd(a[i]-a[0],a[n-1]-a[i])
        print(max(gcd_list(a[0:index]+a[index+1:n]),gcd_list(a[1:n]),gcd_list(a[0:n-1])))

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
def GCD(x,y):
	if x>y:
		a=x
		b=y
	else:
		a=y
		b=x
	while(True):
		c=a%b
		if c==0:
			return b
		else:
			a,b=b,c
 

if N==2:
	print(max(A))
else:
	B=[]
	a0=A[-1]
	for aa in A[0:-1]:
		B.append(GCD(aa,a0))
	gomikamo=B.index(min(B))
	g0=A[0]
	for i in range(0,N-1):
		g0=GCD(A[i],g0)
	del A[gomikamo]
	g1=A[0]
	for i in range(N-1):
		g1=GCD(A[i],g1)
	print(max(g0,g1))

Submission status: Accepted

Solution code:
import fractions

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

gcd = fractions.gcd(A[0], A[1])
ag = {A[0], A[1]}

for d in A[2:]:
    gc = fractions.gcd(gcd, d)
    ag2 = set()
    for c in ag:
        ag2.add(fractions.gcd(c, d))
    ag = ag2
    ag.add(gcd)
    gcd = gc

print(max(ag))

Submission status: Accepted

Solution code:
import random
from operator import itemgetter
import sys
sys.setrecursionlimit(1000000)
ans=0

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

def gcd_all(l):
    rt=l.pop()
    for i in l:
        rt=gcd(i,rt)
    return rt
    
n=int(input())

g=[]

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

ans=0
d=a[-1]
m=a[-1]
mi=-1
k1=[]
flg=0
for i in range(n):
    gg=gcd(a[i],d)
    if gg<m:
        m=gg
        mi=i
ans=max(ans,gcd_all(a[:mi]+(a[mi+1:] if mi+1<n else [])))

d=a[0]
m=a[0]
mi=0
k1=[]
flg=0
for i in range(n):
    gg=gcd(a[i],d)
    if gg<m:
        m=gg
        mi=i
ans=max(ans,gcd_all(a[:mi]+(a[mi+1:] if mi+1<n else [])))

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

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

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

res = 0
for i in range(n):
    res = max(gcd(pre[i], post[n - 1 - i]), res)

print(res)

Submission status: Accepted

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

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

if N == 2:
    print(max(A))
else:
    ans = gcd(A[0], A[1])
    ans2 = max(gcd(A[0], A[2]), gcd(A[1], A[2]))
    for a in A[2:]:
        ans2 = max(gcd(a, ans2), ans)
        ans = gcd(a, ans)
    
    print(ans2)

Submission status: Accepted

Solution code:
import queue

"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
def newton(a,b):
	if b == a:
		return a
	if a>b:
		(a,b) = (b,a)
	while b%a != 0:
		b = b%a
		(a,b) = (b,a)
	return a
N = int(input())
A = [int(i) for i in input().split()]
l = []
r = []

l.append(A[0])
r.append(A[-1])

for i in range(1,N):
	l.append(newton(l[-1],A[i]))
	r.append(newton(r[-1],A[-(i+1)]))
m = max(l[-2],r[-2])
for i in range(1,N-1):
	m = max(m,newton(l[i-1],r[N-2-i]))
print(m)

Submission status: Accepted

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

B.sort()

def gcd(a,b):
    Y=max(a,b)
    X=min(a,b)
    while Y%X!=0:
        X,Y=Y%X,X
    return X

dp=[[0,0,0]for i in range(N)]
dp[0][0]=B[0]
dp[1][0]=gcd(B[0],B[1])
dp[1][1]=B[0]
dp[1][2]=B[1]

for i in range(2,N):
    dp[i][0]=gcd(dp[i-1][0],B[i])
    dp[i][1]=dp[i-1][0]
    dp[i][2]=max(gcd(dp[i-1][1],B[i]),gcd(dp[i-1][2],B[i]))
print(max(dp[N-1]))
#print(dp)

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

# 最大公約数
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

## 高々3種類調べれば良い

if N > 2:
    devs = make_divisors(gcd(As[0],As[1]))
    devs.extend(make_divisors(gcd(As[1],As[2])))
    devs.extend(make_divisors(gcd(As[2],As[0])))
    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
else:
    print(max(As))

Submission status: Accepted

Solution code:
n=int(input())
a = list(map(int,input().split()))
a.sort()
 
def gcd(a,b):
  if a>b:
    return gcd(b,a)
  else:
    if b%a==0:
      return a
    else:
      return gcd(b%a,a)

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

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

Submission status: Accepted

Solution code:
import fractions

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

def gcd3(nums):
    ans1 = fractions.gcd(nums[0], nums[1])
    ans2 = fractions.gcd(nums[0], nums[2])
    ans3 = fractions.gcd(nums[1], nums[2])

    if ans1 >= ans2 and ans1 >= ans3:
        return ans1, nums[2]
    if ans2 >= ans1 and ans2 >= ans3:
        return ans2, nums[1]
    if ans3 >= ans1 and ans3 >= ans2:
        return ans3, nums[0]

ans = 0
if n == 2:
    ans = max(aList)
else:
    sList = []
    sList.append(aList.pop(0))
    sList.append(aList.pop(0))
    sList.append(aList.pop(0))
    ans, v = gcd3(sList)

    for i in range(len(aList)):
        tmp = aList.pop(0)
        tmp1 = fractions.gcd(ans, v)
        tmp2 = fractions.gcd(ans, tmp)
        if tmp1 >= tmp2:
            ans = tmp1
            v = tmp
        else:
            ans = tmp2

print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import fractions
from functools import reduce



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

def gcd(nums):
    return reduce(fractions.gcd,nums)

ans = 1
A.sort()
gcd1 = gcd(A)
for i in range(N):
    A[i] //= gcd1

ans *= gcd1

gcd2 = A[0]
for i in range(1,N):
    gcd2 = fractions.gcd(gcd2,A[i])
    if gcd2 == 1:
        key = i
        break

a = copy.deepcopy(A)
a.remove(A[0])
if gcd(a)!=1:
    ans *= gcd(a)
    print(ans)
    exit()

a = copy.deepcopy(A)
a.remove(A[key])
if gcd(a)!=1:
    ans *= gcd(a)
    print(ans)
    exit()
print(ans)

Submission status: Accepted

Solution code:
N = int(input())                                     
A = list(map(int, input().split()))                  
def gcd(a,b):                                        
    if b > a:                                        
        a, b = b, a                                  
    if b == 0:                                       
        return(a)                                    
    else:                                            
        return(gcd(b, a % b))                        
dp = [0 for i in range(N)]                           
dp[0] = A[0]                                         
for i in range(1,N):                                 
    dp[i] = gcd(dp[i-1] , A[i])                      
dpr = [0 for i in range(N)]                          
dpr[N-1] = A[N-1]                                    
for i in range(N-2,-1,-1):                           
    dpr[i] = gcd(dpr[i+1],A[i])                      
maxgcd = dpr[1]                                      
for i in range(1,N-1):                               
    maxgcd = max(maxgcd, gcd(dp[i-1], dpr[i+1]))     
maxgcd = max(maxgcd,dp[N-2])                         
print(maxgcd)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = sorted(list(map(int, input().split())))
if N == 2:
    print(max(A))
    exit()
result = []
num = 0
for a in A[1:]:
    if a % A[0] != 0:
        num += 1
        if num == 2:
            break
else:
    result.append(A[0])
for n in range(2, int(math.sqrt(A[0])) + 1):
    if A[0] % n != 0:
        continue
    num = 0
    x = A[0] // n
    for a in A[1:]:
        if a % x != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(x)
    num = 0
    for a in A[1:]:
        if a % n != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(n)
num = 0
B = A[0:1] + A[2:]
for a in B:
    if a % A[1] != 0:
        num += 1
        if num == 2:
            break
else:
    result.append(A[1])
for n in range(2, int(math.sqrt(A[1])) + 1):
    if A[1] % n != 0:
        continue
    num = 0
    x = A[1] // n
    for a in B:
        if a % x != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(x)
    num = 0
    for a in B:
        if a % n != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(n)
if len(result) != 0:
    print(max(result))
else:
    print(1)

Submission status: Accepted

Solution code:
n=int(input())
a = list(map(int,input().split()))
a.sort()
 
def gcd(a,b):
  if a>b:
    return gcd(b,a)
  else:
    if b%a==0:
      return a
    else:
      return gcd(b%a,a)

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
min_ptn = A[1]
for i in range(min_ptn,0,-1):
  count = 0
  for a in A:
    if a%i!=0:
      count+=1
    if count>1:
      break
  if count<2:
    print(i)
    break

Submission status: Accepted

Solution code:
from functools import reduce
N = int(input())
A = list(map(int,input().split()))
A.sort()
def gcd(a, b): # 最大公約数
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a % b
    return a
g0 = reduce(gcd,A[1:])

now = A[0]

id = 0
for i in range(1,N):
    ne = gcd(now,A[i])
    if ne < now:
        id = i
        now = ne
A.pop(id)

g = reduce(gcd,A)
print(max(g,g0))

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.sort()
if n == 2:
    print(max(a))
else:
    a1 = gcd(a[0],a[1])
    a2 = gcd(a[1],a[2])
    a3 = gcd(a[2],a[0])
    m = max(a1,a2,a3)
    judge = 0
    for i in range(m):
        if judge == 1:
            break
        cnt = 0
        for j in range(n):
            if a[j] % (m-i) != 0:
                cnt += 1
            if cnt > 1:
                break
            if j == n-1 and cnt <= 1:
                print(m-i)
                judge = 1

Submission status: Accepted

Solution code:
import math 
N = int(input())
A= list(map(int,input().split()))
memo_gcd_foward = [A[0]]
memo_gcd_backward = [A[N-1]]

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

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

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


cand = []
cand.append(memo_gcd_foward[-1])
cand.append(memo_gcd_foward[-2])
cand.append(memo_gcd_backward[-2])

for i in range(N-2):
    cand.append(gcd(memo_gcd_foward[i],memo_gcd_backward[-i-3]))
print(max(cand))

Submission status: Accepted

Solution code:
from fractions import gcd

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

if N == 2:
    ans = max(A)

else:
    memo = {(0,0):1, (N,N):1}

    for i in range(1,N+1):

        if i == 1:
            memo[(0,1)] = A[0]
            memo[(N-1,N)] = A[-1]

        else:

            # gcd first i
            memo[(0,i)] = gcd(memo[(0,i-1)], A[i-1])

            # gcd last i
            memo[(N-i,N)] = gcd(memo[(N-i+1,N)], A[-i])

    ans = memo[(0,N)]

    for i in range(1,N+1):

        if i == 1:
            curgcd = memo[(1,N)]
        elif i == N:
            curgcd = memo[(0,N-1)]
        else:
            curgcd = gcd(memo[(0,i-1)], memo[(i,N)])

        ans = max(ans, curgcd)

print(ans)

Submission status: Accepted

Solution code:
import sys


def gcd(a, b):
    """Euclidean Algorithm"""
    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()))
    A = sorted(A)

    if N == 2:
        return A[1]

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

    g = A[0]
    B = []
    for a in A:
        g = gcd(a, g)
        B.append(g)

    i = B.index(g)
    A.pop(i)

    g = A[0]
    for a in A:
        g = gcd(g, a)

    return max(g, g0)


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

Submission status: Accepted

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

nums = A[:]
import fractions

gcd_queue = [
    (nums[0], True),
    (nums[1], True),
    (fractions.gcd(nums[0], nums[1]), False),
]
for n in nums[2:]:
    tmp_queue = []
    for q in gcd_queue:
        if q[1] == True:
            tmp_queue.append((fractions.gcd(q[0], n), True))
        else:
            tmp_queue.append((fractions.gcd(q[0], n), False))
            tmp_queue.append((q[0], True))
    gcd_queue = set(tmp_queue[:])

ans = 0
for q in gcd_queue:
    ans = max(ans, q[0])
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()))
a.sort()

g_left = []
g_right = []

t = a[0]
for i in range(N):
    t = gcd(t, a[i])
    g_left.append(t)

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

g_right.reverse()

g = 1
for i in range(1, N - 1):
    g = max(g, gcd(g_left[i - 1], g_right[i + 1]))
g = max(g, g_left[N - 2])
g = max(g, g_right[1])

print(g)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int,input().split()))
As.sort(reverse=True)
first_d = As[0]
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

if N == 2:
    print(max(As))
else:
    first = make_divisors(As[0])
    second = make_divisors(As[1])
    third  = make_divisors(As[2])
    div_list = list((set(first) & set(second)) | (set(first) & set(third)) | (set(third) & set(second)))
    div_list.sort(reverse=True)
    
    for d in range(len(div_list)):
        cnt = 0
        for i in range(N):
            if As[i] % (div_list[d]) != 0:
                cnt += 1
                if cnt > 1:
                    break
        if cnt <= 1 :
            ans = div_list[d]
            break
    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in sys.stdin.readline().split()]


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


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N = int(input())
    A = sorted(li_input(), reverse=True)

    ans = 10**100
    ans_i = -1

    for i in range(len(A)-1):
        g = gcd(A[-1], A[i])

        if g < ans:
            ans = g
            ans_i = i

    print(max(
        gcd_list(A[:-1]),
        gcd_list(A[:ans_i] + A[ans_i+1:])
    ))


main()

Submission status: Accepted

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

def readInts():
  return [int(s) for s in input().split(" ")]

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

def gcds(A):
  ret = A[0]
  for n in A[1:]:
    ret = gcd(ret, n)
  return ret

def main():
  N = readInts()[0]
  A = readInts()

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

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

  m = 1
  for i in range(N):
    if i == 0:
      m = max(m, rgcds[i+1])
    elif i == N - 1:
      m = max(m, lgcds[i-1])
    else:
      m = max(m, gcd(lgcds[i-1], rgcds[i+1]))
  print(m)

if __name__ == "__main__":
  main()