Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

3
7 6 8

Sample Output 1

2

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

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))

Submission status: Accepted

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


def com(x, y):
    """ユークリッド互除法
    """
    if x == 0:
        return y
    if y == 0:
        return x
    a = max(x, y)
    b = min(x, y)
    c = a % b
    if c == 0:
        return b
    else:
        return com(b, c)


L = [0]
R = [0]

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

M = []
for i in range(N):
    M.append(com(L[i], R[N-1-i]))

print(max(M))

Submission status: Accepted

Solution code:
from fractions import gcd
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
L=[0]
R=[0]
MAX=0
for i in range(N-1):
    L.append(gcd(L[i],A[i]))
    R.append(gcd(R[i],A[-1-i]))
for i in range(N):
    MAX=max(MAX,gcd(L[i],R[-1-i]))
print(MAX)

Submission status: Accepted

Solution code:
import fractions

integral_count = int(input())
blackboard_integers = list(map(int, input().split()))

gcd_integers = list(set(blackboard_integers))
gcds = [0] * len(gcd_integers)
for i in range(len(gcd_integers)):
    if blackboard_integers.count(gcd_integers[i]) >= 2:
        for n in gcd_integers:
            gcds[i] = fractions.gcd(gcds[i], n)
    else:
        for n in gcd_integers[:i]:
            gcds[i] = fractions.gcd(gcds[i], n)
        for n in gcd_integers[i+1:]:
            gcds[i] = fractions.gcd(gcds[i], n)

print(max(gcds))

Submission status: Accepted

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

n = int(input())
a = list(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,0,-1):
  y[i-1] = gcd(y[i],a[i])

z = [gcd(x[i],y[i]) for i in range(n)]

print(max(z))

Submission status: Accepted

Solution code:
import fractions

integral_count = int(input())
blackboard_integers = list(map(int, input().split()))

gcd_integers = list(set(blackboard_integers))

gcd = 0
result = 1
for i in range(len(gcd_integers)):
    gcd = 0
    if blackboard_integers.count(gcd_integers[i]) >= 2:
        for n in gcd_integers:
            gcd = fractions.gcd(gcd, n)
    else:
        for n in gcd_integers[:i]:
            gcd = fractions.gcd(gcd, n)
        for n in gcd_integers[i+1:]:
            gcd = fractions.gcd(gcd, n)
    if gcd > result:
        result = gcd

print(result)

Submission status: Accepted

Solution code:
def euclid(a, b):
    if a < b:
        b, a = a, b
    if b == 0:
        return a

    return euclid(b, a % b)

if __name__ == "__main__":
    N = int(input())
    a_list = list(map(int, input().split()))

    l_list = [0] * (N + 1)
    r_list = [0] * (N + 1)

    for i in range(N):
        l_list[i + 1] = euclid(l_list[i], a_list[i])
    for i in reversed(range(N)):
        r_list[i] = euclid(r_list[i + 1], a_list[i])

    max_m = 0
    for i in range(N):
        m = euclid(l_list[i], r_list[i + 1])
        max_m = max(m, max_m)
    print(max_m)

Submission status: Accepted

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

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

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

right_gcd = [A[-1]]
for i in reversed(A[0:-1]):
    right_gcd.append(gcd(right_gcd[-1],i))
right_gcd.reverse()

gcd_lst = [right_gcd[1]] + [gcd(right_gcd[i+1], left_gcd[i-1]) for i in range(1,len(A)-1)] + [left_gcd[-2]]
print(max(gcd_lst))

Submission status: Accepted

Solution code:
from fractions import*
n,*a=map(int,open(0).read().split())
p=gcd(a[0],a[1])
l=[a[0],p]
c=list(reversed(a))
q=gcd(c[0],c[1])
r=[q]
for i in range(1,n-1):
    p=gcd(p,a[i+1])
    l.append(p)
    q=gcd(q,c[i+1])
    r.append(q)

r=r[::-1]+[a[-1]]
r=r[1:]+[0]
l=[0]+l

print(max(gcd(s,t)for s,t in zip(r,l)))

Submission status: Accepted

Solution code:
import fractions

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

l = [0]*n
r = [0]*n

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

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

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

Submission status: Accepted

Solution code:
N=int(input())+2
A=[0]+list(map(int,input().split(" ")))+[0]

import fractions
from functools import reduce

proc = lambda x: reduce(fractions.gcd, x)

