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: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    m = min(A)
    L = []
    for a in A:
        b = m
        while True:
            r = a % b
            if r == 0:
                L.append(b)
                break
            a = b
            b = r
    L.pop(L.index(min(L)))
    print(min(L))


main()

Submission status: Wrong Answer

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

import fractions

if N == 2:
    print(fractions.gcd(A[0],A[1]))
    exit()
    
ans = []
for i in range(N):
    a = A[:i] + A[i+1:]
    print(a)
    for j in range(1,N-1):
        if j == 1:
            g = fractions.gcd(a[0],a[j])
        else:
            g = fractions.gcd(g,a[j])
    ans.append(g)

print(max(ans))

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd

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

for i in a:
    b = sorted(a)
    print(a, b)
    b.remove(i)
    ans.append(reduce(gcd, b))

print(max(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
divs = make_divisors(a[0]) #list
#print(divs)
divsTF = [0]*len(divs)
for i in range(len(divs)):
    j = [1 if a[j] % divs[i] else 0 for j in range(n) ]
    #print(divs[i],j)
    if sum(j) <= 1:
        divsTF[i] = 1
#print(divsTF)
ans = 1
for i in range(len(divs)):
    if divsTF[i] == 1:
        ans = max(ans,divs[i])
print(ans)

Submission status: Wrong Answer

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


n = int(input())
a_lst = list(map(int,input().split()))
cnt = 0
ans = gcd(max(a_lst),min(a_lst))

for a in a_lst:
    if a%ans != 0:
        if cnt > 1:
            print(1)
            exit()
        else:
            cnt += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#coding: utf-8
from fractions import gcd
#from math import gcd
N = int(input())
A = list(map(int, input().split()))
l = []
for i in range(N-1):
    l.append(gcd(A[i], A[i+1]))
l.append(gcd(A[0], A[-1]))
l = list(set(l))
l.sort()
print(l[1] if len(l) > 1 else l[0])

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
def gcdline(A):
    q = A[0]
    n = len(A)
    for i in range(n):
        q = gcd(q,A[i])
    return q

a.sort()
now = gcdline(a)
q = now
for i in range(n):
    if q > gcd(now,i):
        q = i
b = []
for i in range(n):
    if i == q:
        continue
    b.append(a[i])

print(gcdline(b))

Submission status: Wrong Answer

Solution code:
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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

N = I()
A = IL()

num = A[0]
for i in range(1,N):
    if A[i]%num == 0:
        continue
    else:
        num = gcd(num,A[i])

k = 1
while A[0]>=num*k:
    cnt = 0
    k += 1
    for i in range(N):
        if A[i]%(num*k) == 0:
            continue
        else:
            cnt += 1
        if cnt == 2:
            break
    else:
        continue
    break

print(num*(k-1))

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
  if a < b:
    a, b = b, a
  if b == 0:
    return a
  c = a % b
  return gcd(b, c)
  
n=int(input())
a=list(map(int,input().split()))
g1=[0 for i in range(n)]
g2=[0 for i in range(n)]
g1[0]=a[0]
g2[n-1]=a[n-1]
for i in range(1,n-1):
  g1[i]=gcd(g1[i-1],a[i])
for i in range(n-2,0,-1):
  g2[n-1-i]=gcd(g2[i+1],a[n-1-i])
ans=1
for i in range(n-2):
  a=gcd(g1[i],g2[i+2])
  ans=max(ans,a)
ans=max(ans,g1[n-2],g2[1])
print(ans)

Submission status: Wrong Answer

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

# ユークリッドの互除法
# 二つの数の最大公約数を求める
# A - (B * N) = C
# B - (C * N) = D ･･･

def sinGCD(a, b):
    if b == 0:
        return a

    # 再帰
    return sinGCD(b, a % b)

def listGCD(listA):
    lenList = len(listA)
    ans = 0
    for i in range(lenList - 1):
        for j in range(i + 1, lenList):
            ans = max(ans, sinGCD(A[i], A[j]))
    return ans

print(listGCD(A))

Submission status: Wrong Answer

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

    # divisors.sort()
    return divisors

n=int(input())
a={int(i) for i in input().split()}
d={}
for i,j in enumerate(a):
    t=div(j)
    for k in t:
        if k in d and d[k]+1>=i:
            d[k]+=1
        elif i==0:
            d[k]=1
ans=1
for i in d:
    if d[i]+1>=n:
        ans=max(ans,i)
print(ans)

Submission status: Wrong Answer

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

num = min(A)
i = 0
while num > 0:
    tmp = [x for x in A if x % num == 0]
    if len(tmp) > 1:
        print(num)
        break
    else:
        num -= 1

Submission status: Wrong Answer

Solution code:
from functools import reduce
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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


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

ans = max(reduce(gcd, A[2:], A[0]), reduce(gcd, A[1:]))
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
g = A[0]
mini_index_1 = 0
mini_index_2 = 0
for i in range(N):
    ng = gcd(g, A[i])
    if ng < g:
        mini_index_1 = i
        mini_index_2 = i-1
        g = ng
# print(mini_index_1)

ans1 = 0
ans2 = 0
for i in range(N):
    if mini_index_1 != i:
        if ans1 == 0:
            ans1 = A[i]
        else:
            ans1 = gcd(ans1, A[i])
for i in range(N):
    if mini_index_2 != i:
        if ans2 == 0:
            ans2 = A[i]
        else:
            ans2 = gcd(ans2, A[i])

print(max(ans1, ans2))

Submission status: Wrong Answer

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

while 1:
    m = min(A)
    nA = [m] + [a%m for a in A if a%m >0]
    if len(nA) == 1:
        A.pop(A.index(m))
        break
    else:
        A = nA

while 1:
    m = min(A)
    A = [m] + [a%m for a in A if a%m >0]
    if len(A) == 1:
        break
print(A[0])

Submission status: Wrong Answer

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

this_gcd = max(a)
gcd_list = []

for i in a:
    this_gcd = fractions.gcd(this_gcd, i)

for I in range(len(a)):
    i = a[I]
    tmp = i // this_gcd
    key = 1
    for j in range(2, int(math.sqrt(tmp)) + 1):
        if tmp % j == 0:
            key = 0

    if key:
        del a[I]
        break

this_gcd = max(a)
for i in a:
    this_gcd = fractions.gcd(this_gcd, i)

print(this_gcd)

Submission status: Wrong Answer

Solution code:
from functools import reduce
read = input
n = int(read())
A = list(map(int, read().split()))
def gcd(a, b):
#     print(a,b)
    if a > b:
        a,b = b,a
    return a if b %a ==0 else gcd(b%a, a)
def cal(ac, x):
    if len(ac) == 0:
        ac.append(x)
        return ac
    nxt = gcd(ac[-1], x)
    ac.append(nxt)
    return ac
A1 = list(reduce(cal, A, []))
A.reverse()
A2 = list(reduce(cal, A, []))
A.reverse()
mx = 1
for i in range(n):
    if i == 0:
        mx =max(A2[ 1 ], mx)
        continue
    if i == n-1:
        mx = max(A1[ n-1 ], mx)
        continue
    nxt = gcd(A[i-1], A[i+1])
    mx = max(nxt, mx)
print(mx)

Submission status: Wrong Answer

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

def gcd(a, b): # 最大公約数
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a % b
    return a
g0 = reduce(gcd,A[1:])

now = A[0]

id = 0
for i in range(1,N):
    ne = gcd(now,A[i])
    if ne < now:
        id = i
        now = ne
A.pop(id)

g = reduce(gcd,A)
print(max(g,g0))

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

lowest = 0
g1 = As[0]
for i in range(1, N):
    new_g = gcd(As[i], g1)
    if new_g != g1:
        lowest = i
    g1 = new_g

g2 = As[0]
for i in range(1, N):
    if i == lowest:
        continue
    g2 = gcd(As[i], g2)

g3 = As[1]
for i in range(2, N):
    g3 = gcd(As[i], g3)

print(max(g2, g3))

Submission status: Wrong Answer

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

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


n = int(input())

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


g = []

for i in range(n):
    for j in range(i+1, n):
        g.append(gcd(a[i], a[j]))


print(max(g))

Submission status: Wrong Answer

Solution code:
import math

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

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

P = [1,M]
for k in range(2,math.ceil(math.sqrt(M))+1):
    if M % k == 0:
        P.append(k)
        P.append(M//k)
ans = 1
for p in P:
    t = 0
    for k in range(N):
        if A[k]%p != 0:
            t += 1
        if t == 2:
            break
    if t <= 1:
        ans = max(ans,p)

print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd


def mygcd(enum):
    if len(enum) == 1:
        return enum[0]
    ret = 0
    for i in range(len(enum)-1):
        if i == 0:
            ret = gcd(enum[0], enum[1])
        else:
            ret = gcd(ret, enum[i])
    return ret


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

ans = 0
for i in range(n):
    li1 = a[0:i]
    li2 = a[i+1:]
    po = gcd(mygcd(li1), mygcd(li2))
    if ans < po:
        ans = po

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

import fractions
import copy
from functools import reduce

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

max_gcd = 0
for idx in range(N):
    
    if idx == 0:
        cleaned = copy.copy(A_list)
        del cleaned[idx]
        gcd_value = gcd(tuple(cleaned))
        if max_gcd < gcd_value:
            max_gcd = gcd_value
    else:
        former_target = A_list[idx-1]
        if former_target % gcd_value == 0:
            cleaned = copy.copy(A_list)
            del cleaned[idx]
            gcd_value = gcd(tuple(cleaned))
            if max_gcd < gcd_value:
                max_gcd = gcd_value
        else:
            continue
        
print(max_gcd)

Submission status: Wrong Answer

Solution code:
#coding: utf-8
from fractions import gcd
#from math import gcd
N = int(input())
A = list(map(int, input().split()))
l = []
for i in range(N-1):
    l.append(gcd(A[i], A[i+1]))
l.append(gcd(A[0], A[-1]))
l.sort()
l = list(set(l))
print(l[1] if len(l) > 1 else l[0])

Submission status: Wrong Answer

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

N = int(input())
A = [i for i in map(int,input().split())]
g = gcd(max(A),min(A))
print(g)

Submission status: Wrong Answer

Solution code:
import functools
import fractions
N = int(input())
A = [int(x) for x in input().split()]
GCD = functools.reduce(fractions.gcd, A)
B = sorted([a // GCD for a in A])
gcd = B[0]
cancel = 1
for b in B[1:]:
  _gcd = fractions.gcd(gcd, b)
  if _gcd == 1 and cancel == 1:
    _gcd = gcd
    cancel = 0
  gcd = _gcd
print(GCD * gcd)

Submission status: Wrong Answer

Solution code:
def main():
    input = sys.stdin.readline
    try:
        n = int(input())
        a = list(map(int, input().split()))
        if n == 2:
            print(max(a))
        else:
            import fractions, itertools
            print(max(fractions.gcd(a[i[0]], a[i[1]]) for i in itertools.permutations(range(n), n - 1)))

    finally:
        input = None

import sys; sys.setrecursionlimit(50000)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

bad_id = 0
max_div = 0
for j in range(3):
    bid = bad_id
    init = False
    for i, item in enumerate(a):
        if i == bid:
            continue
        if not init:
            val = item
            div = val
            init = True
        else:
            val = gcd(div, item)
            if val != div:
                bad_id = i
                div = val
    max_div = max(div, max_div)
    
print(max_div)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

def input_ints():
    return list(map(int, input().split()))

def main():
    n = int(input())
    a = input_ints()
    x = [a[0]]
    y = [a[-1]]
    for i in range(n-1):
        x.append(gcd(x[-1], a[i + 1]))
        y.append(gcd(y[-1], a[n - i - 2]))
    ans = max(x[-2],y[-2])
    for i in range(1, n-1):
        ans = max(ans,gcd(x[i-1],y[-i-1]))
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
ma = min(A)
for i in range(ma):
    tof = [a%ma==0 for a in A]
    if sum(tof)>=N-1:
        print(ma)
        break
    ma -= 1

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        now = gcd(A[i], A[j])
        if now > ans :
            ans = now
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
SA = [A[i] - A[i-1] for i in range(1, N)]
SA.append(A[N-1] - A[0])
ans = 0
for i in range(N):
    X = SA[:]
    X.pop(i)
    M = max(X)
    if M >= ans:
        ans = M
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

ans = 0

for i in range(N):
    tmp = A[:i] + A[i + 1:]
    g = 0
    for j in range(N - 2):
        g = max(g, gcd(tmp[j], tmp[j + 1]))
    ans = max(g, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys


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


def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A)

    if N == 2:
        return A[1]

    a0 = A[0]
    a1 = A[1]

    gcd0 = 10**5
    gcd1 = 10**5
    for i in range(2, N):
        a = A[i]
        gcd0 = min(gcd0, gcd(a0, a))
        gcd1 = min(gcd1, gcd(a1, a))

    return max(gcd0, gcd1)


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

while 1:
    m = min(A)
    nA = [m] + [a%m for a in A if a%m >0]
    if len(nA) == 1:
        A.pop(A.index(m))
        break
    else:
        A = nA

while 1:
    m = min(A)
    A = [m] + [a%m for a in A if a%m >0]
    if len(nA) == 1:
        break
print(A[0])

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

if len(a) == 1:
    print(a[0])
elif len(a) == 2:
    print(max(a))
else:
    v = a[0]
    gcds = sorted([gcd(d, v) for d in a[1:]])
    g1 = gcds[1]
    
    v = a[1]
    gcds = sorted([gcd(d, v) for d in [a[0]] + a[2:]])
    g2 = gcds[1]
    
    print(max([g1, g2]))

Submission status: Wrong Answer

Solution code:
def main():
    input = sys.stdin.readline
    try:
        n = int(input())
        a = list(map(int, input().split()))
        import fractions, itertools
        print(max(fractions.gcd(a[i[0]], a[i[1]]) for i in itertools.permutations(range(n), 2)))

    finally:
        input = None

import sys; sys.setrecursionlimit(50000)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

res = set()
for i in range(N):
  for j in range(i+1, N):
    res.add(gcd(A[i], A[j]))
print(max(res))

Submission status: Wrong Answer

Solution code:
from sys import exit
def gcd(a,b):#greatest common divisor
    if (a<b):
        a,b = b,a
    while(b>0):
        a,b = b ,a%b
    return a
N = int(input())
A = [int(n) for n in input().split()]
maxg = 0
for i in range(1,N):
    maxg = max(gcd(A[0],A[i]), maxg)
for i in range(N-2,-1,-1):
    maxg = max(gcd(A[-1],A[i]), maxg)
print(maxg)

# a = [int(input()) for _ in range(N)]
# S = str(input())
# L = len(S)
# T = str(input())
# exit()

Submission status: Wrong Answer

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


def mygcd(enum):
    if len(enum) == 1:
        return enum[0]
    ret = 0
    for i in range(len(enum)-1):
        if i == 0:
            ret = gcd(enum[0], enum[1])
        else:
            ret = gcd(ret, enum[i])
    return ret


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

ans = 0
for i in range(n):
    li1 = a[0:i]
    li2 = a[i+1:]
    po = gcd(mygcd(li1), mygcd(li2))
    if ans < po:
        ans = po

print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

ans = 0
if len(A) > 2 and all(x % A[1] == 0 for x in A[2:]):
    ans = A[1]
    print(ans)
else:
    cand = [x for x in range(1, A[0]+1) if A[0] % x == 0]
    for x in reversed(cand):
        ng = 0
        ok = True
        for a in A[1:]:
            if a % x == 0:
                continue
            else:
                if ng == 0:
                    ng = 1
                else:
                    ok = False
        if ok:
            print(x)
            exit()

Submission status: Wrong Answer

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


if n <= 2:
    print(max(a))
else:
    a.sort()
    print(max(gcd(a[0], a[-1]), gcd(a[1], a[-1])))

Submission status: Wrong Answer

Solution code:
from functools import reduce

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

N = int(input())
xs = [int(x) for x in input().split()]
argmax_i = 0
max_gcd = 1

for i in range(len(xs) - 1):
    ys = xs[:i] + xs[i + 1:]
    # print(ys)
    x = reduce(gcd, ys, 0)
    # print(x)
    if x > max_gcd:
        max_gcd = x
        argmax_i = i

xs[argmax_i] = max_gcd
print(reduce(gcd, xs, 0))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import fractions


N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

max_gcd_num = 1

for i in range(N):
    for j in range(i+1, N):
        max_gcd_num = max(max_gcd_num, fractions.gcd(A[i], A[j]))

print(max_gcd_num)

Submission status: Wrong Answer

Solution code:
import sys

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

if N == 2:
    print(max(A))
    sys.exit()

for i in range(N):
    L = A[:i]+A[i+1:]
    for j in range(N-2):
    # 割り算 余りを次の割る数に
    # A[i]がゼロになったら終了!
        while L[j]>0:
            tmp = L[j]
            L[j] = L[j+1] % L[j]
            L[j+1] = tmp
        ans = max(ans,L[N-2])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
c = [ int(e) for e in input().split(" ")]

print("1")

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : 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

import math

n = int(input())
seg = SegmentTree(n, math.gcd)

A = list(map(int,input().split()))
for i in range(n):
    seg.update(i, A[i])

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    if N == 2:
        print(max(A[0], A[1]))
        exit()
    max_gcd = 0
    for i in range(N):
        nums = []
        for j in range(N):
            if i==j:
                continue 
            nums.append(A[j])
        max_gcd = max(max_gcd, gcd(*nums))
    print(max_gcd)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce

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

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

B = [None for _ in range(N)]

for i in range(N):
   store = A[i]
   del A[i]
   B[i] = [a for a in A]
   A.insert(i, store)

ans = [None for _ in range(N)]

for i in range(N):
   ans[i] = gcd_list(B[i])

print(max(ans))

Submission status: Time Limit Exceeded

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

ans = 1
for i in range(N):
    g = reduce(math.gcd,A[:i]+A[i+1:])
    ans = max(ans,g)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

class SegmentTree:
    """Segment Tree

    Attributes:
        n (int):       要素数
        num (int):     n以上の最小の2の累乗
        ide_ele (int): 単位元
            - RmQ(Range Minimum Query): inf
            - RMQ(Range Maximum Query): -1
            - RSQ(Range Sum Query):     0
            - RPQ(Range Product Query): 1
            - RGQ(Range GCD Query):     0
        seg (list):    要素の格納先
    """
    def __init__(self, a):
        """初期化 O(N)
        
        Args:
            a (list): 対象の配列
        """
        self.n = len(a)
        self.num = 2 ** (self.n - 1).bit_length()
        self.ide_ele = 0
        self.seg = [self.ide_ele] * (2*self.num-1)

        for i in range(self.n):
            self.seg[self.num+i-1] = a[i]    
        for i in range(self.num-2, -1, -1) :
            self.seg[i] = self.st_func(self.seg[2*i+1], self.seg[2*i+2])

    def query(self, a, b, k=0, l=0, r=-1):
        """区間クエリの計算 O(logN)

        Args:
            l (int): 区間の左端
            r (int): 区間の右端
        
        Returns:
            int: [l, r)についての区間クエリ
        """
        if r < 0:
            r = self.num
        
        if r <= a or b <= l:
            return self.ide_ele
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, 2*k+1, l, (l+r)//2)
            vr = self.query(a, b, 2*k+2, (l+r)//2, r)
            return self.st_func(vl, vr)
        """
        if r <= l:
            return self.ide_ele
        
        l += self.num - 1
        r += self.num - 2
        res = self.ide_ele

        while r - l > 1:
            if l % 2 == 0:
                res = self.st_func(res, self.seg[l])
            if r % 2 == 1:
                res = self.st_func(res, self.seg[r])
                r -= 1
            l = l // 2
            r = (r - 1) // 2
        
        if l == r:
            res = self.st_func(res, self.seg[l])
        else:
            res = self.st_func(res, self.st_func(self.seg[l], self.seg[r]))
        
        return res
        """

    def update(self, i, v):
        """値の更新 O(logN)

        Args:
            i (int): 更新対象のindex
            v (int): 更新値
        """
        i += self.num - 1
        self.seg[i] = v
        while i > 0:
            i = (i - 1) // 2
            self.seg[i] = self.st_func(self.seg[i*2+1], self.seg[i*2+2])
    
    def st_func(self, x, y):
        """問題に応じた処理

        Returns:
            int: 問題に応じた値
                - RmQ(Range Minimum Query): min(x, y)
                - RMQ(Range Maximum Query): max(x, y)
                - RSQ(Range Sum Query):     x + y
                - RPQ(Range Product Query): x * y
                - RGQ(Range GCD Query):     gcd(x, y)
        """
        return gcd(x, y)


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

st = SegmentTree(a)

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

class SegmentTree:
    """Segment Tree

    Attributes:
        n (int):       要素数
        num (int):     n以上の最小の2の累乗
        ide_ele (int): 単位元
            - RmQ(Range Minimum Query): inf
            - RMQ(Range Maximum Query): -1
            - RSQ(Range Sum Query):     0
            - RPQ(Range Product Query): 1
            - RGQ(Range GCD Query):     0
        seg (list):    要素の格納先
    """
    def __init__(self, a):
        """初期化 O(N)
        
        Args:
            a (list): 対象の配列
        """
        self.n = len(a)
        self.num = 2 ** (self.n - 1).bit_length()
        self.ide_ele = 0
        self.seg = [self.ide_ele] * (2*self.num-1)

        for i in range(self.n):
            self.seg[self.num+i-1] = a[i]    
        for i in range(self.num-2, -1, -1) :
            self.seg[i] = self.st_func(self.seg[2*i+1], self.seg[2*i+2])

    def query(self, a, b, k=0, l=0, r=-1):
        """区間クエリの計算 O(logN)

        Args:
            l (int): 区間の左端
            r (int): 区間の右端
        
        Returns:
            int: [l, r)についての区間クエリ
        """
        if r < 0:
            r = self.num
        
        if r <= a or b <= l:
            return self.ide_ele
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, 2*k+1, l, (l+r)//2)
            vr = self.query(a, b, 2*k+2, (l+r)//2, r)
            return self.st_func(vl, vr)
        """
        if r <= l:
            return self.ide_ele
        
        l += self.num - 1
        r += self.num - 2
        res = self.ide_ele

        while r - l > 1:
            if l % 2 == 0:
                res = self.st_func(res, self.seg[l])
            if r % 2 == 1:
                res = self.st_func(res, self.seg[r])
                r -= 1
            l = l // 2
            r = (r - 1) // 2
        
        if l == r:
            res = self.st_func(res, self.seg[l])
        else:
            res = self.st_func(res, self.st_func(self.seg[l], self.seg[r]))
        
        return res
        """

    def update(self, i, v):
        """値の更新 O(logN)

        Args:
            i (int): 更新対象のindex
            v (int): 更新値
        """
        i += self.num - 1
        self.seg[i] = v
        while i > 0:
            i = (i - 1) // 2
            self.seg[i] = self.st_func(self.seg[i*2+1], self.seg[i*2+2])
    
    def st_func(self, x, y):
        """問題に応じた処理

        Returns:
            int: 問題に応じた値
                - RmQ(Range Minimum Query): min(x, y)
                - RMQ(Range Maximum Query): max(x, y)
                - RSQ(Range Sum Query):     x + y
                - RPQ(Range Product Query): x * y
                - RGQ(Range GCD Query):     gcd(x, y)
        """
        return gcd(x, y)


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

st = SegmentTree(a)

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

# segfunc: 問題に応じて設定
def segfunc(x, y):
    return gcd(x, y)


# 配列aで初期化
def init(a):
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2]) 


# a[k]の値をxに更新
def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k*2+1], seg[k*2+2])


# [p, q)についてsegfuncを適用したものを返す
def query(p, q):
    if q <= p:
        return ide_ele
    
    p += num - 1
    q += num - 2
    res = ide_ele

    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(res, segfunc(seg[p], seg[q]))
    
    return res


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

ide_ele = 0
num = 2 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def init(a):
    for i in range(n):
        seg[num+i-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = st_func(seg[2*i+1], seg[2*i+2])

def query(l, r):
    if r <= l:
        return ide_ele
    
    l += num - 1
    r += num - 2
    res = ide_ele

    while r - l > 1:
        if l % 2 == 0:
            res = st_func(res, seg[l])
        if r % 2 == 1:
            res = st_func(res, seg[r])
            r -= 1
        l = l // 2
        r = (r - 1) // 2
    
    if l == r:
        res = st_func(res, seg[l])
    else:
        res = st_func(res, st_func(seg[l], seg[r]))
    
    return res

def update(i, v):
    i += num - 1
    seg[i] = v
    while i > 0:
        i = (i - 1) // 2
        seg[i] = st_func(seg[i*2+1], seg[i*2+2])

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


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

num = 2 ** (n - 1).bit_length()
ide_ele = 0
seg = [ide_ele] * (2*num-1)

init(a)

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

print(res)