Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

3
7 6 8

Sample Output 1

2

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

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
a_list = list(map(int, input().split()))
gcd_l = [0] * (N+1) 
gcd_r = [0] * (N+1) 
for i, a in enumerate(a_list):
    gcd_l[i+1] = gcd(gcd_l[i], a)
for i in range(N, 0, -1):
    a = a_list[i-1]
    gcd_r[i-1] = gcd(gcd_r[i], a)
ans = 1
#print(gcd_l, gcd_r)
for i in range(N):
    tmp = gcd(gcd_l[i], gcd_r[i+1])
    ans = max(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
# 1,7,6,8,1,
# L[i]=A[i]

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

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

ans=1
for i in range(len(A)):
  if i==0:
    if ans<R[i+1]:
      ans=R[i+1]
  elif i==len(A)-1:
    if ans<L[i-1]:
      ans=L[i-1]
  else:
    p=gcd(L[i-1],R[i+1])
    if ans<p:
      ans=p
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

# 2数の最大公約数
def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

# リストの最大公約数
def gcd_list(nums):
    return reduce(gcd, nums)

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

#a[i]より前方要素の最大公約数を保持
l = [0 for _ in range(n)]
l[0] = 0
for i in range(1, n):
    l[i] = gcd(l[i-1], a[i-1])
# print(l)

#a[i]より後方要素の最大公約数を保持
r = [0 for _ in range(n)]
r[n-1] = 0
for i in reversed(range(n-1)):
    r[i] = gcd(r[i+1], a[i+1])
# print(r)

# a[i]を除いた最大公約数を計算
ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i],r[i]))

# 出力
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import sys

n = int(input())
nums = list(map(int, sys.stdin.readline().split()))

l_gcds = [nums[0]]
r_gcds = [nums[n-1]]

for i in range(n - 1):
  l_gcds.append(gcd(l_gcds[i], nums[i+1]))
for j in range(n - 1, 0, -1):
  r_gcds.append(gcd(r_gcds[n - 1 - j], nums[j-1]))

max_num = 0
for k in range(n):
  t = 0
  if k == 0:
    t = l_gcds[n-2]
  elif k == n-1:
    t = r_gcds[n-2]
  else:
    t = gcd(l_gcds[k-1], r_gcds[n-2-k])
  if t > max_num:
    max_num = t

print(max_num)

Submission status: Accepted

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

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.nodes[r-1])
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

segt = SegTree(A, lambda x,y:gcd(x,y), 0)
ans = 0
for i in range(N):
    l = segt.query(0,i)
    r = segt.query(i+1,N)
    g = gcd(l,r)
    ans = max(ans, g)
print(ans)

Submission status: Accepted

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

