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 numpy as np

# 約数列挙(nを含む)
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n // i)

    return divisors


N = int(input())
A = np.array(input().split(), dtype=np.int64)
A.sort()
A = A[::-1]


p0 = make_divisors(A[0])
p1 = make_divisors(A[-1])
P = p0 | p1

for p in sorted(list(P))[::-1]:
    c = 0
    for a in A:
        if a % p == 0:
            c += 1

    if c == N - 1:
        break

q = np.gcd.reduce(A)
if p > q:
    print(p)
else:
    print(q)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = sorted(list(map(int,input().split())))
ans = []

for n in range(N):
  ans+=[np.gcd.reduce(np.delete(A,n))]

print(max(ans))

Submission status: Time Limit Exceeded

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

from collections import deque
q = deque([])
q.append([0, A[0], False])
q.append([1, A[1], True])
# 深さ優先探索
# idx, これまでのGCD, 抜いたか抜いてないか
ans = 0
while q:
    idx, g, jogai = q.pop()
    if g <= ans:
        continue
    if idx == n-1:
        ans = max(ans, g)
        continue

    q.append([idx+1, gcd(g, A[idx+1]), jogai])
    if not jogai:
        q.append([idx+1, g, True])
print(ans)

Submission status: Time Limit Exceeded

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

from collections import deque
q = deque([])
q.append([0, A[0], False])
q.append([1, A[1], True])
# 深さ優先探索
# idx, これまでのGCD, 抜いたか抜いてないか
ans = 0
while q:
    idx, g, jogai = q.pop()
    if idx == n-1:
        ans = max(ans, g)
        continue

    q.append([idx+1, gcd(g, A[idx+1]), jogai])
    if not jogai:
        q.append([idx+1, g, True])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    return b if not a%b else gcd(b,a%b)
def lcm(a,b):
    return (a*b)//gcd(a,b)

def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    res = 0
    m = 0
    for i in range(n):
        l_m = A[0]
        r_m = A[n-1]
        if(i!=0 and i!=n-1):
            for j in range(1,i):
                l_m = gcd(l_m,A[j])

            for j in range(n-1,i,-1):
                r_m = gcd(r_m,A[j])
            res = max(res,gcd(l_m,r_m))
        else:
            if(i==0):
                for j in range(1,n-1):
                    r_m = gcd(r_m,A[j])
                res = max(res,r_m)
            else:
                for j in range(1,n-1):
                    l_m = gcd(l_m,A[j])
                res = max(res,l_m)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import math
def gcd(a,b):
    return b if not a%b else gcd(b,a%b)
def lcm(a,b):
    return (a*b)//gcd(a,b)

def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    res = 0
    m = 0
    for i in range(n):
        l_m = A[0]
        r_m = A[n-1]
        if(i!=0 and i!=n-1):
            for j in range(1,i):
                l_m = gcd(l_m,A[j])

            for j in range(n-1,i,-1):
                r_m = gcd(r_m,A[j])
            res = max(res,gcd(l_m,r_m))
        else:
            if(i==0):
                for j in range(1,n-1):
                    r_m = gcd(r_m,A[j])
                res = max(res,r_m)
            else:
                for j in range(1,n-1):
                    l_m = gcd(l_m,A[j])
                res = max(res,l_m)
    print(res)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import math, copy

def all_gcd(l):
    a = l[0]
    for i in range(1,len(l)):
        b = l[i]
        a = math.gcd(a, b)
    return a

max_gcd = 0
for n in A:
    copied_A = copy.copy(A)
    copied_A.remove(n)
    max_gcd = max(max_gcd, all_gcd(copied_A)) 

print(max_gcd)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
from functools import reduce
ans=0
def gcd(numbers):
  return reduce(math.gcd, numbers)
import itertools
l=list(map(int, input().split()))
if len(l)==1:
  print(l[0])
  exit()
elif len(l)==2:
  print(max(l))
  exit()
else: 
  for v in itertools.combinations(l, len(l)-1):
    ans=max(ans, gcd(v))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
