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:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


class Ruiseki_lr():
    """左右からの畳み込みをそれぞれ計算する"""
    def __init__(self, array, op, e):
        self.op = op
        self.e = e

        n = len(array)
        self.left = [e] * (n + 1)
        self.right = [e] * (n + 1)
        for i in range(n):
            self.left[i + 1] = self.op(self.left[i], array[i])
        for i in reversed(range(n)):
            self.right[i] = self.op(self.right[i + 1], array[i])

    def left(self, p):
        """区間[0, p)の畳み込み結果を返す"""
        return self.left[p]
    
    def right(self, p):
        """区間[p, n)の畳み込みを返す"""
        return self.right[p]

    def fold(self, p):
        """p番目を除いた区間[0, n)の畳み込み結果を返す"""
        return self.op(self.left[p], self.right[p + 1])


n = int(input())
a = list(map(int, input().split()))
ru = Ruiseki_lr(a, gcd, 0)

ans = 0
for i in range(n):
    ans = max(ru.fold(i), ans)
print(ans)

Submission status: Accepted

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

L = {}
R = {}

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

R[n-1] = A[n-1]
#print("R", n-1, R[n-1])
for i in range(n-1):
  R[n-2-i] = gcd(R[n-1-i], A[n-2-i])
  #print("R", n-2-i, R[n-2-i])
  
max_gcd = 0
for i in range(1, n-1):
  max_gcd = max(gcd(L[i-1], R[i+1]), max_gcd)
  #print(i, L[i-1], R[i+1], gcd(L[i-1], R[i+1]))
max_gcd = max((max_gcd, L[n-2], R[1]))
print(max_gcd)

Submission status: Accepted

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)

def ruiseki_lr(array):
    """左右からの畳み込みをそれぞれ計算する
    left[p]  := 区間[0, p)の畳み込み
    right[p] := 区間[p, n)の畳み込み
    """
    op = lambda a, b: gcd(a, b)
    e = 0

    n = len(array)
    left = [e] * (n + 1)
    right = [e] * (n + 1)

    for i in range(n):
        left[i + 1] = op(left[i], array[i])
    for i in reversed(range(n)):
        right[i] = op(right[i + 1], array[i])

    return left, right



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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# from itertools import combinations


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


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

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

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

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

    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


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

def gcd_all(lst):
    g = gcd(lst[0], lst[1])
    for e in lst[2:]:
        g = gcd(g, e)
    return g


def submit():
    n = int(input())
    alist = list(map(int, input().split()))

    if n == 2:
        print(max(alist))
    else:
        # 左から計算したgcd列
        gcd_left = [alist[0]]
        for a in alist[1:]:
            gcd_left.append(gcd(gcd_left[-1], a))
        
        # 右から計算したgcd列
        gcd_right = [alist[-1]]
        for a in reversed(alist[:-1]):
            gcd_right.append(gcd(gcd_right[-1], a))
        gcd_right = gcd_right[::-1]

        gcd_max = 0
        for i in range(n):
            if i == 0:
                gcd_i = gcd_right[i + 1]
            elif i == n - 1:
                gcd_i = gcd_left[i - 1]
            else:
                gcd_i = gcd(gcd_left[i - 1], gcd_right[i + 1])

            if gcd_max < gcd_i:
                gcd_max = gcd_i

        print(gcd_max)


if __name__ == "__main__":
    submit()

Submission status: Accepted

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

import fractions
rgcd = [0]
lgcd = [0]
for i in range(N) :
    rgcd.append(fractions.gcd(rgcd[i], A[i]))
for i in range(N) :
    lgcd.append(fractions.gcd(lgcd[i], A[-1-i]))

lgcd.reverse()
ans = []
for i in range(N) :
    ans.append(fractions.gcd(rgcd[i], lgcd[i+1]))

print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

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

gcdl = [1]*N
gcdl[0] = A[0]

gcdr = [1]*N
gcdr[-1] = A[-1]

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

res = max(gcdl[N-2], gcdr[1])

for i in range(1, N-1):
    res = max(gcd(gcdl[i-1], gcdr[i+1]), res)

print(res)

Submission status: Accepted

