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(x, y):
    if y == 0:
        return x
    while y != 0:
        x, y = y, x % y
    return x
class segment_gcd():
    def __init__(self,A,n,num):
        #####単位元######
        self.ide_ele = 0
        self.seg = [self.ide_ele] * 2 * num
        self.num = num
        # set_val
        for i in range(n):
            self.seg[i +num -1] = A[i]
            # built
        for i in range(num - 2, -1, -1):
            self.seg[i] = gcd(self.seg[2*i +1], self.seg[2*i +2])

    def update(self,k, x):
        k += num - 1
        self.seg[k] = x
        while k:
            k = (k - 1)//2
            self.seg[k] = gcd(self.seg[k*2 +1], self.seg[k*2 +2])

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

def examC():
    N = I()
    A = LI()
    # num:n以上の最小の2のべき乗
    num = 2 ** (N - 1).bit_length()
    Seggcd = segment_gcd(A,N,num)
    ans = -1
    for i in range(N):
        ans = max(ans, gcd(Seggcd.query(0, i), Seggcd.query(i + 1, N)))
    print(ans)


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

Solution code:
from itertools import accumulate
import math
import fractions

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

#最大公約数で累積和作る
B = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    B[i+1] = (fractions.gcd(B[i],A[i]))
    #逆向き,とったやつの反対端用   
    R[N-i -1] = (fractions.gcd(R[N-i], A[N-1 -i]))
 
ans = 0
for i in range(N):
    ans = max(ans, fractions.gcd(B[i], R[i+1]))
print(ans)

Submission status: Accepted

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

N= int(input())
A=[int(x) for x in input().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])
answer=0
for j,k in zip(gcd_L,gcd_R):
  answer=max(answer,gcd(j,k))
print(answer)

Submission status: Accepted

Solution code:
from fractions import*

class SEGMENTTREE():
    def __init__(self,lis,func,ele):
        self.monoidfunc=func
        self.identityelement=ele  # identity element
        self.n=len(lis)  # lis size
        self.node=[ele]*self.n+lis
        for i in range(self.n-1,0,-1):  # build
            self.node[i]=self.monoidfunc(self.node[i<<1],self.node[i<<1|1])
 
    def update(self, point, value):  # set value at position p (0-indexed)
        m=self.monoidfunc
        point+=self.n
        self.node[point]=value
        while point>1:
            self.node[point>>1]=m(self.node[point], self.node[point^1])
            point>>=1
 
    def get(self, l, r):  # result on interval [l, r) (0-indexed)
        m,e=self.monoidfunc,self.identityelement
        res=e
        l+=self.n
        r+=self.n
        while l<r:
            if l&1:
                res=m(res,self.node[l])
                l+=1
            if r&1:
                r-=1
                res=m(res,self.node[r])
            l>>=1
            r>>=1
        return res

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

segtree = SEGMENTTREE(a, gcd, 0)
 
ans = 1
for i, a in enumerate(a):
    segtree.update(i,0)
    ans = max(ans,segtree.get(0,n))
#    print(segtree.node)
    segtree.update(i,a)
print(ans)

Submission status: Accepted

Solution code:
from itertools import*;from fractions import*;u=accumulate;g=gcd;n,a=open(0);*a,=map(int,a.split());a=[0]+a+[0];print(max(starmap(g,zip(u(a,g),list(u(a[:1:-1],g))[::-1]))))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y>0:
    x,y=y,x%y
  return x
b=[a[0]]
for i in range(1,n-1):
  b.append(gcd(b[-1],a[i]))
c=[a[n-1]]
for i in range(1,n-1):
  c.append(gcd(c[-1],a[n-1-i]))
q=b[n-2]
for i in range(0,n-2):
  p=gcd(b[i],c[n-3-i])
  q=max(p,q)
