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:
from fractions import gcd

class SegmentTree:
    """Segment Tree

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

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

    def query(self, l, r):
        """区間クエリの計算 O(logN)

        Args:
            l (int): 区間の左端
            r (int): 区間の右端
        
        Returns:
            int: [l, r)についての区間クエリ
        """
        if r <= l:
            return self.ide_ele
        
        l += self.num - 1
        r += self.num - 2
        res = self.ide_ele

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

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

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

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


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

st = SegmentTree(a)

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

class SegmentTree:
    """Segment Tree

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

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

    def query(self, l, r):
        """区間クエリの計算 O(logN)

        Args:
            l (int): 区間の左端
            r (int): 区間の右端
        
        Returns:
            int: [l, r)についての区間クエリ
        """
        if r <= l:
            return self.ide_ele
        
        l += self.num - 1
        r += self.num - 2
        res = self.ide_ele

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

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

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

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


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

st = SegmentTree(a)

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

class SegmentTree:
    """Segment Tree

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

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

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

        Args:
            a (int): 要求区間の左端
            b (int): 要求区間の右端
            k (int): 
            l (int): 対象区間の左端
            r (int): 対象区間の右端
        
        Returns:
            int: [a, b)についての区間クエリ
        """

        if r < 0:
            r = self.num
        
        if r <= a or b <= l:
            return self.ide_ele
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, 2*k+1, l, (l+r)//2)
            vr = self.query(a, b, 2*k+2, (l+r)//2, r)
            return self.st_func(vl, vr)

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

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

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


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

st = SegmentTree(a)

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

class SegmentTree:
    """Segment Tree

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

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

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

        Args:
            a (int): 要求区間の左端
            b (int): 要求区間の右端
            k (int): 
            l (int): 対象区間の左端
            r (int): 対象区間の右端
        
        Returns:
            int: [a, b)についての区間クエリ
        """

        if r < 0:
            r = self.num
        
        if r <= a or b <= l:
            return self.ide_ele
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, 2*k+1, l, (l+r)//2)
            vr = self.query(a, b, 2*k+2, (l+r)//2, r)
            return self.st_func(vl, vr)

        """
        if r <= l:
            return self.ide_ele
        
        l += self.num - 1
        r += self.num - 2
        res = self.ide_ele

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

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

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

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


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

st = SegmentTree(a)

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline

    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]=gcd(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] = gcd(seg[k*2+1],seg[k*2+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 = gcd(res,seg[p])
            if q&1 == 1:
                res = gcd(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = gcd(res,seg[p])
        else:
            res = gcd(gcd(res,seg[p]),seg[q])
        return res



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

    #####単位元######
    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,gcd(query(0,i),query(i+1,n)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
最大公約数をもっとも落としている数Xを削る（＝見ないことにする）、という発想に置き換える。
方針１：
Xを特定する。
どうやって特定する？
各Aを素因数分解する。このとき、他の

方針２：
約数をカウントする。すべてのAの約数をカウントして総和する。
このとき、カウントがN個になる約数は初期状態での公約数である。
一方で、カウントがN-1個の約数は、その約数をもたない数が一つだけ存在するということなので、
そのような数Aを削ったときに、公約数になる。
したがって、カウントがN-1個以上の約数のうち最大のものが、数Xを削ったときの最大公約数である。
問題はどうやって約数をカウントするかだ。愚直にやるとO(N√max(A))かかるため間に合わない。
ただ、約数の数自体はせいぜい1000個くらいのはず。いったん素因数分解してから、各素因数を何個累乗させるかで考えればよいか。
"""
def main():
    from collections import Counter
    N = int(input())
    A = list(map(int,input().split()))
    count = {}

    for a in A:
        tmp = []
        d = 2
        while d*d <= a:
            while a%d == 0:
                tmp.append(d)
                a //= d
            d += 1
        if a != 1:
            tmp.append(a)
        divides = [1]
        for k,v in Counter(tmp).items():
            M = len(divides)
            for i in range(1,v+1):
                for j in range(M):
                    divides.append(divides[j]*pow(k,i))
        
        for d in divides:
            if d not in count:
                count[d] = 0
            count[d] += 1

    ans = 0
    for k,v in count.items():
        if v >= N-1:
            ans = max(ans,k)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
"""
最大公約数をもっとも落としている数Xを削る（＝見ないことにする）、という発想に置き換える。
方針１：
Xを特定する。
どうやって特定する？
各Aを素因数分解する。このとき、他の

方針２：
約数をカウントする。すべてのAの約数をカウントして総和する。
このとき、カウントがN個になる約数は初期状態での公約数である。
一方で、カウントがN-1個の約数は、その約数をもたない数が一つだけ存在するということなので、
そのような数Aを削ったときに、公約数になる。
したがって、カウントがN-1個以上の約数のうち最大のものが、数Xを削ったときの最大公約数である。
問題はどうやって約数をカウントするかだ。愚直にやるとO(N√max(A))かかるため間に合わない。
ただ、約数の数自体はせいぜい1000個くらいのはず。いったん素因数分解してから、各素因数を何個累乗させるかで考えればよいか。
"""

from collections import Counter

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

for a in A:
    tmp = []
    d = 2
    while d*d <= a:
        while a%d == 0:
            tmp.append(d)
            a //= d
        d += 1
    if a != 1:
        tmp.append(a)
    divides = [1]
    for k,v in Counter(tmp).items():
        M = len(divides)
        for i in range(1,v+1):
            for j in range(M):
                divides.append(divides[j]*pow(k,i))
    
    for d in divides:
        if d not in count:
            count[d] = 0
        count[d] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# author:  Taichicchi
# created: 16.09.2020 22:49:18

import sys

from math import gcd

N = input()

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

m = 0

for i, a in enumerate(A_base):
    A = A_base.copy()
    A.remove(a)
    g = A[0]
    for l in A:
        g = gcd(g, l)
    m = max(m, g)
print(m)

Submission status: Time Limit Exceeded

Solution code:
"""
最大公約数を最も落とす原因になっている整数を特定したい。
"""
from collections import Counter

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

for a in A:
    d = 1
    while d*d < a:
        if a%d == 0:
            if d not in count:
                count[d] = 0
            if a//d not in count:
                count[a//d] = 0
            count[d] += 1
            count[a//d] += 1
        d += 1
    if d**2 == a:
        if d not in count:
            count[d] = 0
        count[d] += 1

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

Submission status: Time Limit Exceeded

Solution code:
"""
最大公約数を最も落とす原因になっている整数を特定したい。
"""
from collections import Counter

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

for a in A:
    tmp = []
    d = 1
    while d*d < a:
        if a%d == 0:
            tmp.append(d)
            tmp.append(a//d)
        d += 1
    if d**2 == a:
        tmp.append(d)
    count += Counter(tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

ans = 0
for i in range(n):
  ans = max(ans, gcd(a[:i]+a[i+1:]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from math import gcd

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


@lru_cache(None)
def func(*x):
    n = len(x)
    if n == 2:
        return gcd(x[0], x[1])
    elif n == 1:
        return x[0]
    return gcd(func(*x[:n//2]), func(*x[n//2:]))


ans = 0
for i in range(N):
    tmp = A[i]
    A[i] = A[i+1 if i < N-1 else 0]
    ans = max(ans, func(*A))
    A[i] = tmp
print(ans)

Submission status: Time Limit Exceeded

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

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


#これだとTLEする
ans=0
for i in range(N):
	temp=0
	for idx, a in enumerate(A):
		if idx==i:
			continue
		temp=gcd(temp, a)
	ans=max(ans,temp)
print(ans)

Submission status: Time Limit Exceeded

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

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


ans=0
for i in range(N):
	temp=0
	for idx, a in enumerate(A):
		if idx==i:
			continue
		temp=gcd(temp, a)
	ans=max(ans,temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#/usr/bin/env python
from functools import *
from math import *

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

gcds = []
for i in range(n):
    l = a[:i] 
    r = a[i+1:]
    if len(l) == 0:
        gl = 0 
    else:
        gl = reduce(gcd, l)

    if len(r) == 0:
        gr = 0 
    else:
        gr = reduce(gcd, r)

    g = gcd(gl, gr) 
    gcds.append(g)

print(max(gcds))

Submission status: Time Limit Exceeded

Solution code:
#/usr/bin/env python
from functools import *
from math import *

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

gcds = []
for i in range(n):
    tmp = a[:i] + a[i+1:]
    g = reduce(gcd, tmp)
    gcds.append(g)

print(max(gcds))

Submission status: Time Limit Exceeded

Solution code:
import fractions
#####segfunc######
def segfunc(x,y):
    return fractions.gcd(x,y)

class SegmentTree():
    def __init__(self,A,n,ide_ele):
        self.ide_ele=ide_ele
        self.num =2**(n-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=A[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=segfunc(self.seg[2*i+1],self.seg[2*i+2])

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

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

N = int(input())
A = list(map(int,input().split()))
ST = SegmentTree(A,N,0)
out = 1
for i in range(N):
    X = ST.query(0,i)
    Y = ST.query(i+1,N)
    out = max(out,fractions.gcd(X,Y))
print(out)

Submission status: Time Limit Exceeded

Solution code:
# 演算内容、単位元の必要に応じて(コンストラクタ参照)
import math

# セグメント木のクラス
# 後日遅延評価なども取り入れていきたいが、とりあえず
# 基本的なところだけを分かりやすい形で組んでみたもの
# length:データ部の長さ depth:構造全体の深さ
# offset:上位構造の長さ tree:全体リスト

class Segment_Tree:
    # コンストラクタ。リストもしくは要素数にて初期化。
    # デフォルトでは最小値を求めるが、op(operation=演算内容、デフォルトは最小値)、
    # ie(identity element単位元)を指定することも可能(f.e: op=operator.add, ie=0)
    def __init__(self, arg1, op=lambda x, y:x if x < y else y, ie=math.inf):
        self.op = op
        self.ie = ie

        if type(arg1) == int:
            default_list = []
            self.length = arg1
        else:
            default_list = list(arg1)
            self.length = len(arg1)

        # 全体の深さ、上位構造分のオフセットを求める
        self.depth = 0
        self.offset = 1
        while self.offset < self.length:
            self.depth += 1
            self.offset *= 2

        # 木の初期化。構造は1-indexedで使用していくことにする
        self.tree = [self.ie] * (self.offset * 2)
        if default_list:
            self.tree[self.offset:self.offset+self.length] = default_list
            self.refresh()

    # 全体の再計算(愚直に……)
    def refresh(self):
        for idx in range(self.offset - 1, 0, -1):
            self.tree[idx] = self.op(self.tree[idx*2], self.tree[idx*2+1])

    # 値のセット、及び関連する部分の再計算
    def set(self, idx, value):
        idx = idx + self.offset
        self.tree[idx] = value
        while idx > 1:
            idx //= 2
            old = self.tree[idx]
            new = self.op(self.tree[idx*2], self.tree[idx*2+1])
            if old == new:
                break
            else:
                self.tree[idx] = new
        
    # 半開区間[left, right)における欲しい値(アレっすよ、アレ)を求める
    def find(self, left, right):
        # 区間がおかしなときは、エラー代わりに単位元でも返しておく
        if left >= right:
            return self.ie
        
        # 1(tree全体を含むもの)から探索開始。キューには探索対象の深さも一緒に入れておく
        result = self.ie
        queue = [(1, 0)]
        while len(queue) > 0:
            node, node_depth = queue.pop()

            # 対象ノードが受け持つ区間を求める
            width = 2 ** (self.depth - node_depth)
            idx_in_row = node - 2 ** (node_depth)
            node_left = width * idx_in_row
            node_right = node_left + width

            # 範囲外なら探索終了
            if node_right <= left or right <= node_left:
                continue

            # はみ出てたら子をキューに追加
            if node_left < left or right < node_right:
                queue.append((node * 2, node_depth + 1))
                queue.append((node * 2 + 1, node_depth + 1))
                continue

            # ここまで来たのならノードの情報は探索範囲に包含されている
            result = self.op(result, self.tree[node])
        
        return result
    
    def get(self, x):
        return self.tree[x+self.offset]

    def find_all(self):
        return self.tree[1]
    
    def show_tree(self):
        print(self.tree)


def main():
    N = int(input())
    n_list = list(map(int, input().split()))
    st = Segment_Tree(n_list, op=lambda x, y:math.gcd(x, y), ie=0)
    result = 1
    for i in range(N):
        g1 = st.find(0, i)
        g2 = st.find(i+1, N)
        result = max(result, math.gcd(g1, g2))
    
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#ABC125C
N=int(input())
A=list(map(int,input().split()))
def gcd(a,b):
    if a>b:a,b=b,a
    while a%b:
        a,b=b,a%b
    return b
def gcd_list(A):
    if len(A)<2:return A[0]
    res=gcd(A[0],A[1])
    for i in range(len(A)-2):
        res=gcd(res,A[i+2])
    return res
res=0
for i in range(N):
    Ai=A[:]
    Ai.pop(i)
    res=max(res,gcd_list(Ai))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from copy import copy
#================================================
def GCD(A):
    n=len(A)
    if n==1:
        return A[0]

    return gcd(GCD(A[:n//2]),GCD(A[n//2:]))
#================================================
N=int(input())
A=list(map(int,input().split()))
B=copy(A)

M=0
for i in range(N):
    B[i]=0
    M=max(M,GCD(B))
    B[i]=A[i]

print(M)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

def gcd(numbers):
    if len(numbers)>=2:
        return reduce(math.gcd,numbers)
    else:
        return math.gcd(0,*numbers)


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

ans = []

for i in range(N):
    if i == 0:
        ans.append(gcd(A[i+1:]))
    elif i == N-1:
        ans.append(gcd(A[:N-1]))
    else:#N=1からN-2
        ans.append(math.gcd(gcd(A[:i]),gcd(A[i+1:])))
#print(ans)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import math

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

# x=math.gcd(a[0],a[1])
# for i in range(1,n):
#     x=math.gcd(x,a[i])

max=0
for i in range(n):
    if i==n-1:
        s=a[i-1]
    else:
        s=a[i+1]

    for j in range(n):
            if j!=i:
                s=math.gcd(s,a[j])
    else:
        if max<s:
            max=s    

print(max)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
j = 1
for i in range(max(a),1,-1):
    num = 0
    for h in a:
        if h%i == 0:
            num += 1
    if num == n or num == n-1:
        j = i
        break
print(j)

Submission status: Time Limit Exceeded

Solution code:
import math
import functools
import copy

N=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
ans=list()

for i in range(N):
  del b[i]
  gcd=functools.reduce(math.gcd,b)
  ans.append(gcd)
  b.insert(i,a[i])

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
import functools
import copy

N=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
ans=list()

for i in range(len(a)):
  del b[i]
  gcd=functools.reduce(math.gcd,b)
  ans.append(gcd)
  b.insert(i,a[i])

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import accumulate

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

g = []
gcd = []

for i in range(n):
  r = a[i]
  a.remove(r)
  gcd = accumulate(a, math.gcd)
  g.append(min(gcd))
  a.insert(i, r)

print(max(g))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
inf=float("inf")
def gcd(a,b):
    if a==inf:return b
    if b==inf:return a
    if b==0: return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)

class segtree:
    def __init__(self,n,operator,identity):
        """
        n: データ配列のサイズ
        operator: 演算子。関数。minとか。
        identity: 単位元。minだったらinf。
        """
        nb=bin(n)[2:] #2進数に変換し、最初の"0b"を除く
        bc=sum([int(digit) for digit in nb]) #これが1だったら2の累乗形
        if bc==1:
            self.num_end_leaves= 2**(len(nb)-1)
        else:
            self.num_end_leaves= 2**(len(nb))

        self.array= [identity for i in range(self.num_end_leaves *2)]
        #単位元で初期化。1個多いのは別にええやろ

        self.identity= identity
        self.operator = operator

    def update(self,x,val):
        """
        x: 代入場所
        val: 代入する値
        """
        actual_x= x+self.num_end_leaves-1
        #末端の葉数が32ならば、末端のindexは31から。

        self.array[actual_x] = val  #更新
        while actual_x>0:
            actual_x = (actual_x-1)//2 #親を見る
            self.array[actual_x]= \
            self.operator( self.array[actual_x*2+1], self.array[actual_x*2+2])

    def get(self, q_left, q_right, arr_ind=0, leaf_left=0, depth=0):
        """
        q_left: クエリ区間の左
        q_right: クエリ区間の右(閉区間)
        arr_ind: 木配列のindex. 最初は親なので0
        leaf_left: 葉がカバーしてる範囲の左端
        depth: 木配列の深さ。
        """
        
        width_of_floor = self.num_end_leaves//(2**depth)
        #今の葉のカバー幅(最初は全体(32としよう))

        leaf_right= leaf_left + width_of_floor - 1
        #今の葉のカバー幅の右端

        if (q_right < leaf_left) or (leaf_right < q_left):
            return  self.identity #クエリ領域と葉が関係ないなら単位元を返す

        elif q_left <= leaf_left and leaf_right <= q_right:
            return self.array[arr_ind] #クエリ領域に葉がすっぽり入ってるなら、葉の値を返す

        else: #そうじゃないならば、子を見る
            val_left = self.get(q_left,q_right, 2*arr_ind+1, leaf_left, depth+1)
            val_right = \
            self.get(q_left,q_right, \
            2*arr_ind+2, leaf_left+width_of_floor//2, depth+1)
            return self.operator(val_left,val_right) #子をマージする演算をする。


seg=segtree(n, gcd, float("inf"))
# A=[i for i in range(10)]
for i,num in enumerate(A):  #用意した配列をぶち込む
  seg.update(i,num)
# print(seg.array)
ans=0
for i in range(n):
    seg.update(i,inf)
    ans=max(ans, seg.array[0])
    seg.update(i,A[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import gcd
from functools import reduce

stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


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


n = ni()
A = nl()
ans = 0
for i in range(n):
    tmp = A[:i] + A[i + 1:]
    ans = max(ans, gcd_list(tmp))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
n = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(n):
    tmp = A.copy()
    del tmp[i]
    gcd_num = gcdlist(tmp)
    ans = max(ans, gcd_num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
n = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(n):
    tmp = A.copy()
    tmp.pop(i)
    gcd_num = gcdlist(tmp)
    ans = max(ans, gcd_num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
n = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(n):
    tmp = A.copy()
    tmp.pop(i)
    gcd_num = gcdlist(tmp)
    ans = max(ans, gcd_num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
n=int(input());a=list(map(int,input().split()))
b=copy.deepcopy(a)
count=0
num=0
result=[]
while count < n:
  b[count]= num
  num+=1
  c=copy.deepcopy(b)
  for i in range(1,n):
    c[i] = math.gcd(c[i-1],c[i])
  result.append(c[-1])
  if num==10:
    b[count]=a[count]
    count+=1
    num=0
print(max(result))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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


def gcd(x, y):
    if x < y:
        x, y = y, x
    while y != 0:
        tmp = x % y
        x = y
        y = tmp
    return x


ans = 1
if N == 2:
    print(max(a))
    exit()


for i in range(N):
    if i == 0:
        n = reduce(gcd, a[1:])
    elif i == N-1:
        n = reduce(gcd, a[:i])
    else:
        n = reduce(gcd, a[:i]+a[i+1:])
    ans = max(ans, n)
print(ans)