ans=reduce(gcd,a[1:])
ans=max(ans,reduce(gcd,a[:n-1]))
for i in range(1,n-1):
  ans=max(gcd(reduce(gcd,a[:i]),reduce(gcd,a[i+1:])),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
gc=reduce(gcd,a)
for i in range(n):
  a[i]//=gc
ans=reduce(gcd,a[1:])
ans=max(ans,reduce(gcd,a[:n-1]))
for i in range(1,n-1):
  ans=max(gcd(reduce(gcd,a[:i]),reduce(gcd,a[i+1:])),ans)
print(ans*gc)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
gc=reduce(gcd,a)
for i in range(n):
  a[i]//=gc
ans=0
for _ in range(n):
  b=a.pop()
  ans=max(reduce(gcd,a),ans)
  a=[b]+a
print(ans*gc)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    N = ii()
    A = list(mi())
    d = defaultdict(int)
    ans = 1

    for a in A:
        for v in make_divisors(a):
            d[v] += 1

    for k, v in d.items():
        if v >= N-1:
            ans = max(ans, k)

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import lru_cache


@lru_cache(maxsize=None)
def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


@lru_cache(maxsize=None)
def lcm(a, b):
    """
    aとbの最小公倍数を計算する
    """
    from math import gcd

    return a * b // gcd(a, b)


N = int(input())
A = tuple(map(int, input().split(' ')))

counter = Counter()
for a in A:
    for d in get_dividers(a):
        counter[d] += 1

ans = 1
candidates = []
for key, value in counter.items():
    if value == N:
        ans = lcm(ans, key)
    elif value == N - 1:
        candidates.append(key)

if candidates:
    ans = max([lcm(ans, c) for c in candidates])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


def lcm(a, b):
    """
    aとbの最小公倍数を計算する
    """
    from math import gcd

    return a * b // gcd(a, b)


N = int(input())
A = tuple(map(int, input().split(' ')))

counter = Counter()
for a in A:
    for d in get_dividers(a):
        counter[d] += 1

ans = 1
candidates = []
for key, value in counter.items():
    if value == N:
        ans = lcm(ans, key)
    elif value == N - 1:
        candidates.append(key)

if candidates:
    ans = max([lcm(ans, c) for c in candidates])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
inf=0
def segtree(a): #RMQ(Range Minimum Query)
    #bi=高さ　bi2=最下段の個数
    global bi 
    bi=math.ceil(math.log2(len(a)))+1
    global bi2
    bi2=2**(bi-1)
    seg=[inf]*(2*bi2-1)
    for i in range(len(a)):
        seg[bi2+i-1]=a[i]
    for i in range(bi-1):
        for j in range(2**(bi-i-2)):
            b=2**(bi-i-2)-1+j
            seg[b]=math.gcd(seg[2*b+1],seg[2*b+2])
    return seg

def seg_update(loc,val): #locの値をvalueに更新
    loc+=bi2-1
    seg[loc]=val
    while True:
        seg[loc]=math.gcd(val,seg[loc])
        if loc==0:
            break
        loc=(loc-1)//2

def seg_find(l,r,tmp=0): #[l,r)の最小値を求める
    a=bi-math.ceil(math.log2(tmp+2))+1
    nl=2**(a-1)*(tmp-(2**(bi-a))+1)
    nr=nl+2**(a-1)
    if nr<=l or nl>=r:
        return inf
    elif l<=nl and nr<=r:
        return seg[tmp]
    else:
        return math.gcd(seg_find(l,r,tmp*2+1),seg_find(l,r,tmp*2+2))

n=int(input())
seg=segtree(list(map(int,input().split())))
ans=0
for i in range(n):
    ans=max(ans,math.gcd(seg_find(0,i),seg_find(i+1,n)))
print(ans)

Submission status: Time Limit Exceeded

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

import math
from functools import reduce

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

maxgcd = 1
for i in range(N):
    if N == 2:
        gcd = A[i]
    else:
        gcd = reduce(math.gcd, [A[j] for j in range(N) if j != i])
    if gcd > maxgcd:
        maxgcd = gcd

print(maxgcd)

Submission status: Time Limit Exceeded

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

import math
from functools import reduce

# 最大公約数（リスト引数）
def GCD_list(numbers):
    return reduce(math.gcd, numbers)


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

maxgcd = 1
for i in range(N):
    B = [A[j] for j in range(N) if j != i]
    if len(B) > 1:
        gcd = GCD_list(B)
    else:
        gcd = B[0]
    if gcd > maxgcd:
        maxgcd = gcd

print(maxgcd)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
def main():
    n, *a = map(int, read().split())

    if n == 1:
        print(a[0])
        sys.exit()
    if n == 2:
        print(max(a))
        sys.exit()

    from math import sqrt
    from math import ceil
    maxa = max(a)
    maxa2 = ceil(sqrt(maxa))
    maxa2 = max(6, maxa2)  # maxa2が6未満だとエラーになる
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    prime_list = [i for i, b in enumerate(p) if b]

    r = 1
    jo = []
    for pre in prime_list:
        if all([ae == 1 for ae in a]):
            break
        while True:
            c = [ae % pre == 0 for ae in a]
            if all(c):
                r *= pre
                a = [ae // pre for ae in a]
            else:
                if c.count(0) == 1:
                    r *= pre
                    jo.append(pre)
                    a[c.index(0)] *= pre
                    a = [ae // pre for ae in a]
                else:
                    break
    jo.sort()
    lenjo = len(jo)
    for joe in jo[:lenjo - 1]:
        r = r // joe
    print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


import math
from functools import reduce
def gcd(numbers):
  return reduce (math.gcd, numbers)


ans = 0
a = list(map(int, input().split()))
for i in range(n):
  c = a[i]
  a.remove(c)
  ans = max(ans, gcd(a))
  a.insert(i, c)
#print(a)
  

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


import math
from functools import reduce
def gcd(numbers):
  return reduce (math.gcd, numbers)


ans = 0
a = list(map(int, input().split()))
for i in range(n):
  c = a[i]
  a.remove(c)
  ans = max(ans, gcd(a))
  a.insert(i,c)
  

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


import math
from functools import reduce
def gcd(numbers):
  return reduce (math.gcd, numbers)


res = []
a = list(map(int, input().split()))
for i in range(n):
  c = a[i]
  a.remove(c)
  res.append(gcd(a))
  a.insert(i,c)
  
ans = max(res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

ans = 0
for i in range(n):
    A2 = A.copy()
    del A2[i]
    x = A2[0]
    for i in range(1, n - 1):
        x = math.gcd(x, A2[i])
    ans = max(ans, x)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Segment tree (GCD)
from fractions import gcd


class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def query(self, start, stop):
        result = 0
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = gcd(result, self._data[l])
            if r & 1 == 0:
                result = gcd(result, self._data[r - 1])
            l = l // 2
            r = (r - 1) // 2
        return result


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

st = SegmentTree(N)
st.update_all(A)

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, st.query(0, N - 1))
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

ans = 1

from math import gcd

for i in range(n):
    tmp = -1
    for j in range(n):
        if i != j:
            if tmp == -1:
                tmp = a[j]
            else:
                tmp = gcd(tmp, a[j])
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

max = 0
for i in range(n):
	if gcd_list(a[:i]+a[i+1:]) >= max:
		max = gcd_list(a[:i]+a[i+1:])
print(max)

Submission status: Time Limit Exceeded

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

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

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

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

for i in range(N):
    a = A.pop(i)
    ans.append(gcd_list(A))
    A.insert(i,a)
print(max(ans))

Submission status: Time Limit Exceeded

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

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

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

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

for i in range(N):
    B = copy.deepcopy(A)
    B.pop(i)
    ans.append(gcd_list(B))
print(max(ans))

Submission status: Time Limit Exceeded

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

def lcm_1(X,Y):
    return math.gcd(X,Y)

def lcm_2(L):
    for i in range(len(L)-1):
        y=L[i+1]
        if i ==0:
            x=L[0]
        x=lcm_1(x,y)
    return x

if n==2:
    print(max(l1))
else:
    l2=[]
    for i in range(n):
        l3=[]
        for j in range(n):
            if i!=j:
                l3.append(l1[j])
        l2.append(lcm_2(l3))
    print(max(l2))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
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(reverse=True)
    return divisors

def make_codivisors(n):
    divisors = []
    n0divisors = make_divisors(n[0])
    n0len = len(n0divisors)
    for i in n0divisors:
        for j in range(1, len(n)):
            if n[j] % i != 0:
                break
            if j == len(n)-1:
                return i
                #divisors.append(i)
            
    #divisors.sort()
    #return divisors
if n == 2:
  print(max(a))
  quit()
  
for i in range(n):
  lista= a[:i]+a[i+1:]
  temp = make_codivisors(lista)
  #print(temp)
  ans = max(ans, temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
	a,b=max(a,b),min(a,b)
	return a if b==0 else gcd(b,a%b)
def GCD(t):
	if len(t)==0:
		return 0
	g=t[0]
	for i in t[1:]:
		g=gcd(g,i)
	return g

n=int(input())
a=list(map(int,input().split()))
m=1
for i in range(n):
	l=GCD(a[:i])
	r=GCD(a[i+1:])
	m=max(gcd(l,r),m)
print(m)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
	a,b=max(a,b),min(a,b)
	return a if b==0 else gcd(b,a%b)
def GCD(t):
	g=t[0]
	for i in t[1:]:
		g=gcd(g,i)
	return g
n=int(input())
a=list(map(int,input().split()))
m=1
for i in range(n):
	t=a[:i]+a[i+1:]
	m=max(GCD(t),m)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import collections

def gcd(u,v):
	if v:
		return gcd(v, u % v)
	else:
		return u

n = int(raw_input())
elems = map(int , raw_input().split(' '))
dpp = [ None ] * len(elems)
dps = [ None ] * len(elems)
for i in range(len(elems)): dpp[i] = reduce(gcd, elems[:i+1])
for i in range(len(elems)): dps[len(elems) - 1 - i] = reduce(gcd, elems[- i - 1:])

r = 0
for i in range(len(elems)):
	u,v = dpp[i-1] if i-1 >= 0 else -1, dps[i+1] if i+1 < len(elems) else -1
	r  = max(r, gcd(u,v) if u != -1 and v != -1 else max(u,v))
print r

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

div1 = set(make_divisors(a[0]))
div2 = set(make_divisors(a[1]))
common = div1 | div2

cnt = defaultdict(int)
for i in range(n):
    for j in common:
        if a[i] % j == 0:
            cnt[j] += 1

for k, v in sorted(cnt.items(), reverse=True):
    if v == n or v == n-1:
        print(k)
        exit()

Submission status: Time Limit Exceeded

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

class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)#basementで初期化
 
        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]
 
        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])
 
    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])
 
    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res
 

