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

#####segfunc######                                                              
def segfunc(x,y):
    return gcd(x,y)

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n=int(input())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
a=list(map(int,input().split()))
init(a)
ans=0
for i in range(n):
    ans=max(gcd(query(0,i),query(i+1,n)),ans)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
Asort = sorted(A)[:: -1]
L = [0] * N  # 左からi番目までのgcdをメモった配列
R = [0] * N  # 右からi番目までのgcdをメモった配列
L[0] = A[0]
R[0] = A[N - 1]
for i in range(1, N):
	L[i] = gcd(L[i - 1], A[i])
	R[i] = gcd(R[i - 1], A[N - 1 - i])
ans = max(L[N - 2], R[N - 2])
for j in range(1, N - 1):
    ans = max(ans, gcd(L[j - 1], R[N - j - 2]))
    
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


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

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

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

print (max_gcd)

Submission status: Accepted

Solution code:
def MAP(): return map(int,input().split())
def gcd(a, b):
    while b:
        a %= b
        a, b = b, a
    return a

n = int(input())
*a, = MAP()

x=[0 for _ in range(n)]
y=[0 for _ in range(n)]
for i in range(1,n):
    x[i]=gcd(x[i-1],a[i-1])
for i in range(n-1)[::-1]:
    y[i]=gcd(y[i+1],a[i+1])
Z=[gcd(x[i],y[i]) for i in range(n)]
print(max(Z))

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

n = I()
a = LI()
l,r = [0]*n,[0]*n
l[0] = a[0]
r[-1] = a[-1]
for i in range(1,n):
    l[i] = gcd(l[i-1],a[i])
for i in range(n-1)[::-1]:
    r[i] = gcd(r[i+1],a[i])
ans = 0
l = [0] + l + [0]
r = [0] + r + [0]
for i in range(1,n+1):
    ans = max(ans,gcd(l[i-1],r[i+1]))
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 = [int(i) for i in input().split()]
x = [0 for i in range(n)]
y = [0 for i in range(n)]

for i in range(1, n):
  x[i] = gcd(x[i-1], a[i-1])
for j in range(n-1)[::-1]:
  y[j] = gcd(y[j+1], a[j+1])
z = [gcd(x[i], y[i]) for i in range(n)]
print(max(z))

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

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

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
L = [0] * n
R = [0] * n
for i in range(1, n):
    L[i] = fractions.gcd(a[i - 1], L[i - 1])
    R[n - 1 - i] = fractions.gcd(a[n - i], R[n - i])
for i in range(0, n):
    ans[i] = fractions.gcd(L[i], R[i])
