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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

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

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

Submission status: Accepted

Solution code:
import math

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

left = [0] * (N+1)
for i in range(1, N+1):
    left[i] = math.gcd(left[i-1], A[i-1])
    
right = [0] * (N+1)
right[N-1] = A[N-1]
for i in range(N-2, -1, -1):
    right[i] = math.gcd(right[i+1], A[i])
    
output = 0
for i in range(N):
    output = max(output, math.gcd(left[i], right[i+1]))
    
print(output)

Submission status: Accepted

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")


class SegmentTree:
    def __init__(self, size, f=lambda x, y: x + y, default=0):
        self.size = 2 ** (size - 1).bit_length()
        self.default = default
        self.dat = [default] * (self.size * 2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

    def query(self, l, r):
        """return f([l,r))
        """
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


N = int(input())
A = list(map(int, input().split()))
s = SegmentTree(N, gcd, 0)
for i, a in enu(A):
    s.update(i, a)

res = 0
for i in range(N):
    val = gcd(s.query(0, i), s.query(i + 1, N))
    if res < val:
        res = val
print(res)

Submission status: Accepted

Solution code:
import math
N = int(input())
arr = list(map(int, input().split()))
gcd_right = [arr[0]]
for i in range(1,N-1):
    gcd_right.append(math.gcd(gcd_right[i-1],arr[i]))
arr = arr[::-1]
gcd_left = [arr[0]]
for i in range(1,N-1):
    gcd_left.append(math.gcd(gcd_left[i-1],arr[i]))
gcd_left = gcd_left[::-1]
ans = max(gcd_right[-1],gcd_left[0])
for i in range(N-2):
    ans = max(ans,math.gcd(gcd_left[i+1],gcd_right[i]))
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()

    # [0, i)の累積GCD
    gcd_cum_l = [0] * (N + 1)
    for i in range(N):
        gcd_cum_l[i+1] = math.gcd(A[i], gcd_cum_l[i])
    # [i, N)の累積GCD
    gcd_cum_r = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        gcd_cum_r[i] = math.gcd(A[i], gcd_cum_r[i+1])
    # print(gcd_cum_l)
    # print(gcd_cum_r)

    ans = 0
    for i in range(N):
        ans = max(math.gcd(gcd_cum_l[i], gcd_cum_r[i+1]), ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

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

fromleft = list(accumulate(a, math.gcd))
fromright = list(accumulate(a[::-1], math.gcd))[::-1]

gcd = []

gcd.append(fromright[1])
for i in range(1, n-1):
    gcd.append(math.gcd(fromleft[i-1], fromright[i+1]))
gcd.append(fromleft[n-2])

print(max(gcd))

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

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

fromleft = list(accumulate(a, math.gcd))
fromright = list(accumulate(a[::-1], math.gcd))[::-1]

gcd = []

gcd.append(fromright[1])
for i in range(1, n-1):
    gcd.append(math.gcd(fromleft[i-1], fromright[i+1]))
gcd.append(fromleft[n-2])

print(max(gcd))

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

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

fromleft = list(accumulate(a, math.gcd))
a.reverse()
fromright = list(accumulate(a, math.gcd))
fromright.reverse()
a.reverse()

gcd = []

gcd.append(fromright[1])
for i in range(1, n-1):
    gcd.append(math.gcd(fromleft[i-1], fromright[i+1]))

gcd.append(fromleft[n-2])

if n == 2:
    print(max(a[1], a[0]))
else:
    print(max(gcd))

Submission status: Accepted

Solution code:
import math

n = int(input())
a = list(map(int,input().split()))
L = [0]*(n+1)
R = [0]*(n+1)
for i in range(n):
    L[i+1] = math.gcd(L[i], a[i])
    R[-2-i] = math.gcd(R[-1-i], a[-1-i])
    
ans = 0
for i in range(n):
    G = math.gcd(L[i], R[i+1])
    ans = max(ans, G)
print(ans)

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

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

fromright = list(accumulate(a, math.gcd))
a.reverse()
fromleft = list(accumulate(a, math.gcd))
fromleft.reverse()

gcd = []

gcd.append(fromleft[1])

for i in range(1, n-1):
  gcd.append(math.gcd(fromright[i-1], fromleft[i+1]))

gcd.append(fromright[n-2])

if n == 2:
  print(max(a))
else:
  print(max(gcd))

Submission status: Accepted

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

import sys
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


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

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


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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

# reffer to: https://qiita.com/dn6049949/items/afa12d5d079f518de368
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.data = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 0:
            i >>= 1
            self.data[i] = self.f(self.data[i*2], self.data[i*2+1])

    # [l, r)
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.data[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


def main():
    N = I()
    A = LI()

    tree = SegmentTree(N, f=math.gcd)
    for i in range(N):
        tree.update(i, A[i])

    ans = 0
    for i in range(N):
        ans = max(ans, math.gcd(tree.query(0, i), tree.query(i + 1, N)))
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N = I()
    A = LI()

    forward = list(itertools.accumulate(A, math.gcd))
    backward = list(itertools.accumulate(A[::-1], math.gcd))[::-1]

    ans = max(backward[1], forward[-2])

    for i in range(1, N - 1):
        ans = max(ans, math.gcd(forward[i - 1], backward[i + 1]))
    print(ans)


if __name__ == '__main__':
    main()

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)
def lcm(a,b):
    return a*b//gcd(a,b)

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

ans=0
for i in range(n):
    if i==0:
        ans=max(ans, r[1]);continue
    if i==n-1:
        ans=max(ans, l[-2]);continue
    ans=max(ans, gcd(l[i-1], r[i+1]))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd


class SegTree:
    X_unit = 0
    X_f = gcd

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    seg = SegTree(N)
    seg.build(A)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.fold(0, i), seg.fold(i+1, N)))
    print(ans)