print(max(q,c[n-2]))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
# MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	N=int(input())
	A=list(map(int,input().split()))
	
	L=[0]*N
	R=[0]*N
	M=[0]*N
	
	L[0] = A[0]
	R[N-1]=A[N-1]
	
	for i in range(1,N):
		L[i]=gcd(A[i],L[i-1])
	for i in range(N-2,0,-1):
		R[i]=gcd(A[i],R[i+1])
	
	M[0]=R[1]
	M[N-1]=L[N-2]
	
	for i in range(1,N-1):
		M[i]=gcd(L[i-1],R[i+1])
	
	print(max(M))
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
def GCM(a, b):
  if a < b:
    a += b
    b = a-b
    a -= b
  if a % b == 0:
    return b
  else:
    return GCM(b, a%b)

N = int(input())
A = list(map(int, input().split()))
l2r =[]
r2l = []
g = A[0]
for a in A:
  g = GCM(g, a)
  l2r.append(g)
g = A[-1]
for a in reversed(A):
  g = GCM(g, a)
  r2l.append(g)
r2l = list(reversed(r2l))
ans = r2l[1]
for i in range(1, N-1):
  ans = max(ans, GCM(l2r[i-1], r2l[i+1]))
ans = max(ans, l2r[N-2])
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
m = [0]*n

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

ans = 1
for a, b in zip(l, r):
    x = gcd(a, b)
    if ans < x:
        ans = x

print(ans)

Submission status: Accepted

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

N = int(input())
A = [int(i) for i in 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] = gca(A[i], L[i - 1])
for i in range(N - 2, -1, -1):
    R[i] = gca(A[i], R[i + 1])
maxg = 0
for i in range(1, N - 1):
    maxg = max(maxg, gca(L[i - 1], R[i + 1]))

print(max(L[N - 2], R[1], maxg))

Submission status: Accepted

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

if n == 2:
    print(max(a))
else:
    l = [0 for i in range(n)]
    r = [0 for i in range(n)]
    
    def gcd(x,y):
        while y != 0:
            x, y = y, x%y
    #        print(x,y)
        return(x)
    
    for i in range(1,n):
        l[i] = gcd(l[i-1],a[i-1])
        r[n-i-1] = gcd(r[n-i],a[n-i])
  #  print(l)
  #  print(r)
    ans = 0
    for i in range(n):
        if l[i] == -1:
            ans = max(ans,r[i])
        elif r[i] == -1:
            ans = max(ans,l[i])
        else:
            ans = max(ans,gcd(l[i],r[i]))
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd
input = sys.stdin.readline
 
class DisjointSparseTable:
    def __init__(self, a):
        # Identity element
        self.e = 0
        self.n = len(a)
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()
 
    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.n + step, step*2):
                if mid - step >= self.n:
                    continue
                # Forward
                val = self.e 
                for j in range(step):
                    val = gcd(self.table[-1][mid + j], val)
                    self.table[lv][mid + j] = val
                # Backward
                val = self.e
                for j in range(step):
                    val = gcd(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val
 
    # Returns f[l:r)
    def query(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[lv][l], self.table[lv][r-1])
 
 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd
input = sys.stdin.readline
 
class DisjointSparseTable:
    def __init__(self, a):
        # Identity element
        self.e = 0
        self.n = len(a)
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()
 
    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.size, step*2):
                if mid - step >= self.n:
                    continue
                # Forward
                val = self.e 
                for j in range(step):
                    val = gcd(self.table[-1][mid + j], val)
                    self.table[lv][mid + j] = val
                # Backward
                val = self.e
                for j in range(step):
                    val = gcd(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val
 
    # Returns f[l:r)
    def query(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[lv][l], self.table[lv][r-1])
 
 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd
input = sys.stdin.readline

class DisjointSparseTable:
    def __init__(self, a):
        # Identity element
        self.e = 0
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()

    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.size, step*2):
                # Forward
                val = self.e 
                for j in range(step):
                    val = gcd(self.table[-1][mid + j], val)
                    self.table[lv][mid + j] = val
                # Backward
                val = self.e
                for j in range(step):
                    val = gcd(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val

    # Returns f[l:r)
    def query(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[lv][l], self.table[lv][r-1])

 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd
input = sys.stdin.readline


class RgcdQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [0] * (2*self.size-1)
        self.initialize(a)

    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data[i] = gcd(self.data[i*2 + 1], self.data[i*2 + 2])

    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = gcd(self.data[2*k+1], self.data[2*k+2])

    # gcd value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = gcd(s, self.data[R-1])
            if L & 1:
                s = gcd(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    ST = RgcdQ(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(ST.query(0, i), ST.query(i+1, n)))
    print(ans)

Submission status: Accepted

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

class DisjointSparseTable:
    def __init__(self, a):
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[0] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a): 
            self.table[-1][i] = item
        self.build()

    def build(self):
        for lv in range(1, self.level):
            step = 2**lv
            level = self.level - 1 - lv
            for mid in range(step, self.size, step*2):
                # Calc forward
                val = 0
                for i in range(step):
                    val = gcd(self.table[-1][mid + i], val)
                    self.table[level][mid + i] = val
                # Calc backward
                val = 0
                for i in range(step):
                    val = gcd(self.table[-1][mid - 1 - i], val)
                    self.table[level][mid - 1 - i] = val
    
    # Returns f[l:r)
    def query(self, l, r):
        if l == r:
            return 0
        elif l == r - 1:
            return self.table[-1][l]
        level = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[level][l], self.table[level][r-1])