Solution code:
from fractions import gcd

class SegTree:
    def __init__(self, N, A, f, e):
        """
        N: A の要素数
        A: セグ木に乗せたい配列
        f: 二項演算 (モノイドじゃなきゃだめ)
        e: f の単位元
        """
        n = 2**(N-1).bit_length() # セグ木の葉の数（N 以上の最小の2べき）
        c = [e] * (2*n)

        for i in range(N):
            c[i+n] = A[i] # 葉をA[i]の値にする
        
        for i in range(n-1, 0, -1):
            c[i] = f(c[i<<1|0], c[i<<1|1]) # 子を使ってボトムアップに値を更新していく
        
        self.n = n # セグ木の葉の数（N 以上の最小の2べき）
        self.c = c # セグ木の配列
        self.e = e
        self.f = f
    
    def update(self, k, x):
        k += self.n
        self.c[k] = x # 対応する葉に移動

        # 祖先をたどって更新していく
        while k > 1:
            k >>= 1
            self.c[k] = self.f(self.c[k<<1|0], self.c[k<<1|1])

    def query(self, l, r):
        res = self.e
        l += self.n; r += self.n # 対応する葉に移動

        while l < r: # 範囲がかぶらない間
            if l & 1: # 左端が右側にいるなら
                res = self.f(res, self.c[l]) # その値と res の積をとって
                l += 1 # 右に 1 動く

            if r & 1: # 右端が左側にいるなら
                r -= 1 # 左に 1 動いて (右端は閉なので)
                res = self.f(res, self.c[r]) # その値と res の積をとる

            l >>= 1; r >>= 1 # 親に移動
        
        return res

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

seg = SegTree(N, A, gcd, 0)

res = 0
for i in range(N):
    res = max(res, gcd(seg.query(0, i), seg.query(i+1, N)))

print(res)

Submission status: Accepted

Solution code:
from fractions import gcd


class SegmentTree:
    def __init__(self, n, init_value, ide_ele):
        self.num = 2 ** (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.seg[i + self.num - 1] = init_value[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    
    def query(self, _p, _q):
        p = _p
        q = _q
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while 1 < q - p:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res
    
    @staticmethod
    def segfunc(a, b):
        return gcd(a, b)


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    seg_tree = SegmentTree(N, A, 0)
    ans = -1
    for i in range(N):
        ans = max(ans, gcd(seg_tree.query(0, i), seg_tree.query(i + 1, N)))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
A = list(map(int, input().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])

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

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

Submission status: Accepted

Solution code:
# operator.add(a, b)
# operator.mul(a, b)


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)
    

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
def AOJ_DSL_2_A():
    n, q = map(int, input().split())
    e = (1 << 31) - 1
    A = [e] * n
    seg = SegmentTree(A, min, e)

    for i in range(q):
        t, x, y = map(int, input().split())
        if t == 0:
            seg.update(x, y)
        else:
            print(seg.get(x, y + 1))


# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
def AOJ_DSL_2_B():
    from operator import add
    import sys
    n, q = map(int, input().split())
    e = 0
    A = [e] * n
    seg = SegmentTree(A, add, e)
    
    query = sys.stdin.readlines()
    for i in range(q):
        t, x, y = map(int, query[i].split())
        x -= 1
        if t == 0:
            A[x] += y
            seg.update(x, A[x])
        else:
            y -= 1
            print(seg.get(x, y + 1))


def ABC125_C():
    from fractions import gcd
    N = int(input())
    A = list(map(int, input().split()))
    
    seg = SegmentTree(A, gcd, 0)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.get(0, i), seg.get(i + 1, N)))
    print(ans)


# AOJ_DSL_2_A()
# AOJ_DSL_2_B()
ABC125_C()

Submission status: Accepted

