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: Runtime Error

Solution code:
import sys
from functools import reduce
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n
def gcd_list(numbers):
    return reduce(gcd, numbers)

n = int(input())
a = list(map(int, sys.stdin.readline().split()))
c = [gcd_list(a[:i] + a[i+1:]) for i in range(n%10)]
c.sort()
if n == 2:
    print(c[1])
else:
    print(c[2])

Submission status: Runtime Error

Solution code:
import sys
from functools import reduce
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n
def gcd_list(numbers):
    return reduce(gcd, numbers)

n = int(input())
a = list(map(int, sys.stdin.readline().split()))
c = [gcd_list(a[:i] + a[i+1:]) for i in range(n%4)]
c.sort()
if n == 2:
    print(c[1])
else:
    print(c[2])

Submission status: Runtime Error

Solution code:
from math 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-1,-1,-1):
    r[i]=gcd(r[i+1],a[i])
ans=l[-1]
for i in range(n):
    ans=max(ans,gcd(l[i],r[i+1]))
print(ans)

Submission status: Runtime Error

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

n = int(input())
aaa = list(map(int, input().split()))
cnt_l = [0] * (n - 1)
cnt_r = [0] * (n - 1)

cnt_l[0] = aaa[0]
for i in range(1, n - 1):
cnt_l[i] = gcd(cnt_l[i - 1], aaa[i])

aaa.reverse()
cnt_r[0] = aaa[0]
for i in range(1, n - 1):
cnt_r[i] = gcd(cnt_r[i - 1], aaa[i])

cnt_l = [cnt_r[-1]] + cnt_l
cnt_r = [cnt_l[-1]] + cnt_r
cnt_r.reverse()