if __name__ == '__main__':
    main()

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().strip().split()))

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

res = 0
for i in range(n):
    if res < gcd(L[i], R[n - i - 1]):
        res = gcd(L[i], R[n - i - 1])

print(res)

Submission status: Accepted

Solution code:
import math

def segfunc(x,y):
  return math.gcd(x,y)

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


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

Tree = SegmentTree(A, segfunc, 0)
ans = 0
for i in range(N):
  Tree.update(i,0)
  ans = max(ans,Tree.sum(0,N))
  Tree.update(i,A[i])
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
alst = list(map(int, input().split()))
l_gcd = [alst[0]]
for num in alst[1:-1]:
    l_gcd.append(gcd(l_gcd[-1], num))

r_gcd = [alst[-1]]
for num in alst[1:-1][::-1]:
    r_gcd.append(gcd(r_gcd[-1], num))
r_gcd = r_gcd[::-1]
ans = max(r_gcd[0], l_gcd[-1])


for num1, num2 in zip(r_gcd[1:], l_gcd[:-1]):
    tmp = gcd(num1, num2)
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
def gcd(m, n):
    if n == 0:
        n, m = m, n
    r = m % n
    return gcd(n, r) if r else n

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

Submission status: Accepted

Solution code:

from math import gcd

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

left = [0] * (N + 2)
right = [0] * (N + 2)

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

for i in reversed(range(N)):
    right[i + 1] = gcd(right[i + 2], X[i])

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

print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
a=list(map(int, input().split()))
alist=[]
gcd1=a[0]
for i in range(0,n):
  gcd1=math.gcd(gcd1,a[i])
  alist.append(gcd1)
blist=[]
gcd2=a[n-1]
for i in range(n-1,-1,-1):
  gcd2=math.gcd(gcd2,a[i])
  blist.append(gcd2)
clist=[alist[n-2],blist[n-2]]
for i in range(n-2):
  clist.append(math.gcd(alist[i],blist[n-i-3]))
print(max(clist))

Submission status: Accepted

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

import math

del_0=a[0]

if n==2:
    print(max(a))
    exit()
#print(a)
for i in range(n):
    #print(">>>>>>>>>",i+1)
    if i==2:
        del_1=max([math.gcd(a[0],a[1]),math.gcd(a[2],a[1]),math.gcd(a[2],a[0])])
        #print(([math.gcd(a[0],a[1]),math.gcd(a[2],a[1]),math.gcd(a[2],a[0])]))
    elif i>2:
        del_1=max(del_0,math.gcd(del_1,a[i]))
        #print(del_1)

    del_0=math.gcd(del_0,a[i])
    #print(del_0)
