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:
# http://tsutaj.hatenablog.com/entry/2017/03/29/204841
class SegmentTree:
    def __init__(self, v, func, init_val):
        self.func = func
        self.init_val = init_val

        sz = len(v)

        self.n = 1
        while self.n < sz:
            self.n *= 2

        self.node = [self.init_val for _ in range(2 * self.n - 1)]
        # 元配列 v をセグメント木で表現する
        # 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        # セグメント木全体で必要なノード数は 2n - 1 個である

        for i in range(sz):
            self.node[i + self.n - 1] = v[i]
        # 最下段に値を入れたあとに、下の段から順番に値を入れる

        for i in range(self.n - 2, -1, -1):
            self.node[i] = self.func(self.node[2 * i + 1], self.node[2 * i + 2])
        # 値を入れるには、自分の子の 2 値を参照すれば良い

    def update(self, x, val):
        x += self.n - 1
        # 最下段のノードにアクセスする

        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = self.func(self.node[2 * x + 1], self.node[2 * x + 2])
        # 最下段のノードを更新したら、あとは親に上って更新していく

    # 要求区間 [a, b) 中の要素の最小値を答える
    # k := 自分がいるノードのインデックス
    # 対象区間は [l, r) にあたる

    def get_val(self, a, b, k, l, r):
        if r <= a or b <= l: return self.init_val
        # 要求区間と対象区間が交わらない -> 適当に返す

        if a <= l and r <= b: return self.node[k]
        # 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う

        vl = self.get_val(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.get_val(a, b, 2 * k + 2, (l + r) // 2, r)
        return self.func(vl, vr)
        # 要求区間が対象区間の一部を被覆 -> 子について探索を行う
        # 左側の子を vl ・ 右側の子を vr としている
        # 新しい対象区間は、現在の対象区間を半分に割ったもの


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


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

st = SegmentTree(v=a, func=gcd, init_val=0)

g = max(
    gcd(
        st.get_val(0, drop_idx, 0, 0, st.n),
        st.get_val(drop_idx + 1, N, 0, 0, st.n)
    ) for drop_idx in range(N)
)
print(g)

Submission status: Accepted

Solution code:
import fractions
import collections
N = int(input())
As = list(map(int, input().split()))
lgcd = [As[0]]
rgcd = collections.deque([As[-1]])
l = As[0]
r = As[-1]
for i in range(1, N):
    l = fractions.gcd(l, As[i])
    r = fractions.gcd(r, As[-(i+1)])
    lgcd.append(l)
    rgcd.appendleft(r)
ans = [lgcd[N-2], rgcd[1]]
for i in range(1, N-1):
    ans.append(fractions.gcd(lgcd[i-1], rgcd[i+1]))
print(max(ans))

Submission status: Accepted

Solution code:
import fractions

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

firstgcds = [0]
lastgcds = [0]
for i in range(0, N):
    firstgcds.append(fractions.gcd(firstgcds[i], A[i]))
    lastgcds.append(fractions.gcd(lastgcds[i], A[-i-1]))
ans = 0
for i in range(0, N):
    preans = fractions.gcd(firstgcds[i], lastgcds[-i-2])
    if ans < preans:
        ans = preans
if ans < firstgcds[N-1]:
    ans = firstgcds[N-1]
print(ans)

Submission status: Accepted

Solution code:
import fractions


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

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

    ans = []
    for i in range(N):
        ans.append(fractions.gcd(gcd_l[i], gcd_r[i + 1]))

    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions


def main() -> None:
    N = int(input())
    A = [int(x) for x in 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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import fractions

class SegmentTree():

    def __init__(self, n):
        self.n = 1
        # nに最も近い2のべき乗を計算
        while self.n < n:
            self.n *= 2

        self.N0 = 2**(n-1).bit_length()

        # ノードの個数は2n-1個
        # 初期化はモノイドで
        self.dat = [0] * (self.n * 2 - 1)
        
    def update(self, i, x):
        i = i + self.n - 1
        self.dat[i] = x

        while(i > 0):
            i = (i-1) // 2
            self.dat[i] = fractions.gcd(self.dat[i * 2 + 1], self.dat[i * 2 + 2])

    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        ret = 0
        
        while L < R:
            if R & 1:
                R -= 1
                ret = fractions.gcd(ret, self.dat[R-1])
                
            if L & 1:
                ret = fractions.gcd(ret, self.dat[L-1])
                L += 1
                
            L >>= 1; R >>= 1
        return ret


if __name__ == "__main__":
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    st = SegmentTree(N)
    for i in range(N):
        st.update(i, A[i])
    
    ans = - (10 ** 10)
    for i in range(N):
        leftv = st.query(0, i)
        rightv = st.query(i+1, N)

        # for Debug    
        #print("**{0}** | {1} {2}".format(i, leftv, rightv))
        ans = max(ans, fractions.gcd(leftv, rightv)) 

    # for Debug
    #print(st.dat)

    print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

    return divisors

ans = 1
for i in make_divisors(a[0]):
    cnt = 0
    for j in a[1:]:
        if j%i:
            cnt += 1
            if cnt >1:
                break
    if cnt < 2:
        ans = max(ans, i)
ans = max(ans, reduce(gcd, a[1:]))
print(ans)

Submission status: Accepted

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

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

data_ans=[]
data1=[A[0]]
data2=[A[N-1]]
l=A[0]
m=A[N-1]
for i in range(1,N-2):
  l=gcd(l,A[i])
  m=gcd(m,A[N-i-1])
  data1.append(l)
  data2.append(m)
l=gcd(l,A[N-2])
m=gcd(m,A[1])
data_ans.append(l)
data_ans.append(m)
for i in range(0,N-2):
  data_ans.append(gcd(data1[i],data2[N-3-i]))
print(max(data_ans))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
import itertools

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


def gcds(list_):
    return list(itertools.accumulate(list_, fractions.gcd))


def reversed_gcds(list_):
    return list(itertools.accumulate(reversed(list_), fractions.gcd))


as_accum_gcd, as_rev_accum_gcd = gcds(as_), reversed_gcds(as_)

dropped_gcds = []
for i in range(len(as_)):
    if i == 0:
        dropped_gcd = as_rev_accum_gcd[-2]
    elif i == len(as_) - 1:
        dropped_gcd = as_accum_gcd[-2]
    else:
        dropped_gcd = fractions.gcd(as_accum_gcd[i - 1], as_rev_accum_gcd[-2 - i])
    dropped_gcds.append(dropped_gcd)

print(max(dropped_gcds))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
  
n = int(input())
A = list(int(i) for i in (input().split()))

front = []
end = []
for i in range(n):
  if(i == 0):
    front.append(gcd(*[A[0]]))
    end.append(gcd(*[A[n-1]]))
  else:
    front.append(gcd(*[front[i - 1],A[i]]))
    end.append(gcd(*[end[i - 1],A[n-1-i]]))

ans = 0
for i in range(n):
  if(i == 0):
    tmp = end[n-2]
  elif(i == n-1):
    tmp = front[n-2]
  else:
    tmp = gcd(*[front[i-1],end[n-2-i]])
  if(ans < tmp):
    ans = tmp
print(ans)

Submission status: Accepted

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

import sys
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd

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

print(counter)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
answer = sorted(a)[1]
if n == 2:
    pass
else:
    for b in reversed(range(answer)):
        cnt = 2
        flag = True
        for i in range(n):
            if a[i] % answer != 0:
                cnt -= 1
            if cnt == 0:
                flag = False
                break
        if flag:
            break
        answer -= 1
print(answer)

Submission status: Accepted

Solution code:
#import math
from fractions import gcd

N = int(input())
As = [int(elm) for elm in input().split(" ")] 

if N >= 3:
    L = []
    R = []

    gl = As[0]
    gr = As[N-1]
    L.append(gl)
    R.append(gr)

    for i in range(1, N-1):
        gl = gcd(gl, As[i]) 
        L.append(gl)

    for i in range(1, N-1):
        gr = gcd(gr, As[N-i-1])
        R.append(gr)

    for i in range(N):
        if i == 0:
            max_g = R[N-2]
        else:
            if i == N-1:
                cur_g = L[N-2]
            else:
                cur_g = gcd(L[i-1], R[N-2-i])
            max_g = max(max_g, cur_g)

    out = max_g
else:
    out = max(As)

print(out)

Submission status: Accepted

Solution code:
#import math
from fractions import gcd

N = int(input())
As = [int(elm) for elm in input().split(" ")] 


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

if N >= 3:
    gs = []
    for i in range(0, (N//2)*2 , 2):
        g = gcd(As[i], As[i+1])
        gs.append(g)
    if N % 2 == 1:
        gs.append(As[N-1])

    while len(gs) != 2:
        #print(gs)
        new_gs = []
        N1 = len(gs)
        #print("len",len(gs), (N1//2)*2)
        for i in range(0, (N1//2)*2, 2):
            g = gcd(gs[i], gs[i+1])
            new_gs.append(g)
        if N1 % 2 == 1:
            new_gs.append(gs[-1])
        gs = new_gs

    g1, g2 = gs
    d1 = divisor(g1) 
    d2 = divisor(g2) 
    ds = sorted(d1 + d2, reverse=True)

    #print(gs)
    #print(ds)
    for d in ds:
        count = sum([int(A % d == 0) for A in As])
        if count >= N-1:
            out = d
            break

else:
    out = max(As)

print(out)

Submission status: Accepted

Solution code:
def gcd(n,m):
  a=max(n,m)
  b=min(n,m)
  while b!=0:
    a,b=b,a%b
  return a
n=int(input())
l=list(map(int,input().split()))
l1=[]
l1.append(l[0])
for i in range(1,n):
  l1.append(gcd(l1[-1],l[i]))
l2=[]
l2.append(l[-1])
for i in range(n-2,-1,-1):
  l2.append(gcd(l2[-1],l[i]))
l3=[]
for i in range(2,n):
  l3.append(gcd(l1[i-2],l2[n-i-1]))
l3.append(l2[n-2])
l3.append(l1[n-2])
print(max(l3))

Submission status: Accepted

Solution code:
import math
def get_div_list(num):
    if num == 1:
        return [1]
    else:
        div_list = []
        div_list.append(1)
        div_list.append(num)
        for i in range(2, math.floor(math.sqrt(num))+ 1):
            if num % i == 0:
                div_list.append(i)
                div_list.append(num // i)
        list(set(div_list))
        div_list.sort(reverse = True)
        return div_list
n = int(input())
a = [int(_) for _ in input().split()]
d = sorted(list(set(get_div_list(a[0])+get_div_list(a[1]))))[::-1]
for i in range(len(d)):
    cnt = 0
    for j in range(n):
        if a[j]%d[i]==0:cnt+=1
    if cnt >= n-1:
        print(d[i])
        break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


def gcd(a, b):
    """ Greatest Common Divisor(最大公約数) """
    while b:
        a, b = b, a % b
    return a


N = d_in()
A_list = ds_in()

cum_gcd = [A_list[0]]
for a in A_list[1:]:
    pre = cum_gcd[-1]
    cum_gcd.append(gcd(a, pre))

reverse = [A_list[-1]]
for a in A_list[-2::-1]:
    pre = reverse[-1]
    reverse.append(gcd(a, pre))

ans = max(reverse[-2], cum_gcd[-2])
for i in range(1, N-1):
    # i番目を抜かす
    ans = max(ans, gcd(cum_gcd[i-1], reverse[N-2-i]))

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

l = [0]*(n+2) # l(i) = A1, A2, ..., A(i-1)のgcd
r = [0]*(n+2) # r(i) = Ai, A(i+1), ..., A(n)のgcd

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

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

print (max(ext))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a  
lgcds = [A[0]]
rgcds = [A[N-1]]
for n in range(N-2):
    lgcds.append(gcd(lgcds[-1],A[n+1]))
    rgcds.append(gcd(rgcds[-1],A[-2-n]))
gcds = [lgcds[-1],rgcds[-1]]
for i in range(N-2):
    gcds.append(gcd(lgcds[i],rgcds[-2-i]))
print(max(gcds))

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]

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

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
g=[]
l=[0]
r=[0]
for i in range(n):
    l.append(gcd(l[i], a[i]))
    r.append(gcd(r[i], a[-i-1]))
r.reverse()
for i in range(n):
    g.append(gcd(l[i], r[i+1]))
print(max(g))

Submission status: Accepted

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

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

F = [0] * N
B = [0] * N
for i in range(N):
    if i - 1 <= -1:
        F[i] = A[i]
    else:
        F[i] = gcd(F[i - 1], A[i])

for i in range(N-1,-1,-1):
    if i + 1 >= N:
        B[i] = A[i]
    else:
        B[i] = gcd(B[i + 1], A[i])


ans = 0
for i in range(1,N-1):
    ans = max(ans, gcd(F[i - 1], B[i + 1]))

ans = max(ans, F[N - 2])
ans = max(ans, B[1])

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

Submission status: Accepted

Solution code:
import fractions

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

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self,param,default,func):
        if isinstance(param,list):
            n=len(param)
        else:
            n=param
        self.d=default
        self.leaf=1<<(n-1).bit_length()
        if isinstance(param,list):
            self.tree=[default]*(self.leaf-1)+param+[default]*(self.leaf-n)
            for i in range(self.leaf-2,-1,-1):
                self.tree[i]=func(self.tree[i*2+1],self.tree[i*2+2])
        else:
            self.tree=[default]*(self.leaf*2-1)
        self.f=func
    def find(self,i):
        return self.tree[i+self.leaf-1]
    def update(self,idx,a):
        idx+=self.leaf-1
        self.tree[idx]=a
        while idx:
            idx=(idx-1)>>1
            self.tree[idx]=self.merge(self.tree[idx*2+1],self.tree[idx*2+2])
    def merge(self,a,b):
        return self.f(a,b)
    def get_top(self):
        return self.tree[0]
    def query(self,a,b): #[a,b)
        T=self.tree
        l,r=a+self.leaf-1,b+self.leaf-1
        res=self.d
        while l<r:
            if not l%2:
                res=self.merge(res,T[l])
                l+=1
            if not r%2:
                r-=1
                res=self.merge(res,T[r])
            l>>=1
            r>>=1
        return res

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

n=int(input())
A=list(map(int,input().split()))
seg=SegmentTree(A,0,gcd)
ans=0
for i in range(n):
    seg.update(i,0)
    ans=max(ans,seg.get_top())
    seg.update(i,A[i])
print(ans)

Submission status: Accepted

Solution code:
import itertools
import fractions

n = int(input())
a = list(map(int, input().split()))
cumgcd = list(itertools.accumulate(a, func=fractions.gcd))
cumgcd_rv = list(itertools.accumulate(a[::-1], func=fractions.gcd))
ans = max(cumgcd[-2],cumgcd_rv[-2])
if n == 2:
  ans = max(a)
else:
  for key,value in enumerate(cumgcd[:n-2]):
    ans = max(ans, fractions.gcd(value,cumgcd_rv[n-3-key]))
print(ans)

Submission status: Accepted

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

def getNum(a, b):
    while(True):
        if a == 0:
            return b
        a, b = max(a, b), min(a, b)
        a %= b

leftGBC, rightGBC= [AList[0]], [AList[-1]]
for i in range(1, N):
    leftGBC.append(getNum(leftGBC[i - 1], AList[i]))
for i in range(1, N):
    rightGBC.append(getNum(rightGBC[i - 1], AList[N - i - 1]))

rightGBC.reverse()

ans = max(leftGBC[-2], rightGBC[1])
for i in range(0, N-2):
    ans = max(getNum(leftGBC[i], rightGBC[i + 2]), ans)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

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

# 先頭から連続する要素の最大公約数の列
L = [0] + list(accumulate(A, gcd))
# 末尾から連続する要素の最大公約数
R = [0] + list(accumulate(reversed(A), gcd))

# Aの各要素について、それを使用しない場合の最大公約数の最大値をL, Rを用いて求める
ans = max(
    gcd(L[k], R[-(k + 2)])
    for k in range(N)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

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

# 先頭から連続する要素の最大公約数の列
L = list(accumulate([0] + A, gcd))
# 末尾から連続する要素の最大公約数
R = list(accumulate([0] + list(reversed(A)), gcd))

# Aの各要素について、それを使用しない場合の最大公約数の最大値をL, Rを用いて求める
ans = max(
    gcd(L[k], R[-(k + 2)])
    for k in range(N)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


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

left = [0]
right = [0]

# 累積GCDを使う

for i in range(N):
    left.append(gcd(left[-1], A[i]))
    right.append(gcd(right[-1], A[N-1-i]))  # Aの後ろからアクセス

right.reverse()

gcd_list = [gcd(left[i], right[i+1]) for i in range(N)]
print(max(gcd_list))

Submission status: Accepted

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


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

left = [0]
right = [0]

for i in range(N):
    left.append(gcd(left[-1], A[i]))
    right.append(gcd(right[-1], A[(N-1)-i]))  # こっちのAは後ろからみる, iがN-1になった時はA[0]


right.reverse()  # indexが小さいほうが多くの数字を考慮した最大公約数になっている


gcd_list = [gcd(left[i], right[i+1]) for i in range(N)]

print(max(gcd_list))

Submission status: Accepted

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


def main():
    N = int(input()) # 5
    A = list(map(int, input().split())) # 12 15 18 24 12

    index = list(range(N))
    L = index.copy()
    # L(0) = 0
    L[0] = 0
    for i in index[:-1]:
        L[i+1] = gcd(L[i], A[i])

    R = index.copy()
    # R(N + 1) = 0
    R.append(0)
    for i in reversed(index):
        R[i] = gcd(R[i+1], A[i])
    
    # print(L) [0, 12, 3, 3, 3]
    # print(R) [3, 3, 6, 12, 12, 0]
    
    # Mi = gcd(L(i), R(i+1))
    M = [gcd(f, b) for f, b in zip(L, R[1:])] # Rはi+1になるように1つずらしている
    # print(M) [3, 6, 3, 3, 3]
    
    print(max(M))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


n, a = II(), LI()
left = [0] * (n+1)
right = [0] * (n+1)

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

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

# print(left)
# print(right)

maxi = -INF

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

print(maxi)

Submission status: Accepted

Solution code:

from fractions import gcd

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

L = [0]
R = [0]

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

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from fractions import gcd

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
gcd_list=[]
reverse_gcd_list = []


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

gcd_list.append(A[0])
reverse_gcd_list.append(A[-1])

for i in range(1,N):
    gcd_list.append(gcd(gcd_list[i-1], A[i]))
    # reverse_gcd_list.insert(0,gcd(reverse_gcd_list[0], A[-1-i]))
    reverse_gcd_list.append(gcd(reverse_gcd_list[-1], A[-1-i]))

reverse_gcd_list.reverse()
num = [gcd_list[-2], reverse_gcd_list[1]]
for i in range(N-2):
    num.append(gcd(gcd_list[i], reverse_gcd_list[i+2]))

print(max(num))

Submission status: Accepted

Solution code:
n = int(input())
v = list(map(int, input().split()))
m = 1
gf = []
gp = []


def gcd(x, y):
    if x < y:
        x += y
        y = x - y
        x -= y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


gf.append(v[0])
for i in range(n-1):
    gf.append(gcd(gf[i], v[i+1]))

gp.append(v[n-1])
for i in range(n-1):
    gp.append(gcd(gp[i], v[n-2-i]))

m = gp[n-2]

for i in range(n-1):
    b = gcd(gf[i], gp[n-3-i])
    if m < b:
        m = b
if m < gf[n-2]:
    m = gf[n-2]

print(m)

Submission status: Accepted

Solution code:
import fractions


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

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

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

# 約数列挙
def divisor(n):
  result = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      result.append(i)
      if i != n // i:
        result.append(n//i)
  return result

# A(intのlist)のうちdで割り切れるものがlen(A)-1個以上あればTrue
def check(A, d):
  count = 0
  for a in A:
    if a % d == 0:
      continue
    count += 1
    if count > 1:
      return False
  return True

for i in sorted(list(set(divisor(A[0])+divisor(A[1]))))[::-1]:
  if check(A, i):
    print(i)
    exit()

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)

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

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

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

Submission status: Accepted

Solution code:
def gcd(a,b):
  if b>a:
    a,b=b,a
  while b:
    a,b=b,a%b
  return a
n = int(input())
a = list(map(int,input().split()))
left = list(range(n-1))
right = list(range(n-1))
left[0]=a[0]
right[0]=a[n-1]
for i in range(1,n-1):
  left[i]=gcd(left[i-1],a[i])
  right[i]=gcd(right[i-1],a[n-i-1])
m=0
for i in range(n):
  if i == 0:
    m=right[n-2]
  elif i == n-1:
    m=max(m,left[n-2])
  else:
    m=max(m,gcd(left[i-1],right[n-i-2]))
print(m)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

results = []
for i in range(N):
    results.append(gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(max(results))

Submission status: Accepted

Solution code:
from fractions import gcd

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

l_gcd_list = [0]
r_gcd_list = [0]
for i in range(N):
    l_gcd_list.append(gcd(l_gcd_list[i], A[i]))
    r_gcd_list.append(gcd(r_gcd_list[i], A[-(i+1)]))
r_gcd_list = r_gcd_list[::-1]
# print(l_gcd_list)
# print(r_gcd_list)

results = []
for i in range(N):
    results.append(gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(max(results))

Submission status: Accepted

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

from fractions import gcd

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

l_gcd_list = [0]
r_gcd_list = [0]
for i in range(N):
    l_gcd_list.append(gcd(l_gcd_list[i], A[i]))
    r_gcd_list.append(gcd(r_gcd_list[i], A[-(i+1)]))
r_gcd_list = r_gcd_list[::-1]
# print(l_gcd_list)
# print(r_gcd_list)

results = []
for i in range(N):
    results.append(gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(max(results))

Submission status: Accepted

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

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

l_gcd_list = [0]*(N+1)
r_gcd_list = [0]*(N+1)
for i in range(N):
    l_gcd_list[i+1] = (gcd(l_gcd_list[i], A[i]))
    r_gcd_list[-(i+2)] = (gcd(r_gcd_list[-(i+1)], A[-(i+1)]))
# print(l_gcd_list)
# print(r_gcd_list)

results = []
for i in range(N):
    results.append(gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(max(results))

Submission status: Accepted

Solution code:
# GCD
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

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

fl=[]
bl=[]

a=l[0]
for x in l:
  a=gcd(a,x)
  fl.append(a)
fl=[0]+fl

l.reverse()
a=l[0]
for x in l:
  a=gcd(a,x)
  bl.append(a)
bl.reverse()
bl=bl+[0]

l2=[]
for i in range(n):
  if fl[i]==0:
    l2.append(bl[i+1])
  elif bl[i+1]==0:
    l2.append(fl[i])
  else:
    l2.append(gcd(fl[i],bl[i+1]))

print(max(l2))

Submission status: Accepted

Solution code:
from fractions import gcd
from sys import exit

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

l_gcd_list = [0]*(N+1)
r_gcd_list = [0]*(N+1)
for i in range(N):
    l_gcd_list[i+1] = (gcd(l_gcd_list[i], A[i]))
    r_gcd_list[-(i+2)] = (gcd(r_gcd_list[-(i+1)], A[-(i+1)]))
# print(l_gcd_list)
# print(r_gcd_list)

results = []
for i in range(N):
    results.append(gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(max(results))

Submission status: Accepted

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

def gcd(m, n):
  while n:
    m, n = n, m%n
  return m

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

Submission status: Accepted

Solution code:
from fractions import gcd
from sys import exit

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

l_gcd_list = [0]
r_gcd_list = [0]
for i in range(N):
    l_gcd_list.append(gcd(l_gcd_list[i], A[i]))
    r_gcd_list.append(gcd(r_gcd_list[i], A[-(i+1)]))
r_gcd_list = r_gcd_list[::-1]
# print(l_gcd_list)
# print(r_gcd_list)

results = []
for i in range(N):
    results.append(gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(max(results))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = [int(s) for s in input().split()]
ans = 0
L = [0] * (N)
R = [0] * (N)
for n in range(0, N):
    if n != N-1:
        L[n+1] = gcd(A[n], L[n])
        R[-(n+2)] = gcd(A[-(n+1)], R[-(n+1)])
for n in range(0, N):
    temp = gcd(L[n], R[n])
    ans = max(temp, ans)
print(ans)