ans = 0
for i in range(n - 1):
tmp = gcd(cnt_l[i], cnt_r[i])
ans = max(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
import fractions
n=int(input())
a=list(map(int,input().split()))
a.sort()
m=a[-2]
num=2
l=[]
while num<=m:
  lis=[]
  for aa in a:
    if aa%num!=0:
      lis.append(aa)
  if len(lis)==1:
    l.append([num,lis[0]])
  num+=1
l.sort(key=lambda x:x[0],reverse=True)
abn=l[0][1]
a.remove(abn)
g=1
for i in range(n-2):
  g=max(g,fractions.gcd(a[i],a[i+1]))
print(g)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
num=2
while True:
  lis=[]
  for aa in a:
    if aa%num!=0:
      lis.append(aa)
  if len(lis)==1:
    abn=aa
    break
  else:
    num+=1
a.remove(abn)
for i in range(n-2):
  g=max(g,math.gcd(a[i],a[i+1]))
print(g)

Submission status: Runtime Error

Solution code:
from math import gcd

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

# check
A.sort(reverse=True)
max_gcd = A[0]
change = False
for a in A:
    ans = gcd(max_gcd, a)
    if ans < max_gcd and change is False:
        change = True
        continue
    max_gcd = ans

print(max_gcd)

Submission status: Runtime Error

Solution code:
from math import gcd

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

# check
A.sort(reverse=True)
max_gcd = A[0]
change = False
for a in A:
    ans = gcd(ans, a)
    if ans < max_gcd and change is False:
        continue
    max_gcd = ans

print(max_gcd)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if num[0]!=num[1]:
    if any([x%num[2]!=0 for x in data[1::]])==True:
        count=int(num[1]/2)+1
else:
    if any([x%num[2]!=0 for x in data[1::]])==True:
        count=int(num[1]/2)+1
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

Submission status: Runtime Error

Solution code:
import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if num[0]!=num[1]:
    count=num[1]/2+1
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
max=0
for i in range(n-1):
    for j in range(i+1,n):
        if math.gcd(a[i], a[j])>max:
            max=math.gcd(a[i], a[j])
            ci=i
            cj=j
print(max)

Submission status: Runtime Error

Solution code:
from functools import reduce
import math
def GCD(a, b):
    if a * b == 0:
        return a + b
    return math.gcd(a, b)

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

L = [0] * n
R = [0] * n

for i in range(n - 1):
    L[i + 1] = GCD(a[i], L[i])
    R[-(i + 2)] = GCD(a[-(i + 1)], R[-(i + 1)])

M = [0] * n
for i in range(n):
    M[i] = GCD(L[i], R[i])
print(max(M))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math

def main():
    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] = math.gcd(L[i], A[i])
        R[N-1-i] = math.gcd(R[N-i], A[N-1-i])
    ans = 0
    for i in range(N):
        ans = max(ans, math.gcd(L[i], R[i+1]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    # i番目から左の全ての要素のGCD
    gcd_from_left = [None] * N
    gcd_from_left[0] = A[0]
    # i番目から右の全ての要素のGCD
    gcd_from_right = [None] * N
    gcd_from_right[-1] = A[-1]

    for i in range(1, N):
        gcd_from_left[i] = math.gcd(A[i], gcd_from_left[i - 1])

    for i in range(N - 2, -1, -1):
        gcd_from_right[i] = math.gcd(A[i], gcd_from_right[i + 1])

    gcd_from_right.sort()

    # 要素iを取り除いたときの最大公約数
    ans = max(gcd_from_left[-2], gcd_from_right[1])
    for i in range(1, N - 1):
        tmp = math.gcd(gcd_from_right[i + 1], gcd_from_left[i - 1])
        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

DP_first = [0] * N
DP_last = [0] * N

DP_first[0] = A[0]
DP_last[0] = A[-1]

for i in range(1, N):
    DP_first[i] = math.gcd(DP_first[i-1], A[i])
    DP_last[i] = math.gcd(DP_last[i-1], A[-1-i])

ans = max(DP_first[N-2], DP_last[N-2])
for i in range(1, N-1):
    ans = max(ans, math.gcd(DP_first[i-1], DP_last[N-2-i]))
print(ans)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
#隣あうAのgcdのリストを作る
lgcd = []
for i in range(N-1):
  lgcd.append(math.gcd(A[i],A[i+1]))

n1 = lgcd.count(1)

ans = -1
if n1 == 3:
  ans = 1
if n1 == 1 or 2:
  i1 = [i for i,x in enumerate(lgcd) if x == 1]  
  for i in i1:
    for j in range(2):
      resA = A[i+j]
      del A[i+j]
      l = []
      for k in range(N-2):
        l.append(math.gcd(A[k],A[k+1]))
        ans = max(ans,min(l))
      A.insert(i+j,resA)
if n1 == 0:
  m = min(lgcd)
  ind = lgcd.index(m)
  for j in range(2):
    resA = A[ind+j]
    del A[ind+j]
    l = []
    for k in range(N-2):
      l.append(math.gcd(A[k],A[k+1]))
      ans = max(ans,min(l))
    A.insert(ind+j,resA) 

if ans == -1:
  ans = A[0]
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
from math import gcd

def main():
    n = int(input())
    a = sorted(int(i) for i in input().split())
    a0 = a[0]
    if a0 == 1:
        print(reduce(gcd, a[1:]))
        return
    c = []
    for i in range(2, int(a0**0.5) + 1):
        while a0 % i == 0:
            c.append(i)
            a0 //= i
    if a0 != 1:
        c.append(a0)
    d = [0] * len(c)
    for ai in a[1:]:
        for i, ci in enumerate(c):
            if ai % ci == 0:
                ai //= ci
            else:
                d[i] += 1
    e = []
    g = 1
    for k, v in zip(c, d):
        if v == 0:
            g *= k
        elif v == 1:
            e.append(k)
    f = [1] * (n - 1)
    for i, ai in enumerate(a[1:]):
        for ei in e:
            if ai % ei == 0:
                ai //= ei
            else:
                f[i] *= ei
    print(max(g * max(f), reduce(gcd, a[1:])))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
tmp = 0
cnt = 0
n=int(input())
l=list(map(int,input().split()))
if len(l)==2:
    print(math.gcd(l[0],l[1]))
    exit()
else:
    for i in range(n-1):
        for j in range(i+1,n):
            cnt = math.gcd (l[i],l[j]) 
            if tmp < cnt:
                tmp = cnt
print(tmp)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
A = LI()
L = list(accumulate(A, gcd))
R = list(accumulate(reversed(A), gcd))
ans = 0
for i in range(1, n):
    ans = max(ans, gcd(L[i-1], R[i-1]))
ans = max(ans, L[-2])
ans = max(ans, R[-2])
print(ans)

Submission status: Runtime Error

Solution code:
from　fractions import gcd
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)
#print(gcd_l_li)
#print(gcd_r_li)

ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  # かきかえる整数が右端のときと左端のとき
for target in range(1, n-1):
    ans = max(ans, gcd(gcd_l_li[target-1], gcd_r_li[target-1]))
print(ans)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = math.gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = math.gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)
#print(gcd_l_li)
#print(gcd_r_li)

ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  # かきかえる整数が右端のときと左端のとき
for target in range(1, n-1):
    ans = max(ans, math.gcd(gcd_l_li[target-1], gcd_r_li[target-1]))
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math

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