ans.sort()
print(ans[n - 1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(n-1):
    L.append(gcd(L[i],a[i]))
    R.append(gcd(R[i],a[-1-i]))
MAX=0
for i in range(n):
    MAX=max(MAX,gcd(L[i],R[-1-i]))
print(MAX)

Submission status: Accepted

Solution code:
from fractions import gcd


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

ls = [0 for i in range(n + 1)]
rs = [0 for i in range(n + 1)]

for i in range(1, n + 1):
    ls[i] = gcd(As[i - 1], ls[i - 1])
for i in range(n - 1, -1, -1):
    rs[i] = gcd(As[i], rs[i + 1])
# print(ls)
# print(rs)
ret = - float('inf')
for i in range(n):
    ret = max(ret, gcd(ls[i], rs[i + 1]))
print(ret)

Submission status: Accepted

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

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

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

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

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

print(max(M))

Submission status: Accepted

Solution code:
import math
import copy
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, = map(int, input().split())
data = getInputListInt()

gcdNormal = np.zeros(n)
gcdReverse = np.zeros(n)

ans = 0

for i in range(1, n):
    if i==1:
        ans = fractions.gcd(data[i-1], data[i])
        gcdNormal[i] = ans
        gcdNormal[0] = data[0]
    else:
        gcdans = fractions.gcd(ans, data[i])
        ans = min(ans, gcdans)
        gcdNormal[i] = ans

ans = 0

for i in range(n-2, -1, -1):
    if i==n-2:
        ans = fractions.gcd(data[i], data[i+1])
        gcdReverse[i] = ans
        gcdReverse[i+1] = data[i+1]
    else:
        gcdans = fractions.gcd(ans, data[i])
        ans = min(ans, gcdans)
        gcdReverse[i] = ans

ans= 0
for i in range(n):
    if i ==0:
        ans = max(ans, gcdReverse[1])
    elif i == n-1:
        ans = max(ans, gcdNormal[n-2])
    else:
        ans = max(ans, fractions.gcd(gcdNormal[i-1], gcdReverse[i+1]))

print(int(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
l = [0 for _ in range(n + 1)]
r = [0 for _ in range(n + 1)]

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

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

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

print(max(m))

Submission status: Accepted

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

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

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

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

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

print(max(A))

Submission status: Accepted

Solution code:
import fractions

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] = fractions.gcd(L_gcd[i], A[i])
    R_gcd[n-i-1] = fractions.gcd(R_gcd[n-i], A[n-i-1])

ans = [0]*n

for i in range(n):
    ans[i] = fractions.gcd(L_gcd[i], R_gcd[i+1])

print(max(ans))

Submission status: Accepted

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

if len(A) > 1:
    result = sorted(A)[1]
else:
    result = min(A)

while True:
    counter = 0
    should_continue = False
    for e in A:
        if e % result != 0:
            counter += 1
            if counter > 1:
                should_continue = True
                break
    if should_continue:
        result -= 1
        continue
    if counter <= 1:  # 1つは書き換えられる
        break
    else:
        result -= 1

print(result)

Submission status: Accepted

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


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

left = [0 for _ in range(N + 1)]
right = [0 for _ in range(N + 1)]

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
gcd_list = [0] * N

# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

#i-1番目までの最大公約数リスト
b = [0] * (N - 1)
b[0] = A[0]
for i in range(1, N - 1):
    b[i] = gcd(b[i - 1], A[i])
#i+1以降の最大公約数リスト
a = [0] * (N - 1)
a[N - 2] = A[N - 1]
for i in reversed(range(0, N - 2)):
    a[i] = gcd(a[i + 1], A[i + 1])

gcd_list[0] = a[0]
gcd_list[N-1] = b[N - 2]
for i in range(1, N - 1):
    gcd_list[i] = gcd(b[i - 1], a[i])

print(max(gcd_list))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    tmp = 1
    tmp2 = 0
    B = A[0]
    if N == 2:
        print(max(A))
    else:
        D = A[0]
        E = A[1]
        for i in range(2,N):
            D = gcd(D,A[i])
            E = gcd(E,A[i])
        for i in range(1,N):
            if B/gcd(B,A[i]) > tmp2 or gcd(A[i],tmp2) < tmp2:
                tmp = i
                tmp2 = B/gcd(B,A[i])
            B = gcd(B,A[i])
        C = A[0]
        for i in range(1,tmp):
            C = gcd(C,A[i])
        for i in range(tmp+1,N):
            C = gcd(C,A[i])
        print(max(C,D,E))
    
    
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#import math
import fractions #fractions.gcd()
sys.setrecursionlimit(1000000)

def main(): 

    N = int(input())
    A = list(map(int,input().split()))
    A_gcd_for=[]
    A_gcd_for.append(A[0])
    A_gcd_af=[]
    A_gcd_af.append(A[-1])
    for i in range(1,N):
        A_gcd_for.append(fractions.gcd(A_gcd_for[-1], A[i]))
        A_gcd_af.append(fractions.gcd(A_gcd_af[-1], A[N-i-1]))
    ans=0
    for i in range(N):
        if i==0: a = A_gcd_af[N-i-2]
        elif i==N-1: a = A_gcd_for[i-1]
        else: a = fractions.gcd(A_gcd_for[i-1], A_gcd_af[N-i-2])
        if a > ans:
            ans=a
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions

n = int(input())
a = list(map(int,input().split()))
b = a[:]

for i in range(1,n):
    a[i] = fractions.gcd(a[i],a[i-1])
    b[n-i-1] = fractions.gcd(b[n-i-1],b[n-i])
a = [0]+a #左に0を追加
b = b+[0] #右に0を追加
print(max(fractions.gcd(a[i],b[i+1]) for i in range(n)))

Submission status: Accepted

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

gl = [0] * (N-1)
gr = [0] * (N-1)

gl[0] = A[0]
gr[0] = A[-1]
for i in range(1,N-1):
    gl[i] = gcd(gl[i-1],A[i])
    gr[i] = gcd(gr[i-1],A[-i-1])
#print(gl[i])
ans = max(gr[-1],gl[N-2])
for i in range(1,N-1):
    g = gcd(gl[i-1],gr[-i-1])
    ans = max(ans,g)
#print(gl,gr)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
d = set()
a = [ int(i) for i in input().split() ]
a = sorted(a)
for i in range(2):
    for j in range(1,int(a[i]**0.5)+1):
        if a[i] % j == 0:
            d.add(j)
            d.add(a[i]//j)
ans = 0
for i in d:
    cnt = 0
    for j in a:
        if j % i != 0:
            cnt += 1

        if cnt >= 2:
            break

    if cnt < 2:
        ans = max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

gl = [0]*(N-1)
gr = [0]*(N-1)
gl[0] = A[0]
gr[0] = A[-1]
for i in range(1, N-1):
    gl[i] = gcd(gl[i-1], A[i])
    gr[i] = gcd(gr[i-1], A[-i-1])
ans = gr[-1]
for i in range(1, N-1):
    ans = max(ans, gcd(gl[i-1], gr[-i-1]))
ans = max(ans, gl[-1])
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

B = A[::-1]
g = B[0]
GCD2 = []
for b in B:
    g = gcd(g, b)
    GCD2.append(g)

ans = 1
for i in range(N):
    if i == 0:
        a = GCD2[N-2]
    elif i == N-1:
        a = GCD1[N-2]
    else:
        a = gcd(GCD1[i-1], GCD2[N-i-2])
    ans = max(ans, a)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
import fractions
gcd=a[0]
l=[]
r=[]
for i in range(n):
	gcd=fractions.gcd(gcd,a[i])
	l.append(gcd)
gcd=a[-1]
for i in range(n):
	gcd=fractions.gcd(gcd,a[-i-1])
	r.append(gcd)
x=list()
x.append((r[n-2]))
for i in range(n-2):
	x.append(fractions.gcd(l[i],r[n-i-3]))
x.append((l[n-2]))
print(max(x))

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)
    return divisors
#a, b, t = map(int, input().split())
n=int(input())
alist = list(map(int, input().split()))

ok=[]
ok2=[]

yakusu=make_divisors(alist[-1])
for yk in yakusu:
    ok2.append(yk)

yakusu=make_divisors(alist[-2])
for yk in yakusu:
    if yk in ok2:
        ok2.remove(yk)
        ok.append(yk)
    else:
        ok2.append(yk)
ok=sorted(ok)
alist=alist[:-2]

for al in alist:
    #print(ok, ok2)
    if al%ok[-1]==0:
        ok3=[]
        for o2 in ok2:
            if al%o2==0:
                ok3.append(o2)
        ok2=ok3
    else:
        ok3=[]
        for o2 in ok2:
            if al%o2==0:
                ok3.append(o2)
        ok2=ok3
        ok3=[]
        for o in ok:
            if al%o==0:
                ok3.append(o)
            else:
                ok2.append(o)
        ok=ok3
#print(ok, ok2)
if len(ok)>0:
    koho1=max(ok)
else:
    koho1=1
if len(ok2)>0:
    koho2=max(ok2)
else:
    koho2=1
print(max(koho1, koho2))

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))
#####単位元######
ide_ele = 0

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

#####segfunc######
def segfunc(x,y):
    return gcd(x, y) 

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from fractions import gcd
#from math import gcd

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

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

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

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

    return max(M)

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

Submission status: Accepted

Solution code:
import fractions 
n=int(input())
a=list(map(int,input().split()))
ans=a[0]
sna=a[n-1]
Ans=[ans]*n
Sna=[sna]*n
for j in range(1,n):
  ans=fractions.gcd(ans,a[j])
  Ans[j]=ans
  sna=fractions.gcd(sna,a[n-j-1])
  Sna[j]=sna
m=Sna[n-2]
for k in range(n-2):
  m=max(m,fractions.gcd(Ans[k],Sna[n-3-k]))
m=max(m,Ans[n-2])
print(m)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    A = sorted(A)
    full = gcd(A[0], A[1])
    removed = set([A[0], A[1]])
    for i in range(2, N):
        temp = set()
        temp.add(full)
        for v in removed:
            temp.add(gcd(v, A[i]))
        full = gcd(full, A[i])
        removed = temp

    return max(removed)

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

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

Submission status: Accepted

Solution code:
from functools import lru_cache
n = int(input())
aa = list(map(int, input().split()))

@lru_cache(maxsize=10**9)
def gcd(a, b) :
    if b == 0 : return a
    elif a%b : return gcd(b, a%b)
    else : return b

l = [0]
r = [0]
for i in range(n) :
    l.append(gcd(l[-1], aa[i]))
    r.append(gcd(r[-1], aa[-i-1]))

m = [gcd(l[i],r[-i-2]) for i in range(n)]
print(max(m))

Submission status: Accepted

Solution code:
from fractions import gcd
class SegmentTree(object):
    def __init__(self, n, func, init_val):
        self.N0 = 2**((n-1).bit_length())
        self.func = func
        self.val = init_val
        self.data = [self.val]*(2*self.N0)
    def update(self, k, x):#k番目の値をxに変更する　O(logn)
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = self.func(self.data[2*k+1], self.data[2*k+2])
    def query(self, l, r):# 区間[l, r)の最小値を求める
        L = l + self.N0; R = r + self.N0
        s = self.val
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
 
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
N = int(input())
S = SegmentTree(N, gcd, 0)
A = list(map(int, input().split()))
for i, a in enumerate(A):
    S.update(i, a)
ans = 1
for i in range(N):
    ans = max(ans, gcd(S.query(0, i), S.query(i+1, N)))
print(ans)

Submission status: Accepted

Solution code:
import fractions
n=int(input())
v=list(map(int,input().split()))
def g(a,b):
  if a==0:return b
  if b==0:return a
  return fractions.gcd(a,b)
l=[0]*(n+1)
r=[0]*(n+1)
for i in range(1,n+1):
  l[i]=g(l[i-1],v[i-1])
for i in range(n)[::-1]:
  r[i]=g(r[i+1],v[i])
x=0
for i in range(n):
  c=g(l[i],r[i+1])
  x=max(c,x)
print(x)

Submission status: Accepted

Solution code:
import functools
 
n = int(input())
lst = list(map(int, input().split()))
 
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
    
lst_forward = []
a = lst[0]
for i in lst:
    a = gcd(a, i)
    lst_forward.append(a)

lst_backward = []
a = lst[-1]
for i in lst[::-1]:
    a = gcd(a, i)
    lst_backward.append(a)
lst_backward = list(reversed(lst_backward))

s = max(lst_backward[1], lst_forward[-2])
for i in range(1, n-1):
    s = max(s, gcd(lst_forward[i-1], lst_backward[i+1]))
print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

'''
- [ABC125 - C - GCD on Blackboard(300点)](https://qiita.com/hkrutknouch/items/e71488de4a0c8e83ee97)
- [累積GCDでAtCoder ABC 125 C – GCD on Blackboardを解く](https://muroiwataru.net/entry/abc-125-python)
'''

from fractions import gcd

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

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

'''
5
64 48 16 18 12
の場合、

n = 0〜4
left:
    0 = 0
    1 = gcd(l[0], a[0]) → gcd(a[0])
    2 = gcd(l[1], a[1]) → gcd(a[0] + a[1])
    3 = gcd(l[2], a[2]) → gcd(a[0] + a[1] + a[2])
    4 = gcd(l[3], a[3]) → gcd(a[0] + a[1] + a[2] + a[3])
    5 = gcd(l[4], a[4]) → gcd(a[0] + a[1] + a[2] + a[3] + a[4])

right:
    5 = 0
    4 = gcd(r[5], a[4]) → gcd(a[4])
    3 = gcd(r[4], a[3]) → gcd(a[4] + a[3])
    2 = gcd(r[3], a[2]) → gcd(a[4] + a[3] + a[2])
    1 = gcd(r[2], a[1]) → gcd(a[4] + a[3] + a[2] + a[1])
    0 = gcd(r[1], a[0]) → gcd(a[4] + a[3] + a[2] + a[1] + a[0])
'''

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

    '''
    n = 0〜4
    gcd(l[0], r[1])  a[0] と a[4]〜a[1] のgcd :        a除外なし(全部同一の値のケース)
    gcd(l[1], r[2])  a[0] と a[4]〜a[2] のgcd :        a[1]を除外
    gcd(l[2], r[3])  a[0]〜a[1] と a[4]〜a[3] のgcd :  a[2]を除外
    gcd(l[3], r[4])  a[0]〜a[2] と a[4] のgcd :        a[3]を除外
    gcd(l[4], r[5])  a[0]〜a[3] と 0 の gcd :          a[4]を除外
    '''

print(ans)

Submission status: Accepted

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

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

L = [0] * (n+2)
R = [0] * (n+2)
for i in range(n+1):
    L[i+1] = gcd(L[i],a[i])

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

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

Submission status: Accepted

Solution code:
try:
    from math import gcd
except:
    from fractions import gcd
import operator
from collections import deque


class Segtree:
    """
    st = Segtree(4, f=operator.add, e=0)
    st[1:] = [4, 9, 16]
    st[0] = -99
    assert st[-1] == 16
    assert st[:] == [-99, 4, 9, 16]
    assert st.grasp(1, 3) == 13
    """

    def __init__(self, n, f=operator.add, e=0):
        """all(f(v, e) == f(e, v) == v for v in data)"""
        self.r = range(n)
        self.size = 2 ** ((n - 1).bit_length())
        self.tree = [e] * (2 * self.size)
        self.f = f
        self.iden = e

    def __len__(self):
        return len(self.r)

    def __list__(self):
        return self.tree[self.size-1:self.size-1+len(self.r)]

    def __repr__(self):
        return repr(list(self))

    def grasp(self, i=0, j=None):
        """reduce(f, data[i:j], e)"""
        if j is None:
            j = len(self)
        i = self.size - 1 + max(i, 0)
        j = self.size - 1 + min(j, len(self))
        ans = self.iden
        while j - i > 0:
            if i & 1 is 0:
                ans = self.f(self.tree[i], ans)
            if j & 1 is 0:
                ans = self.f(ans, self.tree[j-1])
            i = i >> 1
            j = (j - 1) >> 1
        return ans

    def __getitem__(self, i):
        r = self.r[i]
        if isinstance(r, int):
            return self.tree[self.size - 1 + r]
        else:
            return [self.tree[self.size - 1 + ri] for ri in r]

    def __setitem__(self, i, v):
        """Extra elements will be ignored when i is a slice."""
        r = self.r[i]
        if isinstance(r, int):
            r = [r]
            v = [v]
        q = deque()
        s = set()

        def addnext(j):
            k = (j - 1) // 2
            if k >= 0 and k not in s:
                q.append(k)
                s.add(k)

        for ri, vi in zip(r, v):
            j = self.size - 1 + ri
            self.tree[j] = vi
            addnext(j)
        while len(q):
            j = q.popleft()
            # s.remove(j)
            vl = self.tree[2 * j + 1]
            vr = self.tree[2 * j + 2]
            self.tree[j] = self.f(vl, vr)
            addnext(j)


N = int(input())
A = [int(s) for s in input().split()]
st = Segtree(N, f=gcd, e=0)
st[:] = A
ans = max([gcd(st.grasp(0, i), st.grasp(i+1)) for i in range(N)])
print(ans)

Submission status: Accepted

Solution code:
def solve(n, a_list):
    # 1-origin
    left_dp = [0, a_list[0]]
    right_dp = [0, a_list[-1]]

    # time O(N log(A))
    for key in range(1, n):
        left_value = a_list[key]
        left_dp.append(gcd(left_dp[-1], left_value))

        right_value = a_list[-key-1]
        right_dp.append(gcd(right_dp[-1], right_value))

    ans = 0
    for key in range(1, n + 1):
        ans = max(ans, gcd(left_dp[key-1], right_dp[-key-1]))
    return ans


# time O(log(A))
def gcd(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a

    while a % b:
        a, b = b, a % b
    return b


def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    ans = solve(n, a_list)
    print(ans)


main()

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import fractions
from functools import reduce

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

N = I()
A = III()

l = [0]*N
r = [0]*N

l[0] = A[0]
r[N-1] = A[N-1]

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

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

ans = 0
for i in range(1,N-1):
    temp = fractions.gcd(l[i-1],r[i+1])
    if temp > ans:
        ans = temp

temp1 = gcd_list(A[1:])
temp2 = gcd_list(A[:N-1])

print(max(ans,temp1,temp2))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def euclid(a, b):
    if a < b:
        a, b = b, a
    while True:
        r = a % b
        if r == 0:
            return b
        a, b = b, r


n = int(input())
a = [int(x) for x in input().split()]
l_gcd, r_gcd = [a[0]], [a[n-1]]
for i in range(1, n-1):
    l_gcd.append(euclid(l_gcd[i-1], a[i]))
    r_gcd.append(euclid(r_gcd[i-1], a[n-1-i]))

ans = max(l_gcd[n-2], r_gcd[n-2])
for i in range(1, n-1):
    ans = max(ans, euclid(l_gcd[i-1], r_gcd[n-i-2]))
print(ans)

Submission status: Accepted

Solution code:
def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p

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

if n == 2:
    print(max(a))
else:
    x, y, z = a[0], a[1], a[2]
    p, q, r = gcd(x, y), gcd(y, z), gcd(z, x)
    gcd_max = max(p, q, r)
    if gcd_max == p:
        without = z
    elif gcd_max == q:
        without = x
    else:
        without = y

    k = gcd(gcd_max, without)   
    for i in range(3, n):
        a_i = a[i]
        if a_i % gcd_max != 0:
            l = gcd(gcd_max, a_i)
            if l >= k:
                gcd_max = l
            else:
                gcd_max = k
                without = a_i
        k = gcd(k, a_i)
    print(gcd_max)