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: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import copy

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

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

ans_list = []
for i in range(n):
    tmp_list = copy.copy(a_list)
    if i == 0:
        tmp = gcd(*tmp_list[1:])
    
    elif i == n-1:
        tmp = gcd(*tmp_list[:-1])
    
    else:
        tmp_l = gcd(*tmp_list[0:i])
        tmp_r = gcd(*tmp_list[i+1:])
        tmp = gcd(tmp_l, tmp_r)
    
    ans_list.append(tmp)

print(max(ans_list))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

res = 0
for i in range(N):
    tmp = A[i+1:] + A[:i]
    ans = tmp[0]
    for i in range(1,N-1):
        ans = gcd(ans,tmp[i])
    if(res < ans):
        res = ans
print(res)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

res = 0
for i in range(N):
    tmp = A[i+1:] + A[:i]
    ans = tmp[0]
    #print(tmp)
    for i in range(1,N-1):
        ans = gcd(ans,tmp[i])
    if(res < ans):
        res = ans
    #print(ans)
print(res)

Submission status: Time Limit Exceeded

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


class SEGMENT_TREE:
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (2 * N)  # 問題により修正

    def init(self, arr):
        N = self.N
        for i in range(N):
            self.tree[N + i] = arr[i]
        for i in range(N - 1, 0, -1):
            self.tree[i] = gcd(
                self.tree[i * 2], self.tree[i * 2 + 1])  # 問題により修正

    def update(self, p, value):
        i = p + self.N
        self.tree[i] = value
        while i > 1:
            self.tree[i >> 1] = gcd(self.tree[i], self.tree[i ^ 1])  # 問題により修正
            i >>= 1

    def query(self, l, r):
        N = self.N
        res = 0  # 問題により修正
        l += N
        r += N
        while l < r:
            if (l & 1):
                res = gcd(res, self.tree[l])  # 問題により修正
                l += 1
            if (r & 1):
                r -= 1
                res = gcd(res, self.tree[r])  # 問題により修正
            l >>= 1
            r >>= 1
        return res


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    seg = SEGMENT_TREE(N)
    seg.init(A)
    ans = 0
    for i, a in enumerate(A):
        seg.update(i, 0)
        ans = max(ans, seg.query(0, N))
        seg.update(i, a)

    print(ans)

Submission status: Time Limit Exceeded

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