B = [0] * (N - 1)
C = [0] * (N - 1)

for n in range(N - 1):
    if n == 0:
        B[0] = A[0]
        C[N - 2] = A[N - 1]
    else:
        B[n] = math.gcd(B[n - 1], A[n])
        C[N - n - 2] = math.gcd(A[N - n - 1], C[N - n - 1])

ans = 0
for n in range(N):
    if n == 0:
        ans = C[0]
    elif n == N - 1:
        ans = max(ans, B[N - 2])
    else:
        ans = max(ans, math.gcd(B[n - 1], C[n]))
print(ans)

Submission status: Runtime Error

Solution code:
# abc125_c.py
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
A = list(map(int,input().split()))
max_gcd = 0
# print("A : ",A)
for i in range(N-1):
    A_tmp = A[:i]+A[i+1:]
    target = gcd_list(A_tmp)
#    print(target)
    if max_gcd < target:
        max_gcd = target
print(max_gcd)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import math
import operator
from functools import reduce
from itertools import accumulate

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = defaultdict(int)
    for p in primes:
        if x % p == 0:
            n = 0
            while x % p == 0:
                x //= p
                n += 1
            factors[p] = n
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    sl = list(accumulate(A, math.gcd))
    sr = list(reversed(list(accumulate(reversed(A), math.gcd))))
    max_gcd = sl[-1]
    for i in range(N):
        # gcdの単位元は0
        v = 0
        if i > 0:
            v = math.gcd(v, sl[i-1])
        if i < N-1:
            v = math.gcd(v, sr[i+1])
        max_gcd = max(max_gcd, v)
    return max_gcd


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Runtime Error

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]*n
R = [0]*n
def left(i):
    if L[i]:
        return L[i]
    if i < 1:
        return 0
    L[i] = gcd(left(i-1), A[i-1])
    return L[i]
def right(i):
    if R[i]:
        return R[i]
    if i+1 > n-1:
        return 0
    R[i] = gcd(right(i+1), A[i+1])
    return R[i]
ans = 0
for i in range(n):
    g = gcd(left(i), right(i))
    if ans < g:
        ans = g
print(ans)

Submission status: Runtime Error

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()))
def left(i):
    if i < 1:
        return 0
    return gcd(left(i-1), A[i-1])
def right(i):
    if i+1 > n-1:
        return 0
    # ここA[i+1]じゃなくてA[i]
    return gcd(right(i+1), A[i]) 
ans = 0
for i in range(n):
    ans = max(ans, gcd(left(i), right(i)))
print(ans)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(1000000)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
def left(i):
    if i < 1:
        return 0
    return gcd(left(i-1), A[i-1])
def right(i):
    if i+1 > n-1:
        return 0
    return gcd(right(i+1), A[i+1])
ans = 0
for i in range(n):
    ans = max(ans, gcd(left(i), right(i)))
print(ans)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(1000000)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
def left(i):
    if i < 1:
        return 0
    return gcd(left(i-1), A[i-1])
def right(i):
    if i+1 > n-1:
        return 0
    return gcd(right(i+1), A[i+1])
ans = 0
for i in range(n):
    print(i, gcd(left(i), right(i)))
    ans = max(ans, gcd(left(i), right(i)))
print(ans)

Submission status: Runtime Error

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()))
def left(i):
    if i < 1:
        return 0
    return gcd(left(i-1), A[i-1])
def right(i):
    if i+1 > n-1:
        return 0
    return gcd(right(i+1), A[i+1])
ans = 0
for i in range(n):
    ans = max(ans, gcd(left(i), right(i)))
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import math
import copy
from functools import reduce
n = int(input())
a = list(map(int, input().split()))



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

