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 math
N = int(input())
A = [int(_) for _ in input().split()]


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


class SegmentTree():
    def m(self, v1, v2):  # ***monoid***
        return gcd(v1, v2)

    def __init__(self, array):
        m = self.m
        e = self.e = 0  # ***identity element***
        size = self.size = 10**6  # ***limit for array size***
        n = self.n = len(array)
        dat = self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):  # set value at position p (0-indexed)
        m, n, dat = self.m, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = m(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        m, e, n, dat = self.m, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = m(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = m(res, dat[r])
            l >>= 1
            r >>= 1
        return res


ST = SegmentTree(A)
ans = 0
for i, a in enumerate(A):
    ST.modify(i, ST.e)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)

Submission status: Time Limit Exceeded

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

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

gcd_forward = []
gcd_all = numbers[0]
for i in range(0, N - 1):
  gcd_all = gcd(gcd_all, numbers[i])
  gcd_forward.append(gcd_all)

gcd_backward = []
gcd_all = numbers[-1]
for i in range(N - 1, 0, -1):
  gcd_all = gcd(gcd_all, numbers[i])
  gcd_backward.insert(0, gcd_all)

gcd_forward.insert(0, gcd_backward[0])
gcd_backward.append(gcd_forward[-1])

gcd_max = 1
for i in range(N):
  gcd_max = max(gcd_max, gcd(gcd_forward[i], gcd_backward[i]))
  
print(gcd_max)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
y = input().split(" ")
y = list(map(int, y))
y.sort()
i = y[1]
result = 1


while i > 1:
  count = 0
  for n in y:
    if n % i != 0:
      count += 1
      if count >= 2:
        continue
      
  if count <= 1:
    result = i
    break
  i -= 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())
a = list(map(int, input().split()))
 
 
def gcd(x,y):
    while y:
        x,y = y, x % y
    return x
    
gcd_left = [0]
gcd_rigth = [0]
gcd_list = []

for i in range(n):
    s = gcd(gcd_left[i], a[i])
    gcd_left.append(s)
    
for i in range(n):
    t = gcd(gcd_rigth[i], a[-i-1])
    gcd_rigth.append(t)

for i in range(n):
    u = copy.copy(a)
    del u[i]
    v = gcd(gcd_left[i], gcd_rigth[n-1-i])
    gcd_list.append(v)

print(max(gcd_list))

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
y = input().split(" ")
y = list(map(int, y))
y.sort()
i = y[1]
result = 1


while i > 1:
  count = 0
  for n in y:
    if n % i != 0:
      count += 1
    
    if count >= 2:
      continue
      
  if count <= 1:
    result = i
    break
  i -= 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
y = input().split(" ")
y = list(map(int, y))
result = 1
i = max(y)

while i > 1:
  count = 0
  for n in y:
    if n % i != 0:
      count += 1
    
    if count >= 2:
      continue
      
  if count <= 1:
    result = i
    break
  i -= 1

print(result)

Submission status: Time Limit Exceeded

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

n = int(input())
a = [int(i) for i in input().split()]
l, r = [0], [0]
for i in range(n):
    l = l + [gcd(l[i], a[i])]
    r = [gcd(r[0], a[n - 1 - i])] + r