print(del_1)

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
 
def gcd_list(numbers):
    return reduce(gcd, numbers)

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


X = [0]*N
Y = [0]*N
X[0] = A[0]
Y[-1] = A[-1]
ans = [0]*N
for i in range(1,N):
  X[i] = gcd(X[i-1],A[i])
  Y[N-i-1] = gcd(Y[N-i],A[N-i-1])
for i in range(1,N-1):
  ans[i] = gcd(X[i-1],Y[i+1])
ans[0],ans[-1] = gcd_list(A[1:]),gcd_list(A[:-1])
print(max(ans))

Submission status: Accepted

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(n)]
r=[0 for i in range(n)]
l[0]=a[0]
r[0]=a[-1]
for i in range(n-1):
    l[i+1]=gcd(l[i],a[i+1])
for i in range(n-1):
    r[i+1]=gcd(r[i],a[-2-i])

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

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

print(max(ans))

Submission status: Accepted

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


adiv = sorted(set(make_divisors(a[0]) + make_divisors(a[1])),reverse=True)


def is_ok(arg):
    #print(f"index{arg}でーす{adiv[arg]}")
    cnt = 0
    for i in range(n):
        if a[i]%adiv[arg] != 0:
            cnt += 1
            #print(str(a[i])+"×")

        if cnt>=2:
            #print("だめ"+str(a[i])+" iは"+str(i))
            return False
            break    
    else:
        #print("ok-")
        return True

import sys
for i in range(len(adiv)):
    if is_ok(i):
        print(adiv[i])
        sys.exit()

Submission status: Accepted

Solution code:
import math
N = int(input())
List = list(map(int,input().split()))
L=[0]*N
R=[0]*N
for i in range(1,N):
  L[i] = math.gcd(L[i-1],List[i-1])
  R[-i-1] = math.gcd(R[-i],List[-i])
ans = 0
for i in range(N):
  ans = max(ans,math.gcd(L[i],R[i]))
print(ans)