if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Submission status: Accepted

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

N=int(readline())
A=list(map(int,readline().split()))
B=A[::-1]

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

gcd_l=[0]*N
gcd_r=[0]*N

for i in range(N):
  gcd_l[i]=gcd(gcd_l[i-1],A[i])
  gcd_r[i]=gcd(gcd_r[i-1],B[i])
gcd_r=gcd_r[::-1]
#print(gcd_l)
#print(gcd_r)

gcd_l[-1]=0
gcd_r[0]=0

max_gcd=0
for i in range(N):
  max_gcd=max(max_gcd,gcd(gcd_l[i-1],gcd_r[(i+1)%N]))
print(max_gcd)

Submission status: Accepted

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


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


L = [0 for _ in range(N)]
R = [0 for _ in range(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 reversed(range(N-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[i-1])
    else:
        ans = max(ans, gcd(L[i-1], R[i+1]))

print(ans)

Submission status: Accepted

Solution code:
import math

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

def division_enumeration(num):
	ans = []
	d = math.floor(float(num)**(1/2))
	for i in range(1,d+1):
		if num % i == 0:
			ans.append(i)
			ans.append(num//i)

	return ans

trgs = sorted(set(division_enumeration(A[0]) + division_enumeration(A[1])), reverse = True)

for trg in trgs:
	cnt = 0
	cond = True
	for i in range(N):
		if A[i] % trg != 0:
			cnt += 1
			if cnt > 1:
				cond = False
				break
	if not cond:
		continue
	
	ans = trg
	break

print(ans)

Submission status: Accepted

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


class SegTree():
    def __init__(self, ide_ele, segfunc):
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = []
        self.num = 0

    def init(self, A):
        n = len(A)
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele]*(2*self.num)
        for i in range(n):
            self.seg[i+self.num-1] = A[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 += 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):
        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


import fractions
def main():
    s = SegTree(0, fractions.gcd)
    N = int(input())
    A = list(map(int, input().split()))
    s.init(A)
    ans = 0
    for i in range(N):
        ans = max(ans, fractions.gcd(s.query(0, i), s.query(i+1, N)))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
n = int(input())

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

front_gcd = []

a_init = al[0]
for a in al:
    a_init = fractions.gcd(a, a_init)
    front_gcd.append(a_init)
    
back_gcd = []

b_init = al[-1]
for b in al[::-1]:
    b_init = fractions.gcd(b, b_init)
    back_gcd.append(b_init)
    
back_gcd = back_gcd[::-1]

ans = 1
for i in range(n):
    if i == 0:
        x = back_gcd[1]
    elif i == n-1:
        x = front_gcd[-2]
    else:
        x = fractions.gcd(front_gcd[i-1], back_gcd[i+1])
    if x > ans:
        ans = x

print(ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

n = int(input())
a = [int(_) for _ in input().split()]
left, right, ans = ([0], [0], 0)

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

for i in range(n):
    g = fractions.gcd(left[i], right[n-i-1])
    if ans < g:
        ans = g

print(ans)

Submission status: Accepted

Solution code:
import fractions

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] = fractions.gcd(l[i-1], a[i])
  r[n-1-i] = fractions.gcd(r[n-i], a[n-1-i])

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

print (maxgcd)

Submission status: Accepted

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

l=[]
l.append(0)
l.append(0)
r=[]
r.append(a[n-1])
r.append(a[n-1])
g=[]

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


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

for j in range(0,n):
  g.append(gcd(l[j+1],r[n-j-1]))

print(max(g))

Submission status: Accepted

Solution code:
def gcd(a, b): #最大公約数
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
        
def main():
    n=int(input())
    a = list(map(int,input().split()))
    L=[a[0] for _ in range(n)]
    R=[a[n-1] for _ in range(n)]
    for i in range(1,n):
        L[i]=gcd(L[i-1],a[i])
    for i in range(1,n):
        R[i]=gcd(R[i-1],a[n-1-i])
    R.reverse()
    LR=[]
    for i in range(1,n-1):
        LR.append( gcd(L[i-1],R[i+1]) )
    if LR==[]:
        print(max(L[n-2],R[1] ))
    else:
        print(max(max(LR),L[n-2],R[1] ))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

L = [0]
R = [0]

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

M = []

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

ans = max(M)
print(ans)

Submission status: Accepted

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

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

leftGcd = [-1] * (N + 1)
leftGcd[0] = A[0]
for i, a in enumerate(A, start=1):
    leftGcd[i] = gcd(leftGcd[i - 1], a)

rightGcd = [-1] * (N + 1)
rightGcd[-1] = A[-1]
for i, a in enumerate(A[:: -1], start=2):
    rightGcd[-i] = gcd(rightGcd[-i + 1], a)

ans = max(leftGcd[-2], rightGcd[1])
for mid in range(N):
    ans = max(ans, gcd(leftGcd[mid], rightGcd[mid + 1]))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a % b)

def list_euclid(int_list):
    ans = int_list[0]
    if len(int_list) == 1:
        return ans
    kako_hash = {}
    kako_hash[ans] = ans
    for i in range(1,len(int_list)):
        if int_list[i] in kako_hash:
            continue
        else:
            kako_hash[int_list[i]] = int_list[i]
            ans = euclid(ans, int_list[i])
        if ans == 1:
            return ans
    return ans

n = int(input())
a = list(map(int, input().split()))
max_gcd = 0
b_int = {}
min = min(a)
if n == 2:
    max_gcd = max(a)
elif n < 5:
    for i in range(0, n):
        if a[0] in b_int:
            p = a.pop(0)
            # a.append(p)
        else:
            p = a.pop(0)
            b_int[p] = p
            x = list_euclid(a)
            if max_gcd < x:
                max_gcd = x
            a.append(p)
else:
    for i in range(0, n):
        if a[0] in b_int:
            p = a.pop(0)
            # a.append(p)
        else:
            if max_gcd == 0:
                p = a.pop(0)
                b_int[p] = p
                k = len(a) // 2
                x = 0
                y = list_euclid(a[0:k])
                if y == 1:
                    x = 1
                else:
                    z = list_euclid(a[k:len(a)])
                    x = euclid(y, z)
                if max_gcd < x:
                    max_gcd = x
                a.append(p)
            elif min <= max_gcd:
                break
            else:
                p = a.pop(0)
                b_int[p] = p
                k = len(a) // 2
                x = 0
                if k < 1:
                    x = list_euclid(a)
                else:
                    y = list_euclid(a[0:k])
                    if y == 1:
                        x = 1
                    else:
                        z = list_euclid(a[k:len(a)])
                        x = euclid(y, z)
                if max_gcd < x:
                    max_gcd = x
                a.append(p)
print(max_gcd)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)

Submission status: Accepted

Solution code:

import sys

def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))