def yakusuu(a):
    P = [a]
    for k in range(2,math.floor(math.sqrt(a))+1):
        if a % k == 0:
            P.append(k)
            P.append(a//k)
    return P

P = set(yakusuu(A[-1])+yakusuu(A[-2]))
ans = 1
for e in P:
    f = 0
    for a in A:
        if a%e != 0:
            f += 1
        if f == 2:
            break
    if f <= 1:
        ans = max(ans,e)
print(ans)

Submission status: Accepted

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

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

s = [0]*n
for i in range(n):
    if i == 0:
        s[i] = r[n-1]
    elif i == n-1:
        s[i] = l[n-1]
    else:
        s[i] = fractions.gcd(l[i], r[n-(i+1)])
#print(s)
print(max(s))

Submission status: Accepted

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

n, *a = map(int, open(0).read().split())

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

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

Submission status: Accepted

Solution code:
import sys

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == -1: return a
    while a % b > 0:
        a, b = b, a % b
    return b         

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    lGCD = [-1 for _ in range(N + 1)]
    rGCD = [-1 for _ in range(N + 1)]

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

    maxGCD = 1
    for i in range(N):
        gcdI = gcd(lGCD[i], rGCD[i + 1])
        maxGCD = max(maxGCD, gcdI)
    print(maxGCD)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
class SegTree:
  def segfunc(self, x, y):
    return gcd(x, y) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    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 += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      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
seg = SegTree(N, 0, a)
res = 0
for i in range(N):
  res = max(res, gcd(seg.query(0, i), seg.query(i + 1, N)))
  #print(seg.query(0, i), seg.query(i + 1, N))
print(res)

Submission status: Accepted

Solution code:
# https://juppy.hatenablog.com/entry/2019/05/02/%E8%9F%BB%E6%9C%AC_python_%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder

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

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



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

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

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

    ans = 0
    # i番目を書き換える -> 考慮しない
    for i in range(n):
        ans = max(ans,gcd(query(0,i),query(i+1,n)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
N, = map(int, input().split())
X = list(map(int, input().split()))
rs = [0] * N
for i in range(N-1, 0, -1):
    rs[i-1] = gcd(rs[i], X[i])
ls = [0] * N
for i in range(N-1):
    ls[i+1] = gcd(ls[i], X[i])

s = 0
for i in range(N):
    s = max(s, gcd(ls[i], rs[i]))
print(s)

Submission status: Accepted

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

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

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

ans = max(lg[-2], rg[1])
for l,r in zip(lg,rg[2:]):
    g = gcd(l,r)
    ans = max(ans, g)
print(ans)

Submission status: Accepted

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# 約数列挙
def find_divisor(n):
    divisors=[]
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            if i*i!=n:
                divisors.append(n // i)
    return divisors


def main():
    N=I()
    A=LI()
    candidate = set(find_divisor(A[0]) + find_divisor(A[1]))
    ans = 0
    for c in candidate:
        ng_cnt = 0
        for a in A:
            if a%c:
                ng_cnt+=1
        if ng_cnt<=1:
            ans = max(ans, c)
    print(ans)
        
    
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


fromLeft = [0]
fromRight = [0]
for i, a in enumerate(A):
    if i == 0:
        fromLeft.append(a)
        continue
    fromLeft.append(gcd(a, fromLeft[-1]))

for i, a in enumerate(A[::-1]):
    if i == 0:
        fromRight.append(a)
        continue
    fromRight.append(gcd(a, fromRight[-1]))
fromRight = fromRight[::-1]

fromLeft[0] = fromRight[1]
fromRight[-1] = fromLeft[-2]

ans = 1
for i in range(N):
    gl = fromLeft[i]
    gr = fromRight[i + 1]
    ans = max(ans, gcd(gl, gr))

print(ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import fractions
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15

def getyaku(n):
    res = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            res.append(i)
            res.append(n // i)

    return(sorted(list(set(res))))

def judge(cand, nums):
    w = 0
    for num in nums:
        if num % cand !=0:
            if w == 1:
                return False
            else:
                w += 1

    return True

def main():
    n = getN()
    nums = getlist()

    ans = 0
    cands = getyaku(nums[0])

    for cand in cands:
        if judge(cand, nums):
            if ans < cand:
                ans = cand
    cands = getyaku(nums[1])

    for cand in cands:
        if judge(cand, nums):
            if ans < cand:
                ans = cand

    print(ans)
    return

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
lgcd = [0]*N
rgcd = [0]*N
from fractions import gcd
#def gcd(a,b):
#    if b == 0:return a
#    else:return gcd(b, a%b)

temp_lgcd = A[0]
for i in range(N):
    temp_lgcd = gcd(temp_lgcd,A[i])
    lgcd[i] = temp_lgcd

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

ans = 0
for i in range(N):
    if i == 0:
        calc_gcd = rgcd[1]
    elif i == N-1:
        calc_gcd = lgcd[-2]
    else:
        calc_gcd = gcd(lgcd[i-1],rgcd[i+1])
    ans = max(ans,calc_gcd)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

gcd_left = [0] * n
gcd_right = [0] * n
gcd_left[1] = a[0]
gcd_right[n-2] = a[n-1]

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

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

gcd_ex = [0] * n
gcd_ex[0] = gcd_right[0]
gcd_ex[n-1] = gcd_left[n-1]

for i in range(1,n-1):
    gcd_ex[i] = gcd(gcd_left[i], gcd_right[i])

print(max(gcd_ex))

Submission status: Accepted

Solution code:
def gcd(n,m):#n,mは正の整数、最大公約数　許容は？
    if n==0:
        return m
    elif m==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

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

list1=[1 for i in range(0,N)]
list2=[1 for i in range(0,N)]
list1[0]=A[0]
list2[0]=A[N-1]

for i in range(1,N):
    list1[i]=gcd(list1[i-1],A[i])
    list2[i]=gcd(list2[i-1],A[N-1-i])
m=list2[N-2]
for i in range(0,N-2):
    test=gcd(list1[i],list2[N-3-i])
    if test>m:
        m=test
test=list1[N-2]
if test>m:
    m=test
print(m)

Submission status: Accepted

Solution code:
from fractions import gcd

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

    lgcd = [0 for _ in range(n)]
    rgcd = [0 for _ in range(n)]
    for i in range(n):
        if i == 0:
            lgcd[i] = a[i]
            rgcd[-i-1] = a[-i-1]
        else:
            lgcd[i] = gcd(lgcd[i-1],a[i])
            rgcd[-i-1] = gcd(rgcd[-i],a[-i-1]) 
    
    ans = 0
    for i in range(n):
        if i == 0:
            ans = max(ans,rgcd[i+1])
        elif i == n-1:
            ans = max(ans,lgcd[i-1])
        else:
            ans = max(ans,gcd(lgcd[i-1],rgcd[i+1]))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n = int(input())
    a = list(map(int,input().split()))
    l = [0]*n
    r = [0]*n
    for i in range(n):
        if i == 0:
            l[0] = a[0]
            r[n-1] =a[n-1]
        else:
            l[i] = gcd(a[i],l[i-1])
            r[n-i-1] = gcd(a[n-i-1],r[n-i])
    if n > 2:
        ans = max(r[1],l[n-2])
    else:
        ans = max(a)
    for i in range(1,n-1):
        ans = max(ans,gcd(l[i-1],r[i+1]))

    print(ans)
if __name__ == "__main__":
    main() 
    
#endline===============================================

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
a.sort()
d=defaultdict(int)

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

for i in make_divisors(a[0]):
    d[i]+=1
for g in make_divisors(a[1]):
    d[g]+=1

for g in range(2,n):
    for i,m in d.items():
        if a[g]%i==0:
            d[i]+=1

ans=1
for i,m in d.items():
    if m==n-1 or m==n:
        ans=max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
d={}

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
for i in make_divisors(a[0]):
    d[i]=1


for g in range(1,n):
    if g==1:
        new={}
        for i,m in d.items():
            if a[g]%i==0:
                d[i]+=1
                if not a[g]//i in d.keys():
                    new[a[g]//i]=1
        d.update(new)
    else:
        for i,m in d.items():
            if a[g]%i==0:
                d[i]+=1

ans=1
for i,m in d.items():
    if m==n-1 or m==n:
        ans=max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline

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

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

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

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

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

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

l_gcd = [0]*(N+2)
r_gcd = [0]*(N+2)

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

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

ans = 0
for i in range(1, N+1):
    if i==1:
        ans = max(ans, r_gcd[i+1])
    elif i==N:
        ans = max(ans, l_gcd[i-1])
    else:
        ans = max(ans, gcd(l_gcd[i-1], r_gcd[i+1]))

print(ans)

Submission status: Accepted

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

from fractions import gcd

L=[0]*(n+1)
R=[0]*(n+1)
M=[0]*n

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

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

max_M=0
for i in range(n):
    M[i]=gcd(L[i],R[i+1])
    if max_M < M[i]: max_M=M[i]
print(max_M)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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

L=[]
R=[]

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

for i,a in enumerate(A[::-1]):
    if i==0:
        R.append(a)
    else:
        R.append( gcd(R[-1],a) )
R=R[::-1]

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

print ans

Submission status: Accepted

Solution code:
import fractions

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

def main():
    n = int(input())
    num_list = 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],num_list[i]))
        right[n - i - 1] = (fractions.gcd(right[n - i],num_list[n - 1 - i]))
    
    ans = 0
    for i in range(n):
        ans = max(ans,fractions.gcd(left[i],right[i + 1]))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

from fractions import gcd

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
*A, = map(int, input().split())
L, R = [0]*(n+1), [0]*(n+1)
for i, (a, b) in enumerate(zip(A, A[::-1])):
    L[i+1] = gcd(L[i], a)
    R[i+1] = gcd(R[i], b)
L, R = L[:n], R[:n][::-1]
print(max(gcd(l, r) for l, r in zip(L, R)))

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
*A, = map(int, input().split())
B = A[::-1]
L, R = [0]*(n+1), [0]*(n+1)
for i in range(n):
    L[i+1] = gcd(L[i], A[i])
    R[i+1] = gcd(R[i], B[i])
L, R = L[:n], R[:n][::-1]
print(max(gcd(l, r) for l, r in zip(L, R)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd


class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t <= size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def query(self, start, stop):
        result = 0
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = gcd(result, self._data[l])
            if r & 1 == 0:
                result = gcd(result, self._data[r - 1])
            l = l // 2
            r = (r - 1) // 2
        return result

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

st = SegmentTree(N)
st.update_all(A)

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

Submission status: Accepted

Solution code:
def main():
  from fractions import gcd
  n=int(input())
  num=list(map(int,input().split()))
      
  gcdl=[0]*n
  gcdr=[0]*n
  gcdl[0],gcdr[0]=num[0],num[-1]
  for i in range(n-1):
    gcdl[i+1]=gcd(num[i+1],gcdl[i])
    gcdr[i+1]=gcd(num[-i-2],gcdr[i])

  ans=0
  for i in range(n):
    if i!=0 and i!=n-1:
      test=gcd(gcdl[i-1],gcdr[-i-2])
    elif i==0:
      test=gcdr[-2]
    else:
      test=gcdl[-2]

    if test>ans:
      ans=test
  print(ans)
 
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from fractions import gcd

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] = gcd(L[i], A[i])
  
for i in range(N,0,-1):
  R[i-1] = gcd(R[i], A[i-1])
  
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
from functools import reduce
n=int(input())
a=list(map(int,input().split()))


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

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

Submission status: Accepted

Solution code:
from fractions import gcd


class SegmentTree():
    _data = []
    _offset = 0

    def __init__(self, size):
        t = 1
        while t <= size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def update_all(self, iterable):
        for i, v in enumerate(iterable):
            self._data[i + self._offset] = v
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def _query(self, start, stop, index, left, right):
        if right <= start or stop <= left:
            return 0
        if start <= left and right <= stop:
            return self._data[index]
        a = self._query(start, stop, index * 2 + 1, left, (left + right) // 2)
        b = self._query(start, stop, index * 2 + 2, (left + right) // 2, right)
        return gcd(a, b)

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self._offset + 1)


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

st = SegmentTree(N)
st.update_all(A)

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

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
#print(l)
l2 = list(reversed(l))
#print(l2)
#from itertools import combinations
#a = list(combinations(l, n-1))
#print(a)
from fractions import gcd
L, R = [0], [0]
for i in range(n):
    L.append(gcd(L[i],l[i]))
    R.append(gcd(R[i],l2[i]))
#print(L)
R = list(reversed(R))
#print(R)
g = []
for j in range(n):
    g.append(gcd(L[j],R[j+1]))
print(max(g))


#from functools import reduce

#def gcd_list(numbers):
#    return reduce(gcd, numbers)