# print(l, r)
ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i], r[i + 1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
# a = sorted(list(map(int, input().split())), reverse=True) # 降順 <=ここにO(n)だけ時間がかかる
a = list(map(int, input().split()))


# ユークリッドの互除法
ans = 1
for j in range(n):
    x = a.pop(j)
    b = a[0]
    # print(x, a, b)
    for i in range(n-2):
        c = a[i+1]
        if c > b:
            b,c=c,b
            # print(b,c)
        else:
           pass
        r = b%c
        while r!=0:
            b = c
            c = r
            r = b%c
        # while が止まったら、cが最大公約数
        b = c # bを更新
    ans = max(ans, b)
    # print(ans)
    a.insert(j, x) # xを戻す
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd
    def update(k,x):
        k+=N0-1
        data[k]=x
        while k+1:
            k=~-k//2
            data[k]=gcd(data[2*k+1],data[2*k+2])
    def query(l,r):
        L,R=l+N0,r+N0
        s=0
        while L<R:
            if R&1:
                R-=1
                s=gcd(s,data[R-1])
            if L&1:
                s=gcd(s,data[L-1])
                L+=1
            L>>=1
            R>>=1
        return s
    n,*a=map(int,open(0).read().split())
    N0=2**(n-1).bit_length()
    data=[0]*2*N0
    for i in range(n):
        update(i,a[i])
    print(max(gcd(query(0,i),query(i+1,n))for i in range(n)))
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

n, a = II(), LI()
maxi = max(GCD_LIST(a[1:]), GCD_LIST(a[:n-1]))
for i in range(1,n-1):
    left_gcd = GCD_LIST(a[:i])
    right_gcd = GCD_LIST(a[i+1:])
    maxi = max(maxi, fractions.gcd(left_gcd, right_gcd))

print(maxi)

Submission status: Time Limit Exceeded

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

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

ans = []
for i in range(N):
  tmp = A[:i] + A[i+1:]
  res = tmp[0]
  for r in range(1,len(tmp)):
    res = gcd(res, tmp[r])
  ans.append(res)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
# スペース区切りの整数の入力
A = list(map(int, input().split()))


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

ans=[]

for i in range(N):
    B=A[:]
    del B[i]
    sol=0
    for b in B:
        sol=gcd(sol,b)
    ans.append(sol)

print(max(ans))

Submission status: Time Limit Exceeded

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

gcdlistL = [0]
gcdlistR = [0]
for i in range(N):
    gcdlistL.append(gcd(gcdlistL[-1], A[i]))
    gcdlistR.insert(0, gcd(A[N-1-i], gcdlistR[-1-i]))

gcdmax = 0
for i in range(N):
    gcdmax = max(gcdmax, gcd(gcdlistL[i], gcdlistR[i+1]))

print(gcdmax)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True) # 降順

# ユークリッドの互除法
ans = 1
for j in range(n):
    x = a.pop(j)
    # print(a)
    b = a[0]
    for i in range(n-1-1):
        c = a[i+1]
        r = b%c
        while r!=0:
            b = c
            c = r
            r = b%c
        # print(c)
        b = min(b, c) # bを更新
    ans = max(ans, b)
    # print(ans)
    a.insert(j, x) # xを戻す
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C
import functools
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
pre_a = -1