if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)


tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)

for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)

Submission status: Accepted

Solution code:
import sys
import fractions


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    ls = [[0] * (n + 1) for _ in range(2)]
    for i in range(n):
        if i == 0:
            ls[0][i+1] = a[i]
            ls[1][-i-2] = a[-i-1]
        else:
            ls[0][i+1] = fractions.gcd(ls[0][i], a[i])
            ls[1][-i-2] = fractions.gcd(ls[1][-i-1], a[-i-1])
    mgcd = 0
    for i in range(n):
        mgcd = max(mgcd, fractions.gcd(ls[0][i], ls[1][i + 1]))
    print(mgcd)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
dp = [[0,0] for i in range(n)]

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


d1 = [0 for i in range(n)]
d2 = [0 for i in range(n)]
d1[0] = a[0]
d2[-1] = a[-1]

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

otv = 1

for i in range(n):
    if i == 0:
        otv = max(otv,d2[i + 1])
    elif i == n - 1:
        otv = max(otv,d1[i - 1])
    else:
        otv = max(otv, gcd(d2[i + 1],d1[i - 1]))
print(otv)

Submission status: Accepted

Solution code:
from fractions import gcd


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

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

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


if __name__ == '__main__':
    main()

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

ans = A[1]
for i in range(2,N):
    ans = gcd(ans,A[i])