class SEGMENT_TREE:
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (2 * N)  # 問題により修正

    def init(self, arr):
        N = self.N
        for i in range(N):
            self.tree[N + i] = arr[i]
        for i in range(N - 1, 0, -1):
            self.tree[i] = gcd(
                self.tree[i * 2], self.tree[i * 2 + 1])  # 問題により修正

    def update(self, p, value):
        i = p + self.N
        self.tree[i] = value
        while i > 1:
            self.tree[i // 2] = gcd(self.tree[i], self.tree[i ^ 1])  # 問題により修正
            i //= 2

    def query(self, l, r):
        N = self.N
        res = 0  # 問題により修正
        l += N
        r += N
        while l < r:
            if (l & 1):
                res = gcd(res, self.tree[l])  # 問題により修正
                l += 1
            if (r & 1):
                r -= 1
                res = gcd(res, self.tree[r])  # 問題により修正
            l //= 2
            r //= 2
        return res


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    seg = SEGMENT_TREE(N)
    seg.init(A)
    ans = 0
    for i in range(N):
        tmp = gcd(seg.query(0, i), seg.query(i + 1, N))
        ans = max(ans, tmp)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

N = int(input())
a = list(map(int,input().split()))
from fractions import gcd
seg = SegmentTree(N , gcd , 0)
for i in range(N):
    seg.assign(i , a[i])
seg.build()
ans = 1
for i in range(N):
    ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N=int(input())
a=list(map(int,input().split()))
def gcd(li):
  ans=li[0]
  for i in range(len(li)):
    ans=fractions.gcd(ans,li[i])
  return ans
c=a[:]
c.pop(0)
p=gcd(c)
for i in range(N):
  b=a[:]
  b.pop(i)
  p=max(p,gcd(b))
print(p)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree(object):
    def __init__(self, size, op, id):
        s = 1
        while s < size:
            s *= 2
        self.num_leaves = s
        self.nodes = [id]*(2*s-1)
        self.op = op
        self.id = id
    def update(self, i, x):
        i += self.num_leaves - 1
        self.nodes[i] = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = self.op(self.nodes[2*i+1], self.nodes[2*i+2])
    def query(self, l, r):
        l += self.num_leaves-1
        r += self.num_leaves-1
        res = self.id
        while l < r:
            if l&1==0:
                res = self.op(res, self.nodes[l])
            if r&1==0:
                r -= 1
                res = self.op(res, self.nodes[r])
            l >>= 1
            r >>= 1
        return res
INF = -float("inf")
def gcd(x,y):
    if x == INF:
        return y
    if y == INF:
        return x
    if x<y:
        x,y = y,x
    r = (x%y)
    while r:
        x,y = y, r
        r = (x%y)
    return y
    
N = int(input())
A = list(map(int,input().split()))
seg = SegmentTree(N, gcd, INF)
for i in range(N):
    seg.update(i, A[i])
ans = INF
for i in range(N):
    ans = max(gcd(seg.query(0,i), seg.query(i+1, N)), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

#累積GCD
left = [0]
right = [0]
for i in range(n):
    left.append(fractions.gcd(left[i],a[i]))
    right.insert(0,fractions.gcd(right[0],a[n - 1 - i]))

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

Submission status: Time Limit Exceeded

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter
    from functools import lru_cache
    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    A = list(map(int, input().split()))
    @lru_cache(maxsize=None)
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    if len(A) == 2:
        print(max(A))
        exit()
    res = 0
    for i in range(N):
        arr = A[:i] + A[i+1:]
        res = max(res, gcd_group(arr))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    A = list(map(int, input().split()))
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    if len(A) == 2:
        print(max(A))
        exit()
    res = 0
    for i in range(N):
        arr = A[:i] + A[i+1:]
        res = max(res, gcd_group(arr))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

mx = 0
for i in range(n):
    popped = a.pop(i)
    g = a[0]
    for aa in a[1:]:
        g = fractions.gcd(g, aa)
    a.insert(i, popped)
    mx = max(mx, g)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import functools

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

def gcd(nums):
    return functools.reduce(euclid, nums)

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

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

p = []

for i in range(N):
    if i == 0:
        p.append(R[N-2])
    elif i == N-1:
        p.append(L[N-2])
    else:
        p.append( gcd([L[i-1], R[N-2-i]]) )

print(max(p))

Submission status: Time Limit Exceeded

Solution code:
import functools

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

def gcd(nums):
    return functools.reduce(euclid, nums)

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

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

p = []

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

print(max(p))

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import copy
from fractions import gcd


# import math
# import numpy as np
# from collections import Counter, deque
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
import sys
sys.setrecursionlimit(10**9)


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

    # A[0:i]の最大公約数
    def L(i):
        if i == 0:
            return 0
        return gcd(L(i - 1), A[i - 1])

    # A[i:]の最大公約数
    def R(i):
        if i == N:
            return 0
        return gcd(R(i + 1), A[i])

    maxgcd = 0
    for i in range(N):
        maxgcd = max(maxgcd, gcd(L(i), R(i + 1)))

    print(maxgcd)


resolve()

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import copy
from fractions import gcd
# import math
# import numpy as np
# from collections import Counter, deque
from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

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


    maxgcd=0
    for i in range(N):
        maxgcd=max(maxgcd,reduce(gcd,A[:i]+A[i+1:]))

    print(maxgcd)


resolve()

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import copy
import fractions
# import math
# import numpy as np
# from collections import Counter, deque
from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

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

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

    maxgcd=0
    for i in range(N):
        maxgcd=max(maxgcd,gcd(*(A[:i]+A[i+1:])))

    print(maxgcd)


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """
    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
    # k番目 の値を x に更新
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2
    # 区間[l,r]をopでまとめる
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0 + 1
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    def get(self, k):  # k番目の値を取得。query[k,k]と同じ
        return self.tree[k+self.N0]

N = INT()
A = LIST()
lcm_base = lambda x, y: (x * y) // gcd(x, y)
many_lcm = lambda numbers: reduce(lcm_base, numbers)
unit = many_lcm(A)
seg = SegmentTree(N+1, gcd, unit)

for i, x in enumerate(A):
	seg.update(i+1, x)

ans = 0
for i, x in enumerate(A):
	seg.update(i+1, unit)
	ans = max(ans, seg.query(1, N))
	seg.update(i+1, A[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from math import sqrt
def prime_division2(x):
    q = int(sqrt(x))
    h = {}
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            h[i] = ex
    if x>q:
        h[x] = 1
    return h

from fractions import gcd
from functools import reduce
n = inn()
a = inl()
g = reduce(gcd,a)
h = {}
for i in range(2):
    ps = prime_division2(a[i])
    for p in ps:
        h[p] = [BIG,BIG]
pssave = []
for i in range(n):
    pes = prime_division2(a[i])
    pssave.append(pes)
    for p in h:
        if p not in pes:
            h[p] = [0,h[p][0]]
        elif pes[p]<h[p][0]:
            h[p] = [pes[p],h[p][0]]
        elif pes[p]<h[p][1]:
            h[p] = [h[p][0],pes[p]]
mx = 0
for i in range(n):
    pes = pssave[i]
    x = 1
    for p in h:
        if (p not in pes or pes[p]==h[p][0]) and h[p][1]<BIG:
            x *= p**(h[p][1]-h[p][0])
    mx = max(mx,x)
print(g*mx)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    if a==b:
      return a
    else:
      a,b=max(a,b),min(a,b)
      if a%b==0:
        return b
      else:
        return gcd(b,a%b)
def gcd_for_list(L):
    if len(L)==1:
      return L[0]
    for i in range(len(L)):
      if i==0:
        tmp=gcd(L[i],L[i+1])
      elif i==1:
        pass
      else:
        tmp=gcd(tmp,L[i])
    return tmp
ans=0
for i in range(0,n):
  if i==0:
    ans=max(ans,gcd_for_list(a[i+1:]))
  elif i==n-1:
    ans=max(ans,gcd_for_list(a[0:i]))
  else:
    l_r=a[0:i]
    l_l=a[i+1:]
    ans=max(ans,gcd(gcd_for_list(l_r),gcd_for_list(l_l)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 区間[i,j]における最小値を返す
# 値の更新をする
import fractions
class segment_tree:
    '''
    init_val(int): 初期化値
    Input(array):  入力
    '''
    def __init__(self, init_val, Input):
        #self.num:n以上の最小の2のべき乗(一番下のNodeの数)
        n=len(Input)
        self.init_val = init_val
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [init_val] * 2 * self.num
        for i in range(n):
            self.seg[i + self.num - 1] = Input[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i]=self._segfunc(self.seg[2*i+1],self.seg[2*i+2])
    def _segfunc(self, left, right):
        '''
        ここに求めたい関数を入れる
        ex)最小値問題→min, 
        left:左の子
        right:右の子
        '''
        res=fractions.gcd(left,right)
        return res
    def update(self, k, x):
        '''
        k番目の値をxに書き換える
        '''
        k += self.num - 1
        self.seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.seg[k] = self._segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    def query(self, p, q):
        '''
        区間[p,q)の目的の値を取り出す
        '''
        if q <= p:
            return self.init_val
        p += self.num - 1
        q += self.num - 2
        res = self.init_val
        while q - p > 1:
            if p % 2 == 0: #始点が偶数or終点が奇数だと端っこが余る
                res = self._segfunc(res, self.seg[p])
            if q % 2 == 1:
                res = self._segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        res = self._segfunc(res, self.seg[p])
        res = self._segfunc(res, self.seg[q])
        return res
INF = 10 ** 10
n=int(input())
a=list(map(int,input().split()))

# a = [randint(0,N*2) for _ in range(N)]
dp = segment_tree(0, a)
ans=-1
for i in range(n):
  ans=max(ans,fractions.gcd(dp.query(0,i),dp.query(i+1,n)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

def my_gcd(A, i, N):
  if i == 0:
    gcd_tmp = A[1]
    for j in range(2, N):
      gcd_tmp = fractions.gcd(gcd_tmp, A[j])
    return gcd_tmp
  else:
    gcd_tmp = A[0]
    for j in range(N):
      if j != i:
        gcd_tmp = fractions.gcd(gcd_tmp, A[j])
      else:
        if i < N - 1:
          gcd_tmp = fractions.gcd(gcd_tmp, A[j + 1])
        else:
          break
    return gcd_tmp
    
N = int(input())
A = [int(i) for i in input().split()]
gcd_ = 0
if N == 2:
  gcd_ = max(A[0], A[1])
else:
  for i in range(N):
    gcd_ = max(gcd_, my_gcd(A, i, N))
print(gcd_)

Submission status: Time Limit Exceeded

Solution code:
import fractions

n = int(input())
list_A = list(map(int, input().split()))
ans = 0
for i in range(n):
    a = list_A.pop(0)
    b = list_A[0]
    for j in range(1, n-1):
        b = fractions.gcd(b, list_A[j])
        if b < ans:
            break
    if ans < b:
        ans = b
    list_A.append(a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

n = int(input())
list_A = list(map(int, input().split()))
ans = []
for i in range(n):
    a = list_A.pop(0)
    b = list_A[0]
    for j in range(1, n-1):
        b = fractions.gcd(b, list_A[j])
    ans.append(b)
    list_A.append(a)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from math import ceil
n = int(input())
A = list(map(int, input().split()))

def Prime_factorization(num):
  ans_dic = dd(lambda: 0)
  for divisor in range(2, ceil(num**0.5) + 2):
    while num % divisor == 0:
      num //= divisor
      ans_dic[divisor] += 1
  else:
    if len(ans_dic.keys()) == 0:
      ans_dic[num] += 1
  return ans_dic

GCDs = {}
for num in A:
  GCDs[num] = Prime_factorization(num)
#print(GCDs)
    
def marge(A, GCDs, skip):
  keys = set()
  #keyを作成
  for i in range(len(A)):
    if i != skip:
      keys = keys | set(GCDs[A[i]].keys())
  #print(keys)
  #gcdを計算
  #各keyの個数の最小数を算出
  gcd = 1
  for prime in keys:
    min_num_prime = 10**9
    for i in range(len(A)):
      if i != skip:
        min_num_prime = min(GCDs[A[i]][prime], min_num_prime)
    gcd *= prime**min_num_prime
  return gcd  
  
max_gcd = 0
for i in range(len(A)):
  max_gcd = max(marge(A, GCDs, skip=i), max_gcd)
print(max_gcd)

Submission status: Time Limit Exceeded

Solution code:
import functools
import fractions

# 最大公約数
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

def gcd_list(nums):
    return functools.reduce(gcd, nums)

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

left = [0]
right = []
for i in range(N):
    tmp_left = A[:i+1]
    tmp_right = A[i:]
    left.append(gcd_list(tmp_left))
    right.append(gcd_list(tmp_right))
right += [0]
#print(left)
#print(right)

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

Submission status: Time Limit Exceeded

Solution code:
import functools

# 最大公約数
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

def gcd_list(nums):
    return functools.reduce(gcd, nums)

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

# i番目を取り去る
ans = 0
for i in range(N):
    tmp_left = A[:i]
    tmp_right = A[i+1:]
    tmp_lr = tmp_left + tmp_right
    tmp = gcd_list(tmp_lr)
    ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

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

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

def main():
    n=int(input())
    a=list(map(int,input().split()))
    ans=gcd(*a)
    for i in range(n):
      l=[a[j] for j in range(n) if j!=i]
      ans=max(gcd(*l),ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import fractions

n = int(input().rstrip())
numbers = [int(i) for i in input().rstrip().split(" ")]

l_list = [numbers[0]]
for i in range(1, n):
    l_list.append(fractions.gcd(l_list[i - 1], numbers[i]))

r_list = [numbers[len(numbers) - 1]]
for i in reversed(range(0, n - 1)):
    r_list.insert(0, fractions.gcd(r_list[0], numbers[i]))

ans = 0
for i in range(n):
    l = 0
    if i > 0:
        l = l_list[i - 1]
    r = 0
    if i < n - 1:
        r = r_list[i + 1]
    if l == 0:
        l = r
    if r == 0:
        r = l
    ans = max(ans, fractions.gcd(l, r))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

n = int(input().rstrip())
numbers = [int(i) for i in input().rstrip().split(" ")]


def get_gcm(num1: int, num2: int):
    if num1 % num2 == 0:
        return num2
    return get_gcm(num2, num1 % num2)


l_list = [numbers[0]]
for i in range(1, n):
    l_list.append(get_gcm(l_list[i - 1], numbers[i]))

r_list = [numbers[len(numbers) - 1]]
for i in reversed(range(0, n - 1)):
    r_list.insert(0, get_gcm(r_list[0], numbers[i]))

ans = 0
for i in range(n):
    l = 0
    if i > 0:
        l = l_list[i - 1]
    r = 0
    if i < n - 1:
        r = r_list[i + 1]
    if l == 0:
        l = r
    if r == 0:
        r = l
    ans = max(ans, get_gcm(l, r))
print(ans)

Submission status: Time Limit Exceeded

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

import fractions

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

def init(init_val):
    # set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

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

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

# identity element
ide_ele = 0

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

init(A)

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

def main():
    n = int(input())
    a = [int(t)for t in input().split()]

    a_gcd = functools.reduce(fractions.gcd,a)
    a = [x//a_gcd for x in a]
    gcdlist = []

    m = 1
    for i in range(n):
        t = [x for x in a]
        del t[i]
        t_gcd = functools.reduce(fractions.gcd,t)
        m = t_gcd if t_gcd>m else m

    print(a_gcd*m)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools
 
def main():
    n = int(input())
    a = [int(t)for t in input().split()]
 
    a_gcd = functools.reduce(fractions.gcd,a)
  
    a = [x//a_gcd for x in a]
    gcdlist = []
 
    for i in range(n):
        t = [x for x in a]
        del t[i]
        t_gcd = functools.reduce(fractions.gcd,t)
        gcdlist.append(t_gcd)
 
    print(a_gcd*max(gcdlist))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

def main():
    n = int(input())
    a = [int(t)for t in input().split()]

    a_gcd = functools.reduce(fractions.gcd,a)
    gcdlist = []

    for i in range(n):
        t = [x//a_gcd for x in a]
        del t[i]
        t_gcd = functools.reduce(fractions.gcd,t)
        gcdlist.append(t_gcd)

    print(a_gcd*max(gcdlist))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools
import fractions
import copy

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

def GCD(values):
    g = functools.reduce(fractions.gcd, values)
    return g

ans = 0
for i in range(n):
    a.remove(cleana[i])
    ans = max(ans, GCD(a))
    # print("a:",a)
    # print("GCD:",GCD(a))
    a = copy.deepcopy(cleana)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce


def gcd(v1, v2):
    v3 = v1 % v2
    if v3 == 0:
        return v2
    return gcd(v2, v3)


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

    max_gcd = max(reduce(gcd, A[1:]), reduce(gcd, A[:N-1]))

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

        #print(A[:i], A[i+1:])

        max_gcd = max(max_gcd, gcd(v1, v2))

    #print(reduce(gcd, A))

    print(max_gcd)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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

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

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

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

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

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

# 出力
print(ans)

Submission status: Time Limit Exceeded

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

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

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

# l[i]:a[i]を含まない前方要素の最大公約数
l = [0 for _ in range(n)]
l[0] = 0
for i in range(1, n):
    l[i] = gcd_list(a[0:i])
# print(l)

# r[i]:a[i]を含まない後方要素の最大公約数
r = [0 for _ in range(n)]
r[-1] = 0
for i in range(0, n-1):
    r[i] = gcd_list(a[i+1:n])
# print(r)

ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i],r[i]))

print(ans)

Submission status: Time Limit Exceeded

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

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

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

ans = 0
l=len(a)
for i in range(l):
    b = a[0:i] + a[i+1:l]
    ans = max(ans, gcd_list(b))

print(ans)