for i in range(n):
    if pre_a != a[i]:
        if len(a[:i]) >= 1 and len(a[i+1:]) >= 1:
            res = gcd(functools.reduce(gcd, a[:i]), functools.reduce(gcd, a[i+1:]))
        else:
            values = a[:i] + a[i+1:]
            res = functools.reduce(gcd, values)
        ans = max(ans, res)
    pre_a = a[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Euclid(a, b):
  if a>=b:
    big, small = a, b
  else:
    big, small = b, a
  while big % small:
    big, small = small, big % small
  return small

def Euclid_over3(list,N):
  for i in range(N):
    if i == 0:
      pass
    elif i == 1:
      e=Euclid(A[0],A[1])
    else:
      e=Euclid(e,A[i])
  return e
  
N = int(input())
A = list(int(i) for i in input().split())
ans = 0
max = 0

if N == 2:
  if A[0]>=A[1]:
    print(A[0])
  else:
    print(A[1])
  exit()

for i in range(N):
  tmp = A.pop(i)
  ans = Euclid_over3(A,N-1)
  A.insert(i,tmp)
  if max < ans:
    max = ans
      
print(max)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

input = sys.stdin.readline
n = int(input())
a_que = deque(list(map(int, input().split())))
ans = 1
for _ in range(n):
    out = a_que.popleft()
    m = 0
    for a in a_que:
        m = gcd(m, a)
    ans = max(ans, m)
    a_que.append(out)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

gcd_left = []
gcd_left.append(A[0])
gcd_right = []
gcd_right.append(A[N-1])
for i in range(N-1):
    gcd_left.append(fractions.gcd(gcd_left[i],A[i+1]))
    gcd_right.insert(0,fractions.gcd(gcd_right[0],A[N-2-i]))

min_gcd = 1
tmp_left = 0
tmp_right = 0
if N>2:
    if min_gcd < gcd_right[1]:
        min_gcd = gcd_right[1]
    if min_gcd < gcd_left[N-2]:
        min_gcd = gcd_left[N-2]
    for i in range(0,N-2):
        tmp_left = gcd_left[i]
        tmp_right = gcd_right[i+2]
        tmp = fractions.gcd(tmp_left,tmp_right)
        if tmp > min_gcd:
            min_gcd = tmp
else:
    min_gcd = max(A[0],A[1])
print(min_gcd)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
import fractions
from functools import reduce
 
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
 
score = 0
for i in range(N):
    B = A
    keep = B.pop(0)
    n = gcd_list(B)
    if n > score:
        score = n
    A.append(keep)
 
 
print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

input = sys.stdin.readline
n = int(input())
a_list = list(map(int, input().split()))
ans = 1
for i in range(n):
    if i == 0:
        gcd_r = 0
        r_list = a_list[i+1:]
        for r in r_list:
            if gcd_r == 0:
                gcd_r = r
            else:
                gcd_r = gcd(gcd_r, r)
        m = gcd_r
    elif i == n-1:
        gcd_l = 0
        l_list = a_list[:i]
        for l in l_list:
            if gcd_l == 0:
                gcd_l = l
            else:
                gcd_l = gcd(gcd_l, l)
        m = gcd_l
    else:
        gcd_l, gcd_r = 0, 0
        l_list = a_list[:i]
        r_list = a_list[i+1:]
        for l in l_list:
            if gcd_l == 0:
                gcd_l = l
            else:
                gcd_l = gcd(gcd_l, l)
        for r in r_list:
            if gcd_r == 0:
                gcd_r = r
            else:
                gcd_r = gcd(gcd_r, r)
        m = gcd(gcd_l, gcd_r)
    ans = max(ans, m)
print(ans)

Submission status: Time Limit Exceeded

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

import fractions
from functools import reduce

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

score = 0
for i in range(N):
    B = A
    keep = B.pop(0)
    n = gcd_list(B)
    if n > score:
        score = n
    A.append(keep)


print(score)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(N-1):
    L=L+[gcd(L[-1],A[i])]
    R=[gcd(R[0],A[N-i-1])]+R
M=[gcd(L[n],R[n]) for n in range(N)]
print(max(M))

Submission status: Time Limit Exceeded

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()))
A.sort(reverse=True)

gcdlistL = [0]
for i in range(N):
    gcdlistL.append(gcd(gcdlistL[-1], A[i]))
#    print("gcdlistL[-1]={},A[{}]={}".format(gcdlistL[-1],i,A[i]))
#print("gcdlistL={}".format(gcdlistL))

gcdlistR = [0]
for i in range(N):
    gcdlistR.insert(0, gcd(A[N-1-i], gcdlistR[-1-i]))
#    print("gcdlistR[-1-{}]={},A[{}]={}".format(gcdlistR[-1-i],i,i,A[N-1-i]))
#print("gcdlistR={}".format(gcdlistR))

gcdmax = 0
for i in range(N):
    gcdmax = max(gcdmax, gcd(gcdlistL[i], gcdlistR[i+1]))
#    print("gcmax={},gcdL[{}]={},gcdR[{}]={}".format(gcdmax,gcdlistL[i],gcdlistR[-1-i],i,i,A[N-1-i]))