n=int(input())
a=list(map(int,input().split()))
seg=SegTree(a,gcd,0)
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:
from fractions import gcd

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1
    return pf_cnt


def main():
    n = int(input())
    al = list(map(int, input().split()))

    # al_fac = [0]*n
    for i, a in enumerate(al):
        fac = factorization(a)
        # al_fac[i] = fac

    gcd_l = [1]*n
    gcd_r = [1]*n

    gcd_l[0] = al[0]
    gcd_r[-1] = al[-1]

    for i in range(1,n):
        next_l = al[i]
        gcd_l[i] = gcd(next_l, gcd_l[i-1])

        next_r = al[n-i-1]
        gcd_r[n-i-1] = gcd(next_r, gcd_r[n-i])


    ans = max(gcd_r[1], gcd_l[n-2])
    for i in range(1,n-1):
        curr_gcd = gcd(gcd_l[i-1], gcd_r[i+1])
        ans = max(ans, curr_gcd)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1
    return pf_cnt


def main():
    n = int(input())
    al = list(map(int, input().split()))

    al_fac = [0]*n
    for i, a in enumerate(al):
        fac = factorization(a)
        al_fac[i] = fac
        
    gcd_l = [1]*n
    gcd_r = [1]*n

    gcd_l[0] = al[0]
    gcd_r[-1] = al[-1]

    for i in range(1,n):
        next_l = al[i]
        gcd_l[i] = gcd(next_l, gcd_l[i-1])

        next_r = al[n-i-1]
        gcd_r[n-i-1] = gcd(next_r, gcd_r[n-i])


    ans = max(gcd_r[1], gcd_l[n-2])
    for i in range(1,n-1):
        curr_gcd = gcd(gcd_l[i-1], gcd_r[i+1])
        ans = max(ans, curr_gcd)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1
    return pf_cnt