GCD_L=[0 for x in range(N)]

for i in range(N-1):
    l=[GCD_L[i], A[i]]
    GCD_L[i+1]=proc(l)

GCD_R=[0 for x in reversed(range(N))]

for i in reversed(range(N-1)):
    l=[GCD_R[i+1], A[i]]
    GCD_R[i]=proc(l)

M = [0 for x in range(N-1)]

for i in range(N-1):
    l=[GCD_L[i], GCD_R[i+1]]
    M[i]=proc(l)

print(max(M))

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from collections import deque
from functools import *
from itertools import *

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

def gcd_acc(acc, x):
    if len(acc) == 0:
        acc.append(x)
        return acc
    last = acc[-1]
    acc.append(gcd(last, x))
    return acc

def candidates(As):
    length = len(As)
    L = iter(reduce(gcd_acc, As, deque()))
    R = reversed(reduce(gcd_acc, reversed(As), deque()))
    next(R)

    yield next(R)

    if length == 1:
        return

    for _ in range(length-2):
        yield gcd(next(L), next(R))
        pass
    yield next(L)
    pass

print(max(candidates(As)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

# 左側の0番目からi番目までの整数のgcd
gcd_left = [0]*N
# 右側のN-1番目からi番目までの整数のgcd
gcd_right = [0]*N

for i in range(N):
  gcd_left[i] = gcd(gcd_left[i-1], A[i]) if i>0 else A[i]
  gcd_right[N-(i+1)] = gcd(gcd_right[N-i], A[N-(i+1)]) if i > 0 else A[N-1]

ans = 0
# i番目の数字を変えたときのgcd
for i in range(N):
  kouho = gcd(gcd_left[i-1] if i>0 else gcd_right[i+1], gcd_right[i+1] if i < N-1 else gcd_left[i-1])
  if ans < kouho:
    ans = kouho
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from functools import *
from itertools import *

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

def gcd(a, b):
    if a == 0 or b == 0:
        return max(a, b)
    a , b = (a, b) if a > b else (b, a)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
        pass
    return b

def gcd_acc(acc, x):
    if len(acc) == 0:
        acc.append(x)
        return acc
    last = acc[-1]
    acc.append(gcd(last, x))
    return acc

def candidates(As):
    length = len(As)
    L = iter(reduce(gcd_acc, As, deque()))
    R = reversed(reduce(gcd_acc, reversed(As), deque()))
    next(R)

    yield next(R)

    if length == 1:
        return

    for _ in range(length-2):
        yield gcd(next(L), next(R))
        pass
    yield next(L)
    pass

print(max(candidates(As)))

Submission status: Accepted

Solution code:
#import numpy as np

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

#A=np.array(A)






#大きい方から
for i in range(sorted(A)[1],1,-1):
#	if(np.sum(A%i==0)>=N-1):
	
	#check
	b=0
	j=0
	while(b<2):
		if(j==N):
			print(i)
			exit()
		if(A[j]%i!=0):
			b+=1
		j+=1
print(1)

Submission status: Accepted

Solution code:
import fractions
n=int(input())
a=list(map(int,input().split()))
l=[a[0]]
r=[a[-1]]
for i in range(n-2):
    l.append(fractions.gcd(l[i],a[i+1]))
    r.append(fractions.gcd(r[i],a[n-i-2]))
ans=0
for t in range(n):
    if t==0:
        gcd=r[-1]
    elif t==n-1:
        gcd=l[-1]
    else:
        gcd=fractions.gcd(l[t-1],r[-1-t])
    if ans<gcd:
        ans=gcd
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
a_list = [int(x) for x in input().split()]
L = [0]
R = [0]

for i in range(1, N):
    L.append(gcd(L[i-1], a_list[i-1]))
    R.append(gcd(R[i-1], a_list[N-i]))
R.reverse()
ans = 0
for i in range(N):
    ans = max(gcd(L[i], R[i]), ans)
print(ans)

Submission status: Accepted

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

n = int(input())
a = list(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,0,-1):
    y[i-1] = gcd(y[i],a[i])

z = [gcd(x[i],y[i]) for i in range(n)]

print(max(z))

Submission status: Accepted

Solution code:
import math

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort(reverse = True)
    return divisors

A.sort()
l0 = make_divisors(A[0])
l1 = make_divisors(A[1])

if n == 2:
    gcd_max = max(A[0], A[1])
else:
    for d in l1:
        count = 0
        for i in range(2, n):
            if A[i] % d != 0:
                count += 1
            if count > 0:
                break
        if count == 0:
            gcd1 = d
            break
    for d in l0:
        count = 0
        for i in range(1, n):
            if A[i] % d != 0:
                count += 1
            if count > 1:
                break
        if count <= 1:
            gcd2 = d
            break
    gcd_max = max(gcd1, gcd2)

print(gcd_max)

Submission status: Accepted

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

def solve():
    N = int(raw_input())
    arr = [int(_) for _ in raw_input().split()]
    left = [0] * (N + 1)
    right = [0] * (N + 1)
    left[0] = 0
    right[N] = 0
    for i in range(1, N+1):
        left[i] = gcd(left[i - 1], arr[i - 1])
    for i in range(N - 1, 0, -1):
        right[i] = gcd(right[i + 1], arr[i])
    max_gcd = 0
    for i in range(N):
        max_gcd = max(max_gcd, gcd(left[i], right[i+1]))
    print str(max_gcd)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#ABC125C-GCDonBlackboard.py

from sys import stdin
from sys import setrecursionlimit
#import random
from fractions import gcd
from functools import lru_cache

setrecursionlimit(1000000)

input = stdin.readline

N = int(input())
A = list(map(int, input().split()))
#A = [random.randrange(1,10**9) for _ in range(N)]

@lru_cache(maxsize=None)
def L(i):
    if i == 0:
        return 0
    else:
        return gcd(L(i-1),A[i-1])

@lru_cache(maxsize=None)
def R(i):
    if i == N:
        return 0
    else:
        return gcd(R(i+1),A[i])

M = []

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()))
L_A = [0] * (N+1)
R_A = [0] * (N+1)#
for i in range(N):
    L_A[1+i] = gcd(L_A[i], A[i])