print(gcdmax)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math
from functools import reduce

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

gcd_list = []

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

def my_gcd(*numbers):
    return reduce(calc_gcd, numbers)

for i in range(len(A)):
    tmp = copy.copy(A)
    del tmp[i]
    gcd_list.append(my_gcd(*tmp))

print(max(gcd_list))

Submission status: Time Limit Exceeded

Solution code:
#C
N = int(input())
A = list(map(int, input().split()))
def gcd(a, b):
    if a == b: return a
    else:
        if a < b: a, b = b, a #so, a > b
        if b == 0: return a
        return gcd(b, a % b)

def calcgcd(L, ind):
    if len(L) == 1:
        return max(L)
    elif len(L) == 2:
        return max(L)
    else:
        l, r = L[0], L[-1]
        for i in range(0, ind):
            l = gcd(l, L[i])
        for i in range(ind + 1, N):
            r = gcd(r, L[i])
        if ind == 0: ans =  r
        elif ind == N - 1: ans =  l
        else: ans = gcd(l,r)
        return ans
M = []
for i in range(N):
    M.append(calcgcd(A,i))
print(max(M))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
import functools
import fractions
l1=[]
for i in range(n):
  a=l[0]
  del l[0]
  s = functools.reduce(fractions.gcd, l)
  l1.append(s)
  l.append(a)
print(max(l1))

Submission status: Time Limit Exceeded

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

N=int(input().strip())
A=[int(x) for x in input().strip().split()]
# def gcd(a,b):
#     if b==0:
#         return a
    
#     return gcd(b,a%b)

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

for i in range(len(L)-1):
    ANS.append(gcd(L[i],R[i+1]))

print(max(ANS))

Submission status: Time Limit Exceeded

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

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

ans = 0
L = [0]
R = [0]
for i in range(n-1):
    l = gcd(L[-1], A[i])
    L.append(l)
    r = gcd(R[-1], A[::-1][i])
    R.append(r)
for l, r in zip(L,R[::-1]):
    ans = max(ans, gcd(l, r))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import functools
import fractions

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

for i in range(n):
    tmp=a[i]
    a.pop(i)
    ans.append(functools.reduce(fractions.gcd,a))
    a.insert(i,tmp)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
input = sys.stdin.readline

N=int(input().strip())
A=[int(x) for x in input().strip().split()]
def gcd(a,b):
    if b==0:
        return a
    
    return gcd(b,a%b)

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

for i in range(len(L)-1):
    ANS.append(gcd(L[i],R[i+1]))

print(max(ANS))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))

P_MAX = 32000
P = []
for i in range(2,P_MAX):
    sieve = 1
    for p in P:
        if p*p > i:
            break
        elif i % p == 0:
            sieve = 0
            break
    if sieve == 0:
        continue
    else:
        P.append(i)

def factorize(n):
    primes = []
    powers = []
    for p in P:
        if p * p > n:
            break
        elif n % p == 0:
            k = 0
            while n % p == 0:
                n //= p
                k += 1
            primes.append(p)
            powers.append(k)
    if n > 1:
        primes.append(n)
        powers.append(1)
    return primes, powers

N = int(input())
A = inpl()
infty = 100
lowest_powers = defaultdict(lambda: [infty,infty])
bottle_necks = defaultdict(lambda: -1)
all_factors = set()
for n in range(N):
    primes, powers = factorize(A[n])
    prev_primes = list(bottle_necks.keys())
    done = defaultdict(int)
    for i in range(len(primes)):
        done[primes[i]] = 1
        if not primes[i] in all_factors:
            all_factors.add(primes[i])
            if n == 1:
                lowest_powers[primes[i]] = [0,powers[i]]
                bottle_necks[primes[i]] = 0
            elif n == 0:
                lowest_powers[primes[i]] = [powers[i],infty]
                bottle_necks[primes[i]] = 0
        lowest = lowest_powers[primes[i]]
        if powers[i] == lowest[0]:
            lowest[1] = lowest[0]
            bottle_necks[primes[i]] = -1
        elif powers[i] < lowest[0]:
            lowest[1] = lowest[0]
            lowest[0] = powers[i]
            bottle_necks[primes[i]] = n
        elif powers[i] < lowest[1]:
            lowest[1] = powers[i]
    for p in all_factors:
        if done[p] == 0:
            lowest = lowest_powers[p]
            if lowest[0] == 0:
                lowest[1] = 0
                bottle_necks[p] = -1
            else:
                lowest[1] = lowest[0]
                lowest[0] = 0
                bottle_necks[p] = n