maximum = 0
for i in range(n):
    l = copy.deepcopy(a)
    del l[i:i+1]
    maximum = max(maximum, gcd(l))


print(maximum)

Submission status: Runtime Error

Solution code:
import itertools
import math
import copy
from functools import reduce
n = int(input())
a = list(map(int, input().split()))



def gcd(numbers):
    return reduce(math.gcd, numbers)

maximum = 0
for i in range(n):
    l = copy.deepcopy(a)
    del l[i:i+1]
    maximum = max(maximum, gcd(l))


print(maximum)

Submission status: Runtime Error

Solution code:
C - GCD on Blackboard。
累積和を使ういい問題だが、難しい。

```python

from fractions import gcd

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

left = [0]*n
right = [0]*n

# 取り除く点を除いたGCDの累積
# 引き算できないので、両端から求めてそれぞれのgcdを取る
for i in range(n-1):
    left[i+1] = gcd(left[i], A[i])
    right[n-i-2] = gcd(right[n-i-1], A[n-i-1])

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


```

N**2分の計算量がかかる解法は比較的すぐに思いつく。

Submission status: Runtime Error

Solution code:
from fractions import gcd
n = int(input())
aaa = list(map(int, input().split()))
p = aaa[0]
f = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    f.append(p)
aaa.reverse()
p = aaa[0]
b = [p]
for a in a[1:-1]:
    p = gcd(p, a)
    b.append(p)
f = [b[0]] + f
b = b + [f[-1]]
print(max(gcd(p, q)) for p, q in zip(f, b))

Submission status: Runtime Error

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

L,R=[0]*n,[0]*n
L[0],R[-1]=A[0],A[-1]

from math import gcd

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

ans=max([L[-2],R[1]]+[gcd(L[i-1],R[i+1])for i in range(1,n-1)])
print(ans)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=[int(i) for i in input().split()]

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : math.gcd(x,y), default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
    
tree = SegmentTree(n)
for i in range(n):
    tree.update(i,a[i])

max_=tree.query(1,n)
for i in range(1,n-1):
    max_=max(max_,math.gcd(tree.query(0,i),tree.query(i+1,n)))
max_=max(max_,tree.query(0,n-1))
print(max_)

Submission status: Runtime Error

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

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : gcd(x,y), default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
    
tree = SegmentTree(n)
for i in range(n):
    tree.update(i,a[i])

max_=tree.query(1,n+1)
for i in range(1,n-1):
    max_=max(max_,gcd(tree.query(0,i+1),tree.query(i+1,n+1)))
max_=max(max_,tree.query(0,n))
print(max_)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=[int(i) for i in input().split()]

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : math.gcd(x,y), default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
    
tree = SegmentTree(n)
for i in range(n):
    tree.update(i,a[i])

max_=tree.query(1,n+1)
for i in range(1,n-1):
    max_=max(max_,math.gcd(tree.query(0,i+1),tree.query(i+1,n+1)))
max_=max(max_,tree.query(0,n))
print(max_)

Submission status: Runtime Error

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

"""
7 6 8 
1個除いた最大公約数
A1~A(i-1), Ai+1~ANの最大公約数がわかれば良い
"""
# from math import gcd
from fractions import gcd
import sys
input = sys.stdin.readline
class segmented_tree:
    X_unit = 1 << 30
    # X_f = lambda self, a, b: min(a,b)
    X_f = gcd
    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (2*N)
        
    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x 
        # 後ろから入れていく
        for i in range(self.N-1, 0, -1):
            self.X[i] = self.X_f(self.X[i<<1], self.X[i<<1|1])

    # 1点更新
    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i<<1],self.X[i<<1|1])
    
    # 区間取得
    def fold(self, l, r):
        l += self.N
        r += self.N
        vl = self.X[l]
        vr = self.X[r-1]
        # 外から決めていく
        while l < r:
            # print(l,r)
            if l & 1:
                vl = self.X_f(self.X[l], self.X[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.X_f(self.X[r], self.X[r])
            l >>= 1
            r >>= 1
        return self.X_f(vl,vr)
  
st = segmented_tree(n)
st.build(As)
mx = 0
for i in range(n):
    a = st.fold(0,i)
        
    if i+1 < n:
        b = st.fold(i+1,n)
    else:
        b = a
    if i == 0:
        a = b
    # print("a",a,b)
    mx = max(mx,gcd(a,b))
print(mx)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)

a=int(input())
b=list(map(int,input().split()))
c=[]
for i in range(a):
    for j in range(a):
        if i!=j:
            c.append(gcd(b[i],b[j]))
print(max(set(c)))

Submission status: Runtime Error

Solution code:
import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)