for i in reversed(range(N)):
    R_A[i] = gcd(R_A[i+1], A[i])
print(max(gcd(L_A[i], R_A[i+1]) for i in range(N)))

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
L_A = [0] * (N+1)
R_A = [0] * (N+1)
for i in range(N):
    L_A[1+i] = gcd(L_A[i], A[i])
for i in reversed(range(N)):
    R_A[i] = gcd(R_A[i+1], A[i])
print(max(gcd(L_A[i], R_A[i+1]) for i in range(N)))

Submission status: Accepted

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

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]

L[0], R[N - 1] = A[0], A[N - 1]

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

print(max(L[N-2], R[1], *(gcd(L[i], R[i+2]) for i in range(N-2))))

Submission status: Accepted

Solution code:
from fractions import gcd
# input
N = int(input())
A = list(map(int,input().split()))
L_A = [0] * (N+1)
R_A = [0] * (N+1)
for i in range(N):
    L_A[1+i] = gcd(L_A[i], A[i])
for i in reversed(range(N)):
    R_A[i] = gcd(R_A[i+1], A[i])
print(max(gcd(L_A[i], R_A[i+1]) for i in range(N)))

Submission status: Accepted

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

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

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

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

ans = max([gcd(l,r) for l,r in zip(L,R)])
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

l = [0 for i in range(n+1)]
r = [0 for i in range(n+1)]
l[1] = a[0]
r[n-1] = a[n-1]
for i in range(2, n+1):
  l[i] = fractions.gcd(l[i-1], a[i-1])
  r[n-i] = fractions.gcd(r[n-i+1], a[n-i])
  
max_gcd = 1
for i in range(n):
  if l[i] == 0 or r[i+1] == 0:
    gcd_ = l[i] + r[i+1]
  else:
    gcd_ = fractions.gcd(l[i], r[i+1])
  max_gcd = max(max_gcd, gcd_)
print(max_gcd)

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
oc = []
b = 0
for i, v in c.items():
    if v == 1:
        oc.append(i)
    else:
        if b == 0:
            b = i
        else:
            b = gcd(b, i)

loc = len(oc)
if loc <= 1:
    print(b)
    exit()

c = [oc[0], oc[1]]
e = gcd(oc[0], oc[1])
if loc == 2:
    c.append(e)
for i in range(2, loc):
    g1 = gcd(e, oc[i])
    d = []
    for cc in c:
        g2 = gcd(cc, oc[i])
        if g2 > 1:
            d.append(g2)
    c = d
    if e > 1:
        c.append(e)
    if i == loc-1:
        c.append(g1)
    e = g1