bnl = defaultdict(lambda: [])
for p,n in bottle_necks.items():
    if n >= 0:
        lowest = lowest_powers[p]
        bnl[n].append([p,lowest[1]-lowest[0]])
best_n = -1
largest_f = 1
for n in range(N):
    f = 1
    for pp in bnl[n]:
        f *= pp[0]**pp[1]
    if f > largest_f:
        largest_f = f
        best_n = n

ans = 1
bn = bnl[best_n]
pn = [ s[0] for s in bn]
for p in all_factors:
    if p in pn:
        ans *= p**lowest_powers[p][1]
    else:
        ans *= p**lowest_powers[p][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
import numpy as np 
N = int(input())
A = list(map(int, input().strip().split()))
i = 0
B = 0
while i <= N - 1:
    Aa = np.delete(A, i)
    B1 = gcd_list(Aa)
    if B1 > B:
        B = B1
    i += 1
print(B)

Submission status: Time Limit Exceeded

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


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

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

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

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

print(max(num))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
 
P_MAX = 32000
sieve = [1]*P_MAX
sieve[0] = sieve[1] = 0
P = []
for i in range(2,P_MAX):
    sieve = 1
    for p in P:
        if p*p > i:
            break
        elif i % p == 0:
            sieve = 0
            break
    if sieve == 0:
        continue
    else:
        P.append(i)
 
def factorize(n):
    primes = []
    powers = []
    for p in P:
        if p * p > n:
            break
        elif n % p == 0:
            k = 0
            while n % p == 0:
                n //= p
                k += 1
            primes.append(p)
            powers.append(k)
    if n > 1:
        primes.append(n)
        powers.append(1)
    return primes, powers
 
N = int(input())
A = inpl()
infty = 100
lowest_powers = defaultdict(lambda: [infty,infty])
bottle_necks = defaultdict(lambda: -1)
all_factors = set()
for n in range(N):
    primes, powers = factorize(A[n])
    prev_primes = list(bottle_necks.keys())
    done = defaultdict(int)
    for i in range(len(primes)):
        done[primes[i]] = 1
        if not primes[i] in all_factors:
            all_factors.add(primes[i])
            if n == 1:
                lowest_powers[primes[i]] = [0,powers[i]]
                bottle_necks[primes[i]] = 0
            elif n == 0:
                lowest_powers[primes[i]] = [powers[i],infty]
                bottle_necks[primes[i]] = 0
        lowest = lowest_powers[primes[i]]
        if powers[i] == lowest[0]:
            lowest[1] = lowest[0]
            bottle_necks[primes[i]] = -1
        elif powers[i] < lowest[0]:
            lowest[1] = lowest[0]
            lowest[0] = powers[i]
            bottle_necks[primes[i]] = n
        elif powers[i] < lowest[1]:
            lowest[1] = powers[i]
    for p in all_factors:
        if done[p] == 0:
            lowest = lowest_powers[p]
            if lowest[0] == 0:
                lowest[1] = 0
                bottle_necks[p] = -1
            else:
                lowest[1] = lowest[0]
                lowest[0] = 0
                bottle_necks[p] = n
 
bnl = defaultdict(lambda: [])
for p,n in bottle_necks.items():
    if n >= 0:
        lowest = lowest_powers[p]
        bnl[n].append([p,lowest[1]-lowest[0]])
best_n = -1
largest_f = 1
for n in range(N):
    f = 1
    for pp in bnl[n]:
        f *= pp[0]**pp[1]
    if f > largest_f:
        largest_f = f
        best_n = n
 
ans = 1
bn = bnl[best_n]
pn = [ s[0] for s in bn]
for p in all_factors:
    if p in pn:
        ans *= p**lowest_powers[p][1]
    else:
        ans *= p**lowest_powers[p][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

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

import numpy as np 
N = int(input())
A = list(map(int, input().strip().split()))
i = 0
B = 0
while i <= N - 1:
    Aa = np.delete(A, i)
    B1 = gcd_list(Aa)
    if B1 > B:
        B = B1
    i += 1
print(B)

Submission status: Time Limit Exceeded

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

from fractions import gcd

L = [0, 0]
for ai in A:
    L.append(gcd(L[-1], ai))

R = [0, 0]
for ai in A[::-1]:
    R.insert(0, gcd(R[0], ai))

print(max(gcd(l, r) for l, r in zip(L, R)))

Submission status: Time Limit Exceeded

Solution code:
# ユークリッドの互除法
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcd_for_list(target_list, begin_idx, end_idx):
    ans = 0
    for x in target_list[begin_idx:end_idx]:
        ans = gcd(ans,x)
    return ans

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


ans = 1

for i in range(1,n+1):
    left = gcd_for_list(aa,0,i-1)
    right = gcd_for_list(aa,i,n)
    temp = gcd(left, right)
    ans = max(ans, temp)
    # print(aa[0:i-1],left, aa[i:n],right)
print(ans)

Submission status: Time Limit Exceeded

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


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

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

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

for i in range(N-2):
    num = max(gcd(gcd_list[i], reverse_gcd_list[i+2]), num)

print(max(num, gcd_list[-2], reverse_gcd_list[1]))

Submission status: Time Limit Exceeded

Solution code:
###
### atcorder test program
###

### math class
class math:
    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    def gcd_list(self, A):
        if not A:
            return 0
        for i in reversed(range(1, self.gcd(max(A),min(A))+1)):
            count = 0
            for j in A:
                if (j % i) == 0:
                    count += 1
            if count == len(A):
                return i
        return 0

### input num
#i = input()
#A, B, T = [int(x) for x in i.split()]
N = int(input())
A = [int(x) for x in input().split()]
#C = [int(x) for x in input().split()]

### input debug
#print("debug:{}".format(gcd(max(A),min(A))))
#print(list(reversed(range(1, gcd(max(A),min(A))+1))))

mathfunc = math()
anslist = []

for i in range(N):
    Rgcd = mathfunc.gcd_list(A[:i])
    Lgcd = mathfunc.gcd_list(A[i+1:])
    anslist.append(mathfunc.gcd(Rgcd,Lgcd))

### output
print(max(anslist))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
import fractions

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

r = 0

for i in range(n):
    if i == 0:
        all_gcd = a[1]
    else:
        all_gcd = a[0]
    for j in range(n):
        if i == j:
            continue
        else:
            all_gcd = fractions.gcd(all_gcd, a[j])
    r = all_gcd if all_gcd > r else r

print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
input = sys.stdin.readline

N=int(input().strip())
A=[int(x) for x in input().strip().split()]
def gcd(a,b):
    if b==0:
        return a
    
    return gcd(b,a%b)

ANS=[]
for i in range(len(A)):
    B=copy.deepcopy(A)
    if len(B)>1:
        B.pop(i)
    t=0
    for c in range(len(B)):
        t=gcd(B[c],t)
    ANS.append(t)

print(max(ANS))

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = raw_input().split()

cnt = 0
for i in a:
    a[cnt] = int(i)
    cnt += 1

chk = {}
chk2 = {}
def make_divisors(k):
    divisors = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            if i in chk:
                chk[i] += 1
            else:
                chk[i] = 1
            if i != k // i:
                key = int(k//i)
                if key in chk:
                    chk[key] += 1
                else:
                    chk[key] = 1
    return divisors

for i in range(2):
    make_divisors(a[i])
cnt = 1
for i in range(2,len(a)):
    k = a[i]
    if k in chk:
        make_divisors(k)
        cnt += 1
        continue
    del_list = []
    for j in chk:
        if k % j == 0:
            chk[j] += 1
        if chk[j] < cnt+1:
            del_list.append(j)
    for j in del_list:
        del chk[j]
    cnt += 1

answer = 0
for i in chk:
    if int(chk[i]) >= chk[1] - 1 and i > answer:
        answer = i
print answer

Submission status: Time Limit Exceeded

Solution code:

### math class
class math:
    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    def gcd_list(self, A):
        if not A:
            return 0
        for i in reversed(range(1, max(A)+1)):
            count = 0
            for j in A:
                if (j % i) == 0:
                    count += 1
            if count == len(A):
                return i
        return 0

### input num
#i = input()
#A, B, T = [int(x) for x in i.split()]
N = int(input())
A = [int(x) for x in input().split()]
#C = [int(x) for x in input().split()]

### input debug
#print("debug:{}".format(gcd(max(A),min(A))))
#print(list(reversed(range(1, gcd(max(A),min(A))+1))))

mathfunc = math()
anslist = []

for i in range(N):
    Rgcd = mathfunc.gcd_list(A[:i])
    Lgcd = mathfunc.gcd_list(A[i+1:])
    anslist.append(mathfunc.gcd(Rgcd,Lgcd))

### output
print(max(anslist))

Submission status: Time Limit Exceeded

Solution code:
import functools
import math

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



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

listg1 = []
listg2 = []
for i in range(N-1):
    listg1.append(functools.reduce(GCD,list1[0:i+1]))
    listg2.append(functools.reduce(GCD,list1[N-i-1:N]))


gcda = 0
for i in range(N):
    if i==0:
        gcd = listg2[N-2]
    elif i==N-1:
        gcd = listg1[N-2]
    else:
        gcd = GCD(listg1[i-1],listg2[N-2-i])
    if gcd > gcda:
        gcda = gcd

print(gcda)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = raw_input().split()

cnt = 0
for i in a:
    a[cnt] = int(i)
    cnt += 1

chk = {}
def make_divisors(k):
    divisors = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            if i in chk:
                chk[i] += 1
            else:
                chk[i] = 1
            if i != k // i:
                key = int(k//i)
                if key in chk:
                    chk[key] += 1
                else:
                    chk[key] = 1
    return divisors

for i in range(2):
    make_divisors(a[i])
cnt = 1
for i in range(2,len(a)):
    k = a[i]
#    if k in chk:
#        continue
    del_list = []
    for j in chk:
        if k % j == 0:
            chk[j] += 1
        if chk[j] < cnt+1:
            del_list.append(j)
    for j in del_list:
        del chk[j]
    cnt += 1

answer = max(chk.keys())
#answer = 0
#for i in chk:
#    if int(chk[i]) >= chk[1] - 1 and i > answer:
#        answer = i
print answer

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
from copy import copy


def main():
    N = int(input())
    A = list(map(int, input().split()))
    gcds = []
    for i in range(N):
        if i == 0:
            gcds.append(gcd(*A[i+1:]))
        elif i == N-1:
            gcds.append(gcd(*A[:i]))
        else:
            gcds.append(gcd(gcd(*A[:i]), gcd(*A[i+1:])))
    print(max(gcds))


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools
import fractions

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

g = []
if N == 2:
  print(max(A))
else:
  for i in range(N):
    g.append(functools.reduce(fractions.gcd, A[:i] + A[i+1:]))
  print(max(g))