Submission status: Accepted

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    """
    N = read_int()
    A = read_ints()
    prefix = [-1]*N
    # prefix[i] is gcd of numbers 0..i-2
    suffix = [-1]*N
    for i in range(N-1):
        if i == 0:
            prefix[i+1] = A[i]
        else:
            prefix[i+1] = math.gcd(prefix[i], A[i])
    for i in range(N-1, 0, -1):
        if i == N-1:
            suffix[i-1] = A[i]
        else:
            suffix[i-1] = math.gcd(suffix[i], A[i])

    max_gcd = -1
    for i in range(N):
        gcd = -1
        if prefix[i] != -1 and suffix[i] != -1:
            gcd = math.gcd(prefix[i], suffix[i])
        elif prefix[i] == -1:
            gcd = suffix[i]
        else:
            gcd = prefix[i]
        max_gcd = max(max_gcd, gcd)
    return max_gcd


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))
def fde(): print("-flag-")

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

    return res


def main():
    N=ii()
    A=list(mi())
    R = divisors(A[0]) + divisors(A[1])

    ans = 0
    for r in R:
        miss_count = 0
        for a in A:
            if a % r != 0:
                miss_count += 1
                if miss_count == 2:
                    break
        
        if miss_count <= 1:
            ans = max(ans,r)
            

    print(ans)








if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
r=[0]*n
l[0]=a[0]
r[-1]=a[-1]
for i in range(n-1):
  l[i+1]=math.gcd(l[i],a[i+1])
for i in reversed(range(n-1)):
  r[i] = math.gcd(r[i+1],a[i])

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a*b//gcd(a,b))
#####segfunc######
def segfunc(x,y):
    return gcd(x,y)

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(len(init_val)):
        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): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    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

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)
init(lst1)
ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans,query(1,n))
    elif i == n-1:
        ans = max(ans,query(0,n-1))
    else:
        ans = max(ans,gcd(query(0,i),query(i+1,n)))

print(ans)

Submission status: Accepted

Solution code:
from math import gcd
#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
n = int(input())
A = list(map(int, input().split()))
ans = 0

x = [0]*n
y = [0]*n
for i in range(1, n):
    x[i] = gcd(x[i-1], A[i-1])
for i in reversed(range(n-1)):
    y[i] = gcd(y[i+1], A[i+1])

for i in range(n):
    tmp = gcd(x[i], y[i])
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
from math import gcd

input = sys.stdin.readline


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

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

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

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

    ans = 1
    for i in range(N):
        if i == 0:
            ans = max(ans, R_GCD[1])
        elif i == N - 1:
            ans = max(ans, L_GCD[-2])
        else:
            res = gcd(L_GCD[i - 1], R_GCD[i + 1])
            ans = max(ans, res)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import gcd

def f(A):
    ret = [0]
    for a in A:
        ret.append(gcd(ret[-1], a))
    return ret

def solve(N: int, A: "List[int]"):    
    return  max(gcd(g0, g1) for g0, g1 in zip(f(A), f(A[::-1])[-2::-1]))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import gcd
from functools import reduce

def f(A):
    ret = [A[0]]
    for a in A:
        ret.append(gcd(ret[-1], a))
    ret[0] = reduce(gcd, A[1:])
    return ret

def solve(N: int, A: "List[int]"):    
    return  max(gcd(g0, g1) for g0, g1 in zip(f(A), f(A[::-1])[-2::-1]))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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


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

al = [0] * (n + 2)
ar = [0] * (n + 2)

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

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

ans = 0

for i in range(n):
    num = gcd(al[i], ar[i + 2])
    ans = max(ans, num)

print(ans)

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x==0 or y==0:
        return max(x,y)
    if x<y:
        x,y=y,x
    if x%y==0:
        return y
    return gcd(y,x%y)
n=int(input())
a=list(map(int,input().split()))
L=[a[0]]*n
R=[a[-1]]*n
for i in range(n-1):
    L[i+1]=gcd(L[i],a[i+1])
    R[-i-2]=gcd(R[-i-1],a[-i-2])
ans=1
L=[0]+L
R=R+[0]
for i in range(n):
    ans=max(ans,gcd(L[i],R[i+1]))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

Submission status: Accepted

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


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


ans = 1
if N == 2:
    print(max(a))
    exit()

l = [1] * N
l[0] = a[0]
r = [1] * N
r[N-1] = a[N-1]
for i in range(1, N):
    l[i] = gcd(l[i-1], a[i])
    r[N-1-i] = gcd(r[N-i], a[N-1-i])
    
for i in range(N):
    if i == 0:
        n = r[1]
    elif i == N-1:
        n = l[N-2]
    else:
        n = gcd(l[i-1], r[i+1])
    ans = max(ans, n)
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

# L = [0, A_1のgcd, A_1~A_2のgcd, A_1~A_3のgcd, ..., A_1~A_Nのgcd]、len = N+1
L = [0]
for i in range(N):
    L.append(gcd(L[-1], A[i]))


# R = [A_1~A_Nのgcd, A_2~A_Nのgcd, ..., A_N-1~A_Nのgcd, A_Nのgcd, 0], len = N+1
R = [0]
for i in range(N):
    R.append(gcd(R[-1], A[-i - 1]))
R = R[::-1]

ans_list = []
# A_1を消す場合, A_2を消す場合, ..., A_Nを消す場合
for i in range(N):
    ans_list.append(gcd(L[i], R[i + 1]))

print(max(ans_list))

Submission status: Accepted

Solution code:
# 約数列挙(nを含む)
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 solver(N, A):

    # 答えはA[0]かA[1]の約数
    p0 = make_divisors(A[0])
    p1 = make_divisors(A[1])
    P = list(set(p0 + p1))

    # 約数を大きい方から見る
    for p in sorted(P)[::-1]:
        c = 0
        for a in A:
            if a % p == 0:
                c += 1

        if c == N - 1 or c == N:
            return p


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

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

Submission status: Accepted

Solution code:
import numpy as np

# 約数列挙(nを含む)
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n // i)

    return divisors


N = int(input())
A = np.array(input().split(), dtype=np.int64)
A.sort()
A = A[::-1]


p0 = make_divisors(A[0])
p1 = make_divisors(A[-1])
P = p0 | p1

for p in sorted(P)[::-1]:
    c = np.count_nonzero(A % p == 0)
    if c == N - 1:
        break

q = np.gcd.reduce(A)
if p > q:
    print(p)
else:
    print(q)

Submission status: Accepted

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