Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

3
7 6 8

Sample Output 1

2

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

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Accepted

Solution code:
import fractions

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

left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i+1] = fractions.gcd(left[i], a[i])
    right[n-i-1] = fractions.gcd(right[n-i], a[n-1-i]) 

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

Submission status: Accepted

Solution code:
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

N = int(input())
A = list(map(int, input().split()))
left = [0]*N
right = [0]*N

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

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

# print(left, right)
max_val = max(left[-2], right[1])
for i in range(1, N-1):
    max_val = max(max_val, gcd(left[i-1], right[i+1]))

print(max_val)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ah1 = [1 for _ in A]
    ss1.extend(ss2)


    #print(A)
    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i

    #print(ak1)
    #print(ah1)
    #print(ak2)
    #print(ah2)
    print(ak1*max(ah1))



#####################################################ライブラリ集ここから

def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ah1 = [1 for _ in A]
    ah2 = [1 for _ in A]


    #print(A)
    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i

    ak2 = 1
    for i in ss2:
        out = 0
        ahk = None
        for j, a in enumerate(A2):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    ahk = j
            else:
                A2[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah2[ahk] *= i
        else:
            ak2 *= i

    #print(ak1)
    #print(ah1)
    #print(ak2)
    #print(ah2)
    print(max(ak1*max(ah1), ak2*max(ah2)))



#####################################################ライブラリ集ここから

def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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):
        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

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

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i, a[i])

ans = 1
for i in range(n):
    left = s.query(0, i)
    right = s.query(i+1, n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

Submission status: Accepted

Solution code:
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):
        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

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

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i,a[i])

ans = 1
for i in range(n):
    left = s.query(0,i)
    right = s.query(i+1,n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

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


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

# L[i] : A[0] 〜 A[i-1] までのgcd
# R[i] : A[N-1-i+1] 〜 A[N-1] までのgcd 
L = [0]*N
R = [0]*N

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

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

print(ans)

Submission status: Accepted

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

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

#print(cd_dic)
cds = common_divisor(A[0]).union(common_divisor(A[1]))
ans = 1
for k in cds:
    #print(cd_dic)
    cnt = 0
    for a in A:
        if a%k!=0:
            cnt += 1
            if cnt == 2:
                break
    else:
        ans = max(ans,k)

print(ans)

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import heapq

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

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

def main():
    if len(A) <= 2:
        print(max(A))
        exit()
    else:
        a0, a1 = heapq.nsmallest(2, A)
        all_divisors = list(set(make_divisors(a0) + make_divisors(a1)))

    ans = 1
    for divisor in all_divisors:
        cnt = 0
        for a in A:
            if a % divisor != 0:
                cnt += 1
            if cnt == 2:
                break
        if cnt < 2:
            ans = max(ans, divisor)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A = sorted(A)

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 main():
    if len(A) <= 2:
        print(max(A))
        exit()
    else:
        all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1])))

    ans = 1
    for divisor in all_divisors:
        cnt = 0
        for a in A:
            if a % divisor != 0:
                cnt += 1
            if cnt == 2:
                break
        if cnt < 2:
            ans = max(ans, divisor)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if len(A) <= 2:
    print(max(A))
    exit()
else:
    all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1])))

ans = 1
for divisor in all_divisors:
    cnt = 0
    for a in A:
        if a % divisor != 0:
            cnt += 1
        if cnt == 2:
            break
    if cnt < 2:
        ans = max(ans, divisor)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n = int(readline())
  a = [ int(i) for i in readline().split()]
  gcd_l = [0]*n
  gcd_r = [0]*n
  
  for i in range(1,n):
    gcd_l[i] = gcd(a[i-1],gcd_l[i-1])
    gcd_r[n-1-i] = gcd(a[n-i],gcd_r[n-i])
  
  ans = 0
  
  for a, b in zip(gcd_l, gcd_r):
    x = gcd(a,b)
    if ans < x:
      ans = x
   
  print(ans)
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#####segfunc######
def segfunc(a,b):
    while b:
        a, b = b, a % b
    return a

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:
        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())
a = list(map(int,input().split()))
#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, segfunc(query(0,i), query(i+1, n)))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

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

gcd_left = []
tmp = A[0]
for i in range(N):
    tmp = gcd(tmp, A[i])
    gcd_left.append(tmp)

gcd_right = []
tmp = A[-1]
for i in range(N-1, -1, -1):
    tmp = gcd(tmp, A[i])
    gcd_right.append(tmp)
ans = 0
for i in range(len(A)):
    if i == 0:
        ans = max(ans, gcd_right[-2])
    elif i == len(A) - 1:
        ans = max(ans, gcd_left[-2])
    else:
        ans = max(ans, gcd(gcd_left[i-1], gcd_right[N-i-2]))

print(ans)

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = tuple([0] + a + [0])
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = []
    for i, j in zip(l, r):
        ans.append(gcd(i, j))

    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = tuple([0] + a + [0])
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = 0
    for i, j in zip(l, r):
        g = gcd(i, j)
        ans = max(ans, g)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = [0] + a + [0]
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = 0
    for i, j in zip(l, r):
        g = gcd(i, j)
        ans = max(ans, g)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
def gcd(a, b):
	if a < b:
		a, b = b, a
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
a = np.array([int(x) for x in input().split()])
np.sort(a)
l = np.zeros(n + 1)
r = np.zeros(n + 1)
m = np.zeros(n)
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])
for i in range(n):
	m[i] = gcd(l[i], r[i + 1])
print(int(np.max(m)))

Submission status: Accepted

Solution code:
from fractions import gcd
ide = 0
def func(a,b):
  return gcd(a,b)
class SegmentTree:
  def __init__(self,ls):
    n = len(ls)
    self.tree = [ide for i in range(n)]+ls
    for i in range(1,n)[::-1]:
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
  def get(self,l,r):
    ret = ide
    l += n
    r += n
    while l < r:
      if l&1:
        ret = func(ret,self.tree[l])
        l += 1
      if r&1:
        ret = func(ret,self.tree[r-1])
      l >>= 1
      r >>= 1
    return ret
  def update(self,i,x):
    i += n
    self.tree[i] = x
    while i > 1:
      i >>= 1
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
sol = SegmentTree(a)
ans = 0
for i in range(n):
  t = a[i]
  sol.update(i,0)
  ans = max(ans,sol.get(0,n))
  sol.update(i,t)
print(ans)

Submission status: Accepted

Solution code:
import fractions

def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    G = [A[0]]
    prev = A[0]
    for i in range(1, n):
        prev = fractions.gcd(prev, A[i])
        G.append(prev)

    ANS = [G[n - 2]]
    prev = A[n - 1]
    for i in range(n - 2, 0, -1):
        ANS.append(fractions.gcd(G[i - 1], prev))
        prev = fractions.gcd(A[i], prev)

    ANS.append(prev)

    print(max(ANS))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions

n=int(input())
A=list(sorted(map(int,input().split())))
L=[A[0]]
R=[A[n-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=1
for i in range(n):
    if i==0:
        ans=max(R[n-2],ans)
    elif i==n-1:
        ans=max(L[n-2],ans)
    else:
        l=L[i-1]
        r=R[n-i-2]
        ans=max(fractions.gcd(l,r),ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in range(self.sz-1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

Solution code:
# test

import sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()