d = []
for n in range(1,int(A[0]**0.5)+1):
    if A[0]%n == 0:
        d.append(n)
        d.append(A[0]//n)

d.sort(reverse=True)

for n in d:
    cnt = 0
    for a in A:
        if a%n==0:
            cnt += 1
    if cnt >= N-1:
        break
ans = max(ans,n)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import lru_cache

N = int(input())

#約数を列挙
@lru_cache(maxsize=1000)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

A_list = [make_divisors(int(e)) for e in input().split()]

all_divisors_list=[]

for i in A_list:
  all_divisors_list += i

collected_adl = Counter(all_divisors_list)

ans = 1
for a in collected_adl.most_common():
  if a[1] <= N-2:
    break
  elif a[0]>ans:
    ans=a[0]
    
print(ans)

Submission status: Accepted

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


def gcd_list(lst):
    a = lst[0]
    for i in lst[1:]:
        a = gcd(a, i)
    return a


n = int(input())
a = list(map(int, input().split()))
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
for i in range(n-1):
    l_i = 0 if 0 == i else l[i]
    l[i+1] = gcd(l_i, a[i])
for i in range(n)[::-1]:
    r_i1 = 0 if i == n-1 else r[i+1]
    r[i] = gcd(r_i1, a[i])
m = []
for i in range(n):
    r_i1 = 0 if i == n-1 else r[i+1]
    m.append(gcd(l[i], r_i1))
print(max(m))

Submission status: Accepted

Solution code:
import numpy as np

def gcd(v1, v2):
    if v1 == 0 or v2 == 0:
        return max(v1, v2)
#     print(v1, v2, v1%v2)
    if v1 % v2 == 0:
        return v2
    return gcd(v2, v1%v2)

N = int(input())

A = list(map(int, input().split()))
L = np.zeros(N+1)
R = np.zeros(N+1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
#     print(N-i-1, N-i, N-i-1)
    R[N-i-1] = gcd(R[N-i], A[N-i-1])
M = []
for j in range(N):
    M.append(gcd(L[j], R[j+1]))

print(int(max(M)))

Submission status: Accepted

Solution code:
def gcd(a, b):
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)
def mgcd(l):
  if len(l) == 1:
    return l[0]
  else:
    new_l = []
    for i in range(-(-len(l)//2)):
      temp = gcd(l[i], l[-i-1])
      if temp == 1:
        return 1
      else:
        new_l.append(temp)
    return mgcd(new_l)

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans1 = mgcd(a[1:])
min_gcd = 1001001001
min_idx = 0
for i in range(1,n):
  temp = gcd(a[0], a[i])
  if temp < min_gcd:
    min_gcd = temp
    min_idx = i
a.pop(min_idx)
ans2 = mgcd(a)
print(max(ans1, ans2))