if b >= 2:
    print(max([gcd(cc, b) for cc in c]))
elif b == 0:
    print(max(c))
else:
    print(1)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

N = int(input())
A = [int(a) for a in input().split(" ")]
if N==2:
    print(max(A))
else:
    left, right = [-1]*(N-1), [-1]*(N-1)
    lacc, racc = (A[0], A[-1])
    for i in range(N-1):
        lacc, racc = gcd(lacc, A[i]), gcd(racc, A[N-1-i])
        left[i], right[i] = lacc, racc
    ans = max(right[-1], left[-1])
    for l, r in zip(left[:-1], reversed(right[:-1])):
        ans = max(ans, gcd(l,r))
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline

    def init(init_val):
        #set_val
        for i in range(n):
            seg[i+num-1]=init_val[i]    
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=gcd(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        k += num-1
        seg[k] = x
        while k+1:
            k = (k-1)//2
            seg[k] = gcd(seg[k*2+1],seg[k*2+2])
        
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = gcd(res,seg[p])
            if q&1 == 1:
                res = gcd(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = gcd(res,seg[p])
        else:
            res = gcd(gcd(res,seg[p]),seg[q])
        return res



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

    #####単位元######
    ide_ele = 0

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

    ans = -1
    for i in range(n):
        ans = max(ans,gcd(query(0,i),query(i+1,n)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if y == 0:
        return x
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z

L = [0 for _ in range(len(A))]
for i,a in enumerate(A[:-1]):
    L[i+1] = gcd(L[i],a)
R = [0 for _ in range(len(A))]
for i,a in enumerate(A[:0:-1]):
    R[i+1] = gcd(R[i],a)
R = R[::-1]

G = 0
for l,r in zip(L,R):
    g = gcd(l,r)
    if G < g:
        G = g

print(G)

Submission status: Accepted

Solution code:

def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline

    
    def init():
        #set_val
        for i in range(n):
            seg[i+num-1]=a[i]    
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=gcd(seg[2*i+1],seg[2*i+2]) 
    
    def update(k,z):
        k += num
        seg[k] = x
        while k+1:
            k = (k-1)//2
            date[k] = gcd(seg[k*2+1],seg[k*2+2])
    
    def query(p,q):
        if p>n-1 or q<1:
            return 0
        if abs(q-p)<=1:
            return a[p]
        p += num-1
        q += num-2
        res=0
        while q>p:
            if p&1 == 0:
                res = gcd(res,seg[p])
            if q&1 == 1:
                res = gcd(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        res = gcd(res,seg[p])
        return res
 
    n = int(input())
    a = tuple(map(int,input().split()))

    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[0]*2*num
    
    init()
 
    ans = -1
    for i in range(n):
        ans = max(ans,gcd(query(0,i),query(i+1,n)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def GCD( a,  b ):
    if b == 0:
        # print("--" * 10)
        return a
    else:
        # print(b)
        return GCD(b, a % b)

N = int(input())
As = list(map(int,input().split(" ")))

left = [0]

for i,A in enumerate(As[:]):
    left.append(GCD(A,left[i]))
Bs = As[::-1]
right = [0]

for i,B in enumerate(Bs[:]):
    right.append(GCD(B,right[i]))
# print(left)
# print(right)

left = left[::-1]

ans = []
for i in range(0,N):
    ans.append(GCD(left[i+1],right[i]))
print(max(ans))

Submission status: Accepted

Solution code:
import fractions


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

gcd_L=[]
gcd_R=[]

L=a[0]
for i in range(n):

    L=fractions.gcd(L,a[i])
    gcd_L.append(L)

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

    R=fractions.gcd(R,a[n-i-1])
    gcd_R.append(R)


# print(gcd_L)
# print(gcd_R)

ans=gcd_R[n-2]

for i in range(1,n-1):
    ans = max(ans,fractions.gcd(gcd_L[i-1],gcd_R[n-i-2]))


ans= max(ans,gcd_L[n-2])

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

L = [0]*(N+2)
R = [0]*(N+2)

gcd = fractions.gcd

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

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

#print(L,R)

M = []
for i in range(N):
    M.append(gcd(L[i],R[i+2]))

print(max(M))

Submission status: Accepted

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

n = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
for i in range(n):
	L.append(gcd(L[i], A[i]))
	R.append(gcd(R[i], A[-(i + 1)]))
R = R[::-1]

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

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x
 
N = int(input())
lst = [int(x) for x in input().split()]
 
l = [0] * N
r = [0] * N
 
l[0] = lst[0]
r[-1] = lst[-1]
 
for i in range(1, N):
    l[i] = gcd(l[i-1], lst[i])
 
for i in range(N-2, -1, -1):
    r[i] = gcd(r[i+1], lst[i])

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

Submission status: Accepted

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

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

index = list(range(N))
L = index.copy()

L[0] = 0
for i in index[:-1]:
    #print(i)
    L[i+1] = gcd(L[i], A[i])

R = index.copy()
R.append(0)
for i in reversed(index):
    #print(i)
    R[i] = gcd(R[i+1], A[i])

# confirm
#print(L)
#print(R)

M = []
for j in range(len(L)):
    m = gcd(L[j], R[j+1])
    #print(m)
    M.append(m)

# Confirm
#print(M)

# Answer
print(max(M))

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
L=[0]
R=[0]
for i in range(n):
    L.append(gcd(L[i],A[i]))
    R.append(gcd(R[i],A[-(i+1)]))
R=R[::-1]

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
L=[0]*(n+1)
R=[0]*(n+1)
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
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=[]
for k in range(n):
    ans.append(gcd(L[k],R[k+1]))
print(max(ans))

Submission status: Accepted

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

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

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

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

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

max_gcd = r_GCD[1]
for i in range(1, n-1):
	left = l_GCD[i-1]
	right = r_GCD[i+1]
	max_gcd = max(max_gcd, gcd(left, right))
max_gcd = max(max_gcd, l_GCD[-2])

print(max_gcd)

Submission status: Accepted

Solution code:
import fractions
n = int(input())
a = [0] + list(map(int,input().split())) + [0]


#はじめと最初の値を代入
L = [0] * (n+2)
R = [0] * (n+2)

for i in range(n):
    L[i+1] = fractions.gcd(L[i], a[i+1])

for j in range(n,0,-1):
    R[j] = fractions.gcd(R[j+1],a[j])

#print(a)
#print(L)
#print(R)

print(max(fractions.gcd(L[k-1],R[k+1]) for k in range(1,len(L)-1)))

Submission status: Accepted

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

a=input()
b=list(map(int,input().split()))
l=[0]
r=[0]
g=[]
for a in range(len(b)-1):
    l.append(gcd(l[-1],b[a]))
    r.append(gcd(r[-1],b[-1-a]))
for a in range(len(l)):
    g.append(gcd(l[a],r[-1-a]))
print(max(g))

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_gcd = [0]*(N+1)
R_gcd = [0]*(N+1)

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

ans = 0
for i in range(N):
    if gcd(L_gcd[i],R_gcd[i+1])>ans:
        ans = gcd(L_gcd[i],R_gcd[i+1])
    
print(ans)

Submission status: Accepted

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

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

L = [0] * (N + 2)
R = [0] * (N + 2)

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

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

print(max(fractions.gcd(L[i], R[i + 2]) for i in range(0, N)))

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
a = [int(i) for i in input().split()]
a.sort()
a=deque(a)
a.appendleft(0)
a.append(a[-1])
#print(n,a)

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

left=deque([0 for i in range(n)])
left[0]=gcd(a[0],a[1])
for i in range(1,n):
  left[i]=gcd(left[i-1],a[i+1])
#print(left)

right=deque([0 for i in range(n)])
right[-1]=gcd(a[-1],a[-2])
for i in range(-2,-1-n,-1):
  right[i]=gcd(right[i+1],a[i-1])
#print(right)

ans=right[1]
for i in range(n-2):
  val=gcd(left[i],right[i+2])
  if ans < val:
    ans=val
if ans < left[-2]:
  ans=left[-2]
  
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
# import numpy as np
# import math
import fractions as math
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]

gcd_l = [0,A[0]]
gcd_r = [0,A[N-1]]
gcd_ = A[0]
for i in range(1, N-1):
  gcd_ = math.gcd(gcd_,A[i])
  gcd_l.append(gcd_)

gcd_ = A[N-1]
for i in range(1, N-1):
  gcd_ = math.gcd(gcd_, A[N-1-i])
  gcd_r.append(gcd_)
  
def gcd_0(a,b):
  if a==0:
    return b
  if b==0:
    return a
  return math.gcd(a,b)
  

gcd_list = [gcd_0(gcd_l[i], gcd_r[N-1-i]) for i in range(N)]
# print(gcd_l)
# print(gcd_r)
# print(gcd_list)

print(max(gcd_list))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)

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

def calc(A, res):
    for a in A:
        if res == 0:
            res = a
        else:
            res =  gojo(max(res, a), min(res, a))
        gcds.append(res)
    return res

gcds = []
ig = -1
calc(A, 0)

for i, a in enumerate(reversed(gcds)):
    if a != gcds[-1]:
        ig = len(gcds) - i - 1
        break

item = A.pop(ig)
ans1 = calc(A, 0)
A.pop(ig)
A.insert(0, item)
ans2 = calc(A, 0)
print(max(ans1, ans2))

Submission status: Accepted

Solution code:
from fractions import *
n = int(input())
a = [0]+list(map(int, input().split()))+[0]
b = [0]*(n+2)
c = [0]*(n+2)
for i in range(1, n+1):
	b[i] = gcd(b[i-1], a[i])
for i in range(n, 0, -1):
	c[i] = gcd(c[i+1], a[i])
print(max(gcd(b[i-1], c[i+1]) for i in range(1, n+1)))
#sample answer.

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
    else:
        return gcd(a % b, b)

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

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

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

Submission status: Accepted

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

#2数の最大公約数を返す関数
#ユークリッドの互除法より
def gcd(a,b):
    if b>a:
        a,b = b,a
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)
    
#頭からとおしりから順にそこまでの最大公約数を計算する
head = lista[0]
tail = lista[n-1]
headlist,taillist = [],[]
for i in range(n):
    headlist.append(gcd(head,lista[i]))
    head = headlist[i]
    taillist.append(gcd(tail,lista[-1*(i+1)]))
    tail = taillist[i]
    
#print(headlist)
#print(taillist)

if n==2:
    print(max(lista[0],lista[1]))
else:
    mhead = taillist[-2]
    mtail = headlist[-2]
    maxval=max(mhead,mtail)
    for i in range(1,n-1):
        maxtemp = gcd(headlist[i-1],taillist[-1*i-2])
        if maxtemp>maxval:
            maxval= maxtemp
    print(maxval)

Submission status: Accepted

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

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

def L(end_i, A):
    if(end_i == 0):
        return 0
    
    a = 0
    for i in range(end_i):
        a = gcd(a, A[i])
    return a


def R(start_i, A, N):
    if(start_i == N - 1):
        return 0

    a = 0
    for i in range(start_i + 1, N):
        a = gcd(a, A[i])
    return a


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

left = [0] * N
right = [0] * N

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

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

M = []
for i in range(N):
    M.append(gcd(left[i], right[i]))
#print(M)

print(max(M))

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
n = int(input())
a = list(map(int, input().split()))
left, right = [0] * (n+1), [0] * (n+1)
for i in range(n):
    left[i+1] = gcd(left[i], a[i])
for i in reversed(range(n)):
    right[i] = gcd(right[i+1], a[i])
ans = 0
for i in range(n):
    l = left[i]
    r = right[i+1]
    ans = max(ans, gcd(l, r))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
a.sort()
x=[a[0]]
for i in range(1,n):
    x.append(gcd(x[-1],a[i]))
y=[a[-1]]
for i in range(2,n+1):
    y.append(gcd(y[-1],a[-i]))
y=y[::-1]
res=[x[-2],y[1]]
for i in range(n-2):
    res.append(gcd(x[i],y[i+2]))
print(max(res))

Submission status: Accepted

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

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

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

R.reverse()

#Res=[0]*N
res=0
for i in range(N):
  #Res.append(gcd(L[i],R[i+1]))
  res=max(res,gcd(L[i],R[i+1]))
  #Res[i]=gcd(L[i],R[i+1])
#print(max(Res))
print(res)

Submission status: Accepted

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

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

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

R.reverse()

Res=[0]*N
#res=0
for i in range(N):
  #Res.append(gcd(L[i],R[i+1]))
  #res=max(res,gcd(L[i],R[i+1]))
  Res[i]=gcd(L[i],R[i+1])
print(max(Res))

Submission status: Accepted

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

L=[]
R=[]
L.append(0)
R.append(0)

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

R.reverse()

#Res=[]
res=0
for i in range(N):
  #Res.append(gcd(L[i],R[i+1]))
  res=max(res,gcd(L[i],R[i+1]))
print(res)