Solution code:
# operator.add(a, b)
# operator.mul(a, b)


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n - 1)
        for i in range(len(A)):
            self.__node[i + n - 1] = A[i]
        for i in range(n - 2, -1, -1):
            self.__node[i] = self.__dot(self.__node[2 * i + 1], self.__node[2 * i + 2])
    
    def update(self, i, c):
        i += self.__n - 1
        node = self.__node
        node[i] = c
        while i > 0:
            i = (i - 1) // 2
            node[i] = self.__dot(node[2 * i + 1], node[2 * i + 2])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n - 1
        r += self.__n - 1
        while (l < r):
            if (l % 2 == 0):
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l = (l - 1) // 2
            if (r % 2 == 0):
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r = (r - 1) // 2
        return self.__dot(vl, vr)
    

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
def AOJ_DSL_2_A():
    n, q = map(int, input().split())
    e = (1 << 31) - 1
    A = [e] * n
    seg = SegmentTree(A, min, e)

    for i in range(q):
        t, x, y = map(int, input().split())
        if t == 0:
            seg.update(x, y)
        else:
            print(seg.get(x, y + 1))


# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
def AOJ_DSL_2_B():
    from operator import add
    import sys
    n, q = map(int, input().split())
    e = 0
    A = [e] * n
    seg = SegmentTree(A, add, e)
    
    query = sys.stdin.readlines()
    for i in range(q):
        t, x, y = map(int, query[i].split())
        x -= 1
        if t == 0:
            A[x] += y
            seg.update(x, A[x])
        else:
            y -= 1
            print(seg.get(x, y + 1))


def ABC125_C():
    from fractions import gcd
    N = int(input())
    A = list(map(int, input().split()))
    
    seg = SegmentTree(A, gcd, 0)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.get(0, i), seg.get(i + 1, N)))
    print(ans)


# AOJ_DSL_2_B()
ABC125_C()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