a=int(input())
b=list(map(int,input().split()))
c=[]
for i in range(a):
    for j in range(a):
        if i!=j:
            c.append(gcd(b[i],b[j]))
print(max(set(c)))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
if n <= 2:
    print(max(a))
else:
    gcd_left = [a[0]]
    gcd_right = [a[-1]]
    for i in range(1, n):
        gcd_left.append(math.gcd(a[i], gcd_left[-1]))
        gcd_right.append(math.gcd(a[n-i-1], gcd_right[-1]))
    gcd_right = gcd_right[::-1]
    print(gcd_left, gcd_right)
    ans = max(gcd_left[-2], gcd_right[1])
    for i in range(n-2):
        ans = max(ans, math.gcd(gcd_right[i+2], gcd_left[i]))
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

class segtree():#seg=segtree(A),単位元とsegfuncを指定すること
    def __init__(self,A,ide=0):#単位元とsegfuncを指定すること
        n=len(A)
        num=2**(n-1).bit_length()
        seg=[ide]*(2*num-1)
        segfunc=self.segfunc
        self.ide,self.n,self.num,self.seg = ide, n, num, seg
        for i in range(n): seg[i+num-1]=A[i]#setvalue
        for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])#build
            
    def segfunc(self,x,y):return math.gcd(x,y) #seg木の基本関数
        
    def update(self,k,x):#Aのk番目の要素をxに置き換える,計算量log(N)
        k += self.num-1
        seg,segfunc=self.seg,self.segfunc
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
    def query(self,p,q):#区間[p,q)の累積segfuncを求める,計算量log(N)
        if q<=p: return self.ide
        num,segfunc,seg=self.num,self.segfunc,self.seg
        p += num-1; q += num-2
        res=self.ide
        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,q = p//2, (q-1)//2
        if p == q: res = segfunc(res,seg[p])
        else: res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    seg=segtree(A)
    ans=1
    for i in range(N):
        seg.update(i,0)
        ans=max(ans,seg.query(0,N))
        seg.update(i,A[i])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from itertools as f;from fractions import*;c=lambda l:list(f.accumulate([0]+l,gcd));_,a=open(0);*a,=map(int,a.split());print(max(gcd(s,t)for s,t in zip(c(a),c(a[::-1])[-2::-1])))

Submission status: Runtime Error

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

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

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

MAX =0
for i in range(n):
    if i == 0:
        MAX =max(MAX, c[-1])
    elif i ==n-1:
        MAX =max(MAX, b[-1])
    else:
        MAX =max(MAX, gcd(b[i-1], c[n-i-2]))
print(MAX)

Submission status: Runtime Error

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

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

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

MAX =0
for i in range(n):
    if i == 0:
        MAX =max(MAX, c[-1])
    elif i ==n-1:
        MAX =max(MAX, b[-1])
    else:
        MAX =max(MAX, gcd(b[i-1], c[n-i-2]))

print(MAX)

Submission status: Runtime Error

Solution code:
import copy

from fraction import gcd
from functools import reduce

def gcdli(xl):
    #xlはlist
    return reduce(gcd , xl)

def gcd_on_blackboard(n, ali):

    ans = 0

    for i in range(n):
        count = copy.copy(ali)
        count.pop(i)
        ans = max(ans, gcdli(count))

    return ans

def main():
    n = int(input())
    ali = list(map(int, input().split()))
    print(gcd_on_blackboard(n, ali))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import copy

from math import gcd
from functools import reduce

def gcdli(xl):
    #xlはlist
    return reduce(gcd , xl)

def gcd_on_blackboard(n, ali):

    ans = 0

    for i in range(n):
        count = copy.copy(ali)
        count.pop(i)
        ans = max(ans, gcdli(count))

    return ans

def main():
    n = int(input())
    ali = list(map(int, input().split()))
    print(gcd_on_blackboard(n, ali))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
L = [A[0]]
R = [A[-1]]

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

print(ans)