def main():
    n = int(input())
    al = list(map(int, input().split()))

    al_fac = [0]*n
    for i, a in enumerate(al):
        fac = factorization(a)
        al_fac[i] = fac

    gcd_l = [1]*n
    gcd_r = [1]*n

    gcd_l[0] = al_fac[0]
    gcd_r[-1] = al_fac[-1]

    for i in range(1,n):
        next_l = al_fac[i]
        next_l_gcd = {1:1}
        for prime,cnt in next_l.items():
            if prime in gcd_l[i-1]:
                next_l_gcd[prime] = min(cnt, gcd_l[i-1][prime])
        gcd_l[i] = next_l_gcd

        next_r = al_fac[n-i-1]
        next_r_gcd = {1:1}
        for prime,cnt in next_r.items():
            if prime in gcd_r[n-i]:
                next_r_gcd[prime] = min(cnt, gcd_r[n-i][prime])
        gcd_r[n-i-1] = next_r_gcd

    ans = 1
    for i in range(1,n-1):
        curr_gcd = 1
        for prime,cnt in gcd_l[i-1].items():
            if prime in gcd_r[i+1]:
                min_cnt = min(cnt, gcd_r[i+1][prime])
                curr_gcd *= prime**min_cnt
        ans = max(ans, curr_gcd)


    # i = 0
    curr_gcd = 1
    for prime,cnt in gcd_r[1].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

    # i = n-1
    curr_gcd = 1
    for prime,cnt in gcd_l[n-2].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

    # print(al_fac)
    # print(gcd_l)
    # print(gcd_r)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt

def main():
    n = int(input())
    al = list(map(int, input().split()))

    al_fac = []
    for a in al:
        fac = factorization(a)
        al_fac.append(fac)

    gcd_l = [1]*n
    gcd_r = [1]*n

    gcd_l[0] = al_fac[0]
    gcd_r[-1] = al_fac[-1]

    for i in range(1,n):
        next_l = al_fac[i]
        next_l_gcd = {1:1}
        for prime,cnt in next_l.items():
            if prime in gcd_l[i-1]:
                next_l_gcd[prime] = min(cnt, gcd_l[i-1][prime])
        gcd_l[i] = next_l_gcd

        next_r = al_fac[n-i-1]
        next_r_gcd = {1:1}
        for prime,cnt in next_r.items():
            if prime in gcd_r[n-i]:
                next_r_gcd[prime] = min(cnt, gcd_r[n-i][prime])
        gcd_r[n-i-1] = next_r_gcd

    ans = 1
    for i in range(1,n-1):
        curr_gcd = 1
        for prime,cnt in gcd_l[i-1].items():
            if prime in gcd_r[i+1]:
                min_cnt = min(cnt, gcd_r[i+1][prime])
                curr_gcd *= prime**min_cnt
        ans = max(ans, curr_gcd)


    # i = 0
    curr_gcd = 1
    for prime,cnt in gcd_r[1].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

    # i = n-1
    curr_gcd = 1
    for prime,cnt in gcd_l[n-2].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

    # print(al_fac)
    # print(gcd_l)
    # print(gcd_r)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt


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

al_fac = []
for a in al:
    fac = factorization(a)
    al_fac.append(fac)

gcd_l = [1]*n
gcd_r = [1]*n

gcd_l[0] = al_fac[0]
gcd_r[-1] = al_fac[-1]

for i in range(1,n):
    next_l = al_fac[i]
    next_l_gcd = {1:1}
    for prime,cnt in next_l.items():
        if prime in gcd_l[i-1]:
            next_l_gcd[prime] = min(cnt, gcd_l[i-1][prime])
    gcd_l[i] = next_l_gcd

    next_r = al_fac[n-i-1]
    next_r_gcd = {1:1}
    for prime,cnt in next_r.items():
        if prime in gcd_r[n-i]:
            next_r_gcd[prime] = min(cnt, gcd_r[n-i][prime])
    gcd_r[n-i-1] = next_r_gcd

ans = 1
for i in range(1,n-1):
    curr_gcd = 1
    for prime,cnt in gcd_l[i-1].items():
        if prime in gcd_r[i+1]:
            min_cnt = min(cnt, gcd_r[i+1][prime])
            curr_gcd *= prime**min_cnt
    ans = max(ans, curr_gcd)


# i = 0
curr_gcd = 1
for prime,cnt in gcd_r[1].items():
    curr_gcd *= (prime**cnt)
ans = max(ans, curr_gcd)

# i = n-1
curr_gcd = 1
for prime,cnt in gcd_l[n-2].items():
    curr_gcd *= (prime**cnt)
ans = max(ans, curr_gcd)

# print(al_fac)
# print(gcd_l)
# print(gcd_r)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
#import math
import fractions
from functools import reduce
import copy

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

N=int(input())
AList=list(map(int, input().split()))
SubList=AList.copy()
ANS=0
for i in range(N):
    AList=SubList.copy()
    del AList[i]
    ANS=max(gcd_list(AList),ANS)
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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

for i in a:
    y.extend(make_divisors(i))

C = dict(Counter(y))
c = sorted(C.items(), key=lambda x: x[1], reverse=True)

for j in c:
    if j[0]!=1:
        if j[1]+1 == n or j[1] == n:
            ans = max(ans,j[0])

print(ans)

Submission status: Time Limit Exceeded

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

def f(X):
  p = X[0]
  for i in range(1,len(X)):
    p = gcd(p,X[i])
  return(p)  
  
ans = 1
for i in range(n):
  X = A
  X = list(A)
  X.pop(i)
  ans = max(ans,f(X))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

N =int(input())
arr = list(map(int, input().split()))
dic = defaultdict(int)

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

    for l in range(len(divisors)):
        dic[divisors[l]] += 1

ans = 0
for i in dic:
    if dic[i] >= N-1:
        ans = max(ans,i)

print(ans)