left = [0]*(N+1)
for i in range(1,N+1):
    left[i] = fractions.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] = fractions.gcd(right[i+1],A[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:
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:
import sys
from fractions import gcd
input = sys.stdin.readline

def main():
    n=int(input())
    a=list(map(int,input().split()))
    f,b=[0]*(n+2),[0]*(n+2)
    f[1],b[n]=a[0],a[-1]
    for i in range(2,n+1):
        f[i],b[n-i+1]=gcd(a[i-1],f[i-1]),gcd(a[n-i],b[n-i+2])
    ans=0
    for i in range(1,n+1):
      ans=max(ans,gcd(f[i-1],b[i+1]))
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
num = int(input())
numarray = [int(i) for i in input().split()]

result_f = numarray[:] + [0]
result_t = [0] + numarray[:]
for i in range(num):
    result_f[num-i-1] = fractions.gcd(result_f[num-i], numarray[num-i-1])
    result_t[i+1] = fractions.gcd(result_t[i], result_t[i+1])

gcd_result = []
for i in range(num):
    gcd_result.append(fractions.gcd(result_t[i], result_f[i+1]))

print(max(gcd_result))

Submission status: Accepted

Solution code:
def main():
  import sys
  import fractions
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  l,r=[0]*(n-1),[0]*(n-1)
  for i in range(n-1):
    l[i]=fractions.gcd(l[i-1],a[i]) 
    r[i]=fractions.gcd(r[i-1],a[n-1-i])
  x=[0]*n
  for i in range(n):
    if i==0:
      x[i]=r[-1]
    elif i==(n-1):
      x[i]=l[-1]
    else:
      x[i]=fractions.gcd(l[i-1],r[n-2-i])
  print(max(x)) 
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
 
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] = (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:
n = int(input())
a = list(map(int, input().split()))

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

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

ans = max(gl[n-2], gr[n-2])
for i in range(1, n-1):
    ans = max(ans, gcd(gl[i-1], gr[n-2-i]))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
#n,m=map(int,input().split())
al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

import fractions
#gcd=fractions.gcd(a,b)#最大公約数

left=[0 for i in range(n)]
right=[0 for i in range(n)]
left[0]=al[0]
right[n-1]=al[n-1]

for i in range(1,n):
    left[i]=(fractions.gcd(al[i],left[i-1]))

for i in range(n-2,-1,-1):
    right[i]=fractions.gcd(al[i],right[i+1])
    
ansl=[]
#左端の値
ansl.append(right[1])
#右端の値
ansl.append(left[n-2])

for i in range(1,n-1):
    ansl.append(fractions.gcd(left[i-1],right[i+1]))
print(max(ansl))

Submission status: Accepted

Solution code:
# coding: utf-8
import fractions

n = int(input().rstrip())
numbers = [int(i) for i in input().rstrip().split(" ")]

l_list = [0 for i in range(n)]
l_list[0] = numbers[0]
for i in range(1, n):
    l_list[i] = fractions.gcd(l_list[i-1], numbers[i])

r_list = [0 for i in range(n)]
r_list[n-1] = numbers[n-1]
for i in reversed(range(0, n - 1)):
    r_list[i] = fractions.gcd(r_list[i+1], numbers[i])

ans = 0
for i in range(n):
    l = 0
    if i > 0:
        l = l_list[i - 1]
    r = 0
    if i < n - 1:
        r = r_list[i + 1]
    if l == 0:
        l = r
    if r == 0:
        r = l
    ans = max(ans, fractions.gcd(l, r))
print(ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

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

gcd_exclude = []
for i in range(n):
    gcd_exclude.append(gcd(gcd_to[i], gcd_from[i+1]))

print(max(gcd_exclude))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
 
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
n = int(input())
A = list(map(int, input().split()))
ans = 0
l = [A[0]]
r = [A[n-1]]
for i in range(1, n):
    l.append(gcd(l[i-1], A[i]))
    r.append(gcd(r[i-1], A[n-i-1]))
r.reverse()
# print(l, r)
for i in range(n):
    if i == 0:
        cost = r[1]
    elif i == n-1:
        cost = l[n-2]
    else:
        cost = gcd(l[i-1], r[i+1])
    if ans < cost:
        ans = cost

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:
# ABC125C - GCD on Blackboard
from fractions import gcd


class SegmentTree:
    __slots__ = ["_default_value", "_seg_func", "_size", "_tree"]

    def __init__(self, initial_values, default_value, seg_func) -> None:
        self._default_value = default_value
        self._seg_func = seg_func
        self._size = 1 << (len(initial_values) - 1).bit_length()
        self._tree = self._build(initial_values)

    def _build(self, initial_values) -> list:
        """Build a segment tree with initial values."""
        tree = [self._default_value] * (2 * self._size)

        for idx, val in enumerate(initial_values):  # set
            # modify val if needed (e.g. str -> ord())
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  # build
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def update(self, index: int, value: int) -> None:
        """Update index to value."""
        index += self._size - 1
        # modify value if needed as same as in _build()
        self._tree[index] = value
        while index:
            index = (index - 1) // 2
            self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

    def query(self, left: int, right: int):
        """Respond to query in [left, right]."""
        left += self._size
        right += self._size
        result = self._default_value
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    N, *A = map(int, open(0).read().split())
    seg = SegmentTree(A, 0, gcd)
    ans = max(gcd(seg.query(0, i), seg.query(i + 1, N)) for i in range(N))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self,arr,func=min,ie=2**63):
        self.n = 2**(len(arr)-1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.tree[self.n+i-1] = arr[i]
        for i in range(self.n-1)[::-1]:
            self.tree[i] = func(self.tree[2*i+1],self.tree[2*i+2])

    def set(self,index,x):
        index += self.n-1
        self.tree[index] = x
        while index:
            index = (index-1)//2
            self.tree[index] = self.func(self.tree[2*index+1],self.tree[2*index+2])

    def query(self,left,right):
        if right <= left:
            return self.ie
        left += self.n-1
        right += self.n-2
        tmp_l = self.ie
        tmp_r = self.ie
        while right-left>1:
            if left & 1 == 0:
                tmp_l = self.func(tmp_l,self.tree[left])
            if right & 1 == 1:
                tmp_r = self.func(self.tree[right],tmp_r)
                right -= 1
            left = left//2
            right = (right-1)//2
        if left == right:
            tmp_l = self.func(tmp_l,self.tree[left])
        else:
            tmp_l = self.func(self.func(tmp_l,self.tree[left]),self.tree[right])
        return self.func(tmp_l,tmp_r)

def gcd(x,y):
    if x==-1: return y
    if y==-1: return x
    while y: x,y = y,x%y
    return x

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

st = SegmentTree(A,gcd,-1)

maxgcd = 1

for i in range(N):
    maxgcd = max(maxgcd,gcd(st.query(0,i),st.query(i+1,N+1)))

print(maxgcd)

Submission status: Accepted

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

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

def main():
  n = int(input())
  As = list(map(int, input().split()))
  rgcds, lgcds = [0] * n, [0] * n
  lgcds[0], rgcds[-1] = As[0], As[-1]
  
  for i in range(1, n):
    lgcds[i] = gcd(lgcds[i-1], As[i])
    rgcds[n-(i+1)] = gcd(rgcds[n-(i)], As[n-(i+1)])
  
  max = -1
  for i in range(n):
    if i==0:
      tmp = rgcds[i+1]
    if i==n-1:
      tmp = lgcds[i-1]
    if 0 < i < n-1:
      tmp = gcd(lgcds[i-1], rgcds[i+1])
    if max < tmp:
      max = tmp
  print(max)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import functools
import fractions
import copy

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

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

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

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

# print(l)
# print(r)

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

print(ans)

Submission status: Accepted

Solution code:
import fractions
import functools

def main():
    n = int(input())
    a = [int(t)for t in input().split()]

    a_gcd = functools.reduce(fractions.gcd,a)
    a = [x//a_gcd for x in a]
    
    a_rev = a[::-1]

    lgcd = [0]
    rgcd = [0]
    for i in range(n):
        l = fractions.gcd(a[i],lgcd[i])
        r = fractions.gcd(a_rev[i],rgcd[i])
        lgcd.append(l)
        rgcd.append(r)

    rgcd = rgcd[::-1]
    g = [fractions.gcd(lgcd[i],rgcd[i+1]) for i in range(n)]
    
    print(max(g)*a_gcd)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

l = [0] * (n + 1)
r = [0] * (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])

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

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce


def gcd(v1, v2):
    v3 = v1 % v2
    if v3 == 0:
        return v2
    return gcd(v2, v3)


def main():
    N = int(input())
    A = [int(v) for v in input().split()]

    max_gcd = max(reduce(gcd, A[1:]), reduce(gcd, A[:N-1]))

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

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

    # print(left)
    # print(right)

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

    print(max_gcd)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = [int(i) for i in input().split()]
gcd_left = [0] * N
gcd_right = [0] * N
chk = 1
for i in range(N):
	if i == 0:
		chk = A[0]
	else:
		chk = fractions.gcd(chk,A[i])
	gcd_left[i] = chk
temp = 0
for i in range(N):
	num = N-1-i
	if i == 0 :
		temp = A[num]
	else:
		temp = fractions.gcd(temp,A[num])
	gcd_right[num] = temp
ans = 0
for i in range(N):
	if i == 0:
		ans = max(ans,gcd_right[1])
	elif i == N-1:
		ans = max(ans,gcd_left[N-2])
	else:
		ans = max(ans,fractions.gcd(gcd_left[i-1],gcd_right[i+1]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

gcd_from_left = [a[0]]
gcd_from_right = [a[-1]]

for i in range(1, n):
    gcd_from_left.append(fractions.gcd(gcd_from_left[i - 1], a[i]))
    gcd_from_right.append(fractions.gcd(gcd_from_right[i - 1], a[n - 1 - i]))

gcd_from_right.reverse()

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

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)
    divisors.sort(reverse=True)
    return divisors
import numpy as np
N = int(input())
B = list(map(int,input().split()))
B.sort()
memory = 0
C = np.array(B)
min_number = B[0]
if len(B) < 3:
    print(B[-1])
    exit()
for i in make_divisors(min_number):
    if min_number % i == 0:
        if len(C[C % i != 0]) < 2:
                memory = i
                break
min_number = B[1]
for i in make_divisors(min_number):
    if min_number % i == 0:
        if len(C[C % i != 0]) < 2:
            if memory < i:    
                memory = i
            break
print(memory)

Submission status: Accepted

Solution code:
#125_C
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 range(N-1,-1,-1):
    R[i]=gcd(R[i+1],A[i])
    
ans=0
for i in range(N):
    M=gcd(L[i],R[i+1])
    ans=max(ans,M)

print(ans)

Submission status: Accepted

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

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

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

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