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: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    def sowa(self, n):
        r = 1
        for k,v in self.division(n):
            t = 1
            for i in range(1,v+1):
                t += math.pow(k, i)
            r *= t
        return r


def main():
    n = I()
    ac = collections.Counter(LI())
    if n == 2:
        return max(ac.keys())
    a = []
    aa = []
    for k,v in ac.items():
        if v > 1:
            aa.append(k)
        else:
            a.append(k)

    tr = -1
    if len(aa) > 0:
        tr = aa[0]
        for k in aa[1:]:
            tr = fractions.gcd(k,tr)

    l = len(a)
    if l < 2:
        return tr
    if l < 3:
        r = 1
        for i in a:
            kr = fractions.gcd(i,tr)
            if r < kr:
                r = kr
        return r

    m = max(a)
    lm = m // (l-1)
    pr = Prime(10**9)
    p = collections.defaultdict(int)

    for b in a:
        r = [1]
        for k, v in pr.division(b):
            for c in r[:]:
                for i in range(1,v+1):
                    t = c*(k**i)
                    if t > lm:
                        break
                    r.append(t)
        for k in r:
            p[k] += 1



    if tr == -1:
        r = 1
        for k,v in p.items():
            if v >= l-1 and r < k:
                r = k
        return r

    r = 1
    for k,v in p.items():
        kk = fractions.gcd(tr,k)
        if v >= l-1 and r < kk:
            r = kk

    return r


print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 27 20:57:32 2019

@author: Yamazaki Kenichi
"""
import sys

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

def eg(x,y):
    if y == 0:
        return x
    x, y = y, x%y
    return eg(x,y)

if N == 2:
    print(max(A[0],A[1]))
    sys.exit()

tmp1 = eg(A[0],eg(A[1],A[2]))
tmp2 = max(eg(A[0],A[1]),eg(A[1],A[2]),eg(A[0],A[2]))

T = [[1,1,1] for i in range(N)]
T[1][0],T[1][1],T[1][2] = tmp1, tmp2, tmp2
for i in range(2,N):
    T[i][0] = eg(T[i-1][0],A[i])
    T[i][1] = T[i-1][0]
    T[i][2] = max(eg(T[i-1][2],A[i]),eg(T[i-1][1],A[i]))
print(max(T[N-1]))

Submission status: Accepted

Solution code:
import fractions
n = int(input())
listA = list(map(int, input().split()))
listA.sort()
if len(listA) < 3:
    print(max(listA))
else:
    minGcd1 = fractions.gcd(listA[0], listA[1])
    minGcd2 = fractions.gcd(listA[1], listA[2])
    minGcd3 = fractions.gcd(listA[0], listA[2])
    ming1 = minGcd1
    maxg1 = 1
    while ming1 > 1:
        count=0
        flag=0
        index1=0
        while index1 < len(listA):
            if listA[index1]%ming1==0:
                pass
            else:
                count+=1
            if count >1:
                flag=1
                break
            index1+=1
        if flag:
            ming1-=1
        else:
            maxg1 = ming1
            break
    ming2 = minGcd2
    maxg2 = 1
    while ming2 > 1:
        count = 0
        flag = 0
        index1 = 0
        while index1 < len(listA):
            if listA[index1] % ming2==0:
                pass
            else:
                count += 1
            if count > 1:
                flag = 1
                break
            index1 += 1
        if flag:
            ming2 -= 1
        else:
            maxg2 = ming2
            break
    ming3 = minGcd3
    maxg3= 1
    while ming3 > 1:
        count = 0
        flag = 0
        index1 = 0
        while index1 < len(listA):
            if listA[index1] % ming3==0:
                pass
            else:
                count += 1
            if count > 1:
                flag = 1
                break
            index1 += 1
        if flag:
            ming3 -= 1
        else:
            maxg3 = ming3

            break
    print(max(maxg1, maxg2, maxg3))

Submission status: Accepted

Solution code:
import math
import numpy as np

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)
    return divisors
  
def set_list(es):
  return len(list(set(es))) == 1
  
n = int(input())
n_list = [int(i) for i in input().split()] 

if set_list(n_list):
    print(n_list[0])
else:
  min1 = min(n_list)
  n_list.remove(min1)
  min2 = min(n_list)
  n_list.append(min1)

  div_list = make_divisors(min1) + make_divisors(min2)
  div_set = set(div_list)
  div_list = sorted(list(div_set))

  k = 0
  length = len(div_set)
  while k < length: 
    s = div_list[length - k - 1]
    count = 0
    j = 0
    for x in n_list:
      if n_list[j] % s == 0:
        count += 1
      j += 1
    if count >= n - 1:
      print(s)
      break
      
    k += 1

Submission status: Accepted

Solution code:
from math import sqrt
from sys import exit
N=int(input())
A=list(map(int,input().split()))

if len(A)==2:
    print(max(A))
    exit()

def gcd(a,b):
    if a<b: a,b=b,a
    if a%b==0: return b
    return gcd(b,a%b)
    
g=gcd(A[0],A[-1])

p=[]

for i in range(1,int(sqrt(g)+1)):
    if g%i==0:
        if i*i==g: p.append(i)
        else: p+=[i,g//i]
        
def ok(n):
    f=False
    for a in A[1:-1]:
        if a%n:
            if f: return False
            f=True
    return True
    
def GCD(L):
    if len(L)==1: return L[0]
    ans=gcd(L[0],L[1])
    if len(L)>2:
        for l in L[2:]:
            ans=gcd(ans,l)
    return ans

p.sort(reverse=True)
for num in p:
    if ok(num):
        ans=num
        break
p1=GCD(A[1:-1])
print(max([ans,gcd(p1,A[0]),gcd(p1,A[-1])]))

Submission status: Accepted

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

def gcd(x, y): 
  
   while(y): 
       x, y = y, x % y 
  
   return x 
  

GG=[0]*N
GG[0]=A[0]
for i in range(1,N):
    GG[i]=gcd(GG[i-1],A[i])

GG2=[0]*N
GG2[-1]=A[-1]

for i in range(2,N+1):
    GG2[-i]=gcd(GG2[-(i-1)],A[-i])

ans=[0]*N

ans[0]=GG2[1]
ans[-1]=GG[N-2]
#print(GG)
#print(GG2)
#print(ans)


temp=ans[0]
for i in range(1,N-1):
    ans[i]=gcd(GG[i-1],GG2[i+1])
    if ans[i]>temp:
        temp=ans[i]
if ans[-1]>temp:
    temp=ans[-1]


print(temp)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
def divi(a, b):
    rem = b % a
    if rem == 0:
        return a
    else:
        return divi(rem, a)
A.sort()
all_d = divi(A[0], A[1])
max_d = max(all_d, max(divi(A[1],A[2]), divi(A[0],A[2]))) if N > 2 else A[1]
for i in range(2,N):
    d = divi(all_d, A[i])
    max_d = divi(max_d, A[i])
    if max_d < all_d:
        max_d = all_d
    all_d = d
print(max_d)

Submission status: Accepted

Solution code:
from collections import*
from functools import*
from fractions import*
def dv(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 Counter(divisors)

n,*a=map(int,open(0).read().split())
if n<1000:
    ans=Counter()
    for i in range(n):
        ans+=dv(a[i])
    l=[]
    for k,v in ans.items():
        if v==n-1 or v==n:
            l.append(k)
    print(max(l))
else:
    print(max(reduce(gcd,a[n//4:]),reduce(gcd,a[:n//4]+a[n//2:]),reduce(gcd,a[:n//2]+a[3*n//4:]),reduce(gcd,a[:3*n//4])))

Submission status: Accepted

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

divsTF = [0]*len(divs)
for i in range(len(divs)):
    j = [1 if a[_] % divs[i] else 0 for _ in range(n) ]

    if sum(j) <= 1:
        divsTF[i] = 1

ans = 1
for i in range(len(divs)):
    if divsTF[i] == 1:
        ans = max(ans,divs[i])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = sorted(list(map(int,input().split())))
arr1 = arr[::-1]
dp = [[0]*2 for i in range(n)]
dp1 = [[0]*2 for i in range(n)]

dp[0][0] = arr[0]
dp[0][1] = arr[1]
dp1[0][0] = arr1[0]
dp1[0][1] = arr1[1]

def gcd(a,b):
    x = max(a,b)
    y = min(a,b)
    if x%y:
        return gcd(y,x%y)
    else:
        return y
for i in range(n-1):
    dp[i+1][0] = gcd(dp[i][0],arr[i+1])
    dp[i+1][1] = max(dp[i][0],gcd(dp[i][1],arr[i+1]))
    dp1[i+1][0] = gcd(dp1[i][0],arr1[i+1])
    dp1[i+1][1] = max(dp1[i][0],gcd(dp1[i][1],arr1[i+1]))
print(max(dp[-1][0],dp[-1][1],dp1[-1][0],dp1[-1][1]))

Submission status: Accepted

Solution code:
from functools import reduce
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
def gcd_list(numbers):
    return reduce(gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
if n == 2:
  print(max(a))
else:
  p = gcd_list(a[:3])
  q = max([gcd(a[0], a[1]), gcd(a[0], a[2]), gcd(a[1], a[2])])
  for i in range(3, n):
    q = max([p, gcd(q, a[i])])
    p = gcd(p, a[i])
    
  print(q)

Submission status: Accepted

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

n = int(input())
vals = [int(x) for x in input().split(" ")]
vals.sort()
vals.reverse()

rewrite = False

minindex = 0

minval = vals[0]
for b in vals[1:]:
    temp = b
    a = minval
    tempmin = minval
    
    minval = gcd(a, b)
    if minval < tempmin:
        minindex = temp

if len(vals) > 2 and vals[1] == minindex:
    # 調整
    v1 = gcd(vals[0], vals[2])
    v2 = gcd(vals[1], vals[2])
    if v1 < v2:
        minindex = vals[0]

if minindex == vals[0]:
    minval = vals[1]
else:
    minval = vals[0]

jump = False

for b in vals[1:]:
    if not jump and b == minindex:
        jump = True
        continue
    a = minval
    minval = gcd(a, b)

print(minval)

Submission status: Accepted

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

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

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)
    return divisors

divisors = list(set(make_divisors(A_list[0]) + make_divisors(A_list[1])))
divisors.sort(reverse=True)

counter = 0
for divisor in divisors:
    for A in A_list:
        if A % divisor != 0:
            counter += 1
        if counter > 1:
            break
    if counter <= 1:
        print(divisor)
        break
    else:
        counter = 0

Submission status: Accepted

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

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

A.sort()

l = [0]
m = A[0]
for i in range(1, N):
    tmp = gcd(m, A[i])
    if tmp < m:
        l.append(i)
    m = tmp
    # print(m)

max_num = m
for l_i in l:
    b = A.copy()
    b.pop(l_i)
    x = b[0]
    for i in range(1, N-1):
        # print("a:", i)
        x = gcd(x, b[i])
    # print(x)
    max_num = max(max_num, x)

print(max_num)

Submission status: Accepted

Solution code:
def gcd(x,y):
	return gcd(y,x%y) if y else x
n,a,b,c=int(input()),list(map(int,input().split())),[],[]
for i in range(n):
	b.append(gcd(b[i-1],a[i-1]) if i else 0)
	c.append(gcd(c[i-1],a[n-i]) if i else 0)
print(max([gcd(b[i],c[n-i-1]) for i in range(n)]))

Submission status: Accepted

Solution code:
def euclidean(x, y):
    b = max(x, y)
    s = min(x, y)
    while True:
        ns = b % s
        if ns == 0:
            return s
        b = s
        s = ns

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

W = set()
for n in range(N):
    if n == 0:
        v = A[n]
    elif n == 1:
        nW = set()
        nW.add(v)
        nW.add(A[n])
        v = euclidean(v, A[n])
        W = nW
    else:
        nW = set()
        nW.add(v)
        for w in W:
            nW.add(euclidean(w, A[n]))
        v = euclidean(v, A[n])
        W = nW
print(max(W))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from functools import reduce


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

def gcd_group(A):
    return reduce(gcd, A)


def solve(N: int, A: "List[int]"):
    left = [A[0]] # A[0]からA[i]までのGCD
    right = [A[N-1]] # A[i]からA[N-1]までのGCD
    for i in range(1, N):
        left.append(gcd(left[-1], A[i]))
        right.append(gcd(right[-1], A[-i-1]))
    right.reverse()

    ret = 0
    for i in range(N):
        if i == 0:
            temp = right[1]
        elif i == N-1:
            temp = left[N-2]
        else:
            temp = gcd(left[i-1], right[i+1])

        if temp > ret:
            ret = temp
    print(ret)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

n = int(input())

a = list(map(int,input().split()))
#
# a = [4,8,12,9,16]


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


gcd_l = [a[0]]
gcd_r = [a[-1]]
for i in range(1,n):
    gcd_l.append(fractions.gcd(gcd_l[i-1],a[i]))
    gcd_r.append(fractions.gcd(gcd_r[i-1],a[-i-1]))

gcd_r.reverse()

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
mae = [a[0]]
for i in range(n-1):
    mae.append(gcd(mae[i],a[i+1]))
ushiro = [a[n-1]]
for i in range(n-1):
    ushiro.append(gcd(ushiro[i],a[n-i-2]))

ans = ushiro[n-2]

for i in range(n-1):
    if i != n-2:
        ans = max(ans,gcd(mae[i],ushiro[n-i-3]))
    else:
        ans = max(ans,mae[n-2])

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int, input().split()))
List1=[0]*n
List1[0]=a[0]
List2=[0]*n
List2[0]=a[-1]
for i in range(1, n):
    List1[i]=gcd(List1[i-1], a[i])
    List2[i]=gcd(List2[i-1], a[-i-1])
ans=List2[-2]
for i in range(1, n-1):
    ans=max(ans, gcd(List1[i-1], List2[n-i-2]))
ans=max(ans,List1[n-2])
print(ans)

Submission status: Accepted

Solution code:
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)
    return divisors

N = int(input())
A = list(map(int, input().split()))
divisors = sorted(make_divisors(A[0]) + make_divisors(A[1]), reverse=True)

ans = 0
for d in divisors:
    ok_cnt = 0
    for a in A:
        if a % d == 0:
            ok_cnt += 1
    if ok_cnt >= N-1:
        ans = d
        break
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import fractions

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


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


def main():
    n = II()
    A = LI()
    A.sort()
    A.reverse()

    pre = [0] * n
    pre[0] = A[0]
    for i in range(1, n):
        pre[i] = gcd(pre[i - 1], A[i])
    res = pre[-1]
    for i in range(n):
        t = pre[i]
        for j in range(i + 2, n):
            t = gcd(t, A[j])
            if t == pre[j - 1]:
                t = -1
                break
        res = max(res, t)

    t = A[1]
    for a in A[1:]:
        t = gcd(t, a)

    return max(res, t)


print(main())

Submission status: Accepted

Solution code:
def divisor(x):
    y = list()
    for i in range(1, int(x ** 0.5 + 1)):
        if x % i == 0:
            y.append(i)
            y.append(x // i)
    return y

n = int(input())
a = list(map(int, input().split()))
a.sort()
d0 = divisor(a[0])
d1 = divisor(a[1])
d = dict.fromkeys(d0 + d1)
ans = 1
for di in sorted(list(d.keys()))[::-1]:
    flag = False
    ans_flag = True
    for ai in a:
        if ai % di != 0:
            if flag:
                ans_flag = False
                break
            else:
                flag = True
    if ans_flag:
        ans = di
        break
print(ans)

Submission status: Accepted

Solution code:
import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()

dp = [[1]*N for i in range(2)]
dp[0][0] = A[0]

a, b = A[0], A[-1]
for i in range(1, N):
    a = fractions.gcd(a, A[i])
    dp[0][i] = a
    b = fractions.gcd(b, A[N-i])
    dp[1][N-i] = b

ans = 1
for i in range(N):
    g = 1
    if i == 0:
        g = dp[1][1]
    elif i == (N-1):
        g = dp[0][-2]
    else:
        g = fractions.gcd(dp[0][i-1], dp[1][i+1])
    if g > ans:
        ans = g
print(ans)

Submission status: Accepted

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

from fractions import gcd

xs1 = []

r = A[0]
for x in A:
    r = gcd(x, r)
    xs1.append(r)

xs2 = []

r = A[-1]
for x in A[::-1]:
    r = gcd(x, r)
    xs2.append(r)

xs2 = xs2[::-1]

#print(xs1)
#print(xs2)

result = max(xs1[-2], xs2[1])

for i in range(N - 2):
    r = gcd(xs1[i], xs2[i + 2])
    result = max(result, r)

print(result)

Submission status: Accepted

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


def gcd(a, b):
    if a < b:
        a, b = b, a
    assert a >= b
    r = a % b
    if r == 0:
        return b
    
    else:
        return gcd(b, r)


gcd_list_l = list()
gcd_list_r = list()

for i in range(0, N):
    if i == 0:
       value = As[i]
    else:
        value = gcd(gcd_list_l[-1], As[i])
    
    gcd_list_l.append(value)

for i in range(N)[::-1]:
    if i == N - 1:
        value = As[i]
    else:
        value = gcd(gcd_list_r[-1], As[i])
    gcd_list_r.append(value)

gcd_list_r.reverse()

# print(gcd_list_l)
# print(gcd_list_r)

ans = 0
for i in range(N):
    if i == 0:
        value = gcd_list_r[i + 1]
    elif i == N - 1:
        value = gcd_list_l[i - 1]
    else:
        value = gcd(gcd_list_l[i - 1], gcd_list_r[i + 1])
    
    ans = max(value, ans)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

l_list = [a_list[i] for i in range(n)]
r_list = [a_list[i] for i in range(n)]
r_list.reverse()

for i in range(1, n):
    l_list[i] = gcd(a_list[i], l_list[i-1])
for i in range(1, n):
    r_list[i] = gcd(r_list[i-1], a_list[n-i-1])

gcd_list = [0]
if n > 2:
    gcd_list = [gcd(l_list[i-1], r_list[n-i-2]) for i in range(1, n-1)]
gcd_0 = r_list[n-2]
gcd_n = l_list[n-2]
ans = max(max(max(gcd_list), gcd_0), gcd_n)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

if N == 2:
    print(max(A))
else:
    a = gcd(A[1], A[2])
    b = gcd(A[0], A[2])
    c = gcd(A[0], A[1])
    mx = max(a, b, c)
    mn = gcd(c, A[2])

    for a in A[3:]:
        new = gcd(mx, a)
        mx = max(new, mn)
        mn = gcd(mn, a)
    print(mx)

Submission status: Accepted

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


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

g_pre = [0] * (n + 1)
for i in range(n):
    g_pre[i] = gcd(g_pre[i - 1], a[i])

g_suf = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    g_suf[i] = gcd(g_suf[i + 1], a[i])

ans = -1

for i in range(n):
    ans = max(ans, gcd(g_pre[i - 1], g_suf[i + 1]))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
def divisors(n):
    div = set()
    A = 1
    while A*A <= n:
        if n%A == 0:
            if A*A == n:
                div.add(A)
            else:
                B = n//A
                div.add(A)
                div.add(B)
        A += 1
    return div
div = list(divisors(A[0]) | divisors(A[1]))
m = 0
for x in div:
    count = 0
    for a in A:
        if a%x != 0:
            count += 1
    if count <= 1:
        m = max(m, x)
print(m)

Submission status: Accepted

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

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

g = [None] * N
grev = [None] * N
g[0] = A[0]
grev[-1] = A[-1]
for i in range(1, N):
    g[i] = gcd(g[i-1], A[i])
    grev[-1-i] = gcd(grev[-i], A[-1-i])
maxgcd = max(grev[1], g[N-2])
for i in range(1, N-1):
    maxgcd = max(maxgcd, gcd(g[i-1], grev[i+1]))
print(maxgcd)

Submission status: Accepted

Solution code:
# coding: utf-8

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

appear_D = {}


def sosuu(n):
    output = []
    for i in range(1, int(pow(n, 0.5))+1):
        if n % i == 0:
            output.append(i)
            if i != n // i:
                output.append(n // i)

    return output


ans_cantdidate = []

min_fst = a[0]
for i in range(n):
    if a[i] < min_fst:
        min_fst = a[i]

min_snd = a[0] if a[0] != min_fst else a[1]
for i in range(n):
    if min_fst < a[i] < min_snd:
        min_snd = a[i]

sosuus = set(sosuu(min_fst)) | set(sosuu(min_snd))
for num in sosuus:
    not_common = 0
    for i in range(n):
        if a[i] % num > 0:
            not_common += 1
        if not_common > 1:
            break
    if not_common < 2:
        ans_cantdidate.append(num)

print(max(ans_cantdidate))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


# globals
inf = float('inf')
N = 0
A = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    forward = [A[0]]
    for a in A[1:]:
        forward.append(gcd(forward[-1], a))
    backward = [A[-1]]
    for a in reversed(A[:-1]):
        backward.append(gcd(backward[-1], a))
    backward.reverse()
    ans = max(forward[-2], backward[1])
    for i in range(1, len(A)-1):
        ans = max(ans, gcd(forward[i-1], backward[i+1]))
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

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

ma = 0
L = [[]] * N
all = gcd(A[0], A[1])
L[1] = [A[0], A[1]]

for i in range(2, N):
  t = [all]
  all = gcd(all, A[i])
  for j in L[i - 1]:
    k = gcd(j, A[i])
    if k not in t:
      t.append(k)
  L[i] = t

Ans = max(L[-1])

print(Ans)

Submission status: Accepted

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

A.sort()
A_min = A[1]

def func():
    for i in range(A_min, 0, -1):
        cnt = 0
        for j in range(n):
            if cnt == 0:
                if A[j] % i > 0:
                    cnt += 1
                    bad = j
            elif cnt == 1:
                if A[j] % i > 0:
                    cnt += 1
                    break

        if cnt < 2:
            return i

result = func()
print(result)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(raw_input())
L = map(int, raw_input().split())

D1 = [0]*n
D2 = [0]*n

for i in xrange(1, n):
    D1[i] = gcd(D1[i-1], L[i-1])

for i in xrange(n-2, -1, -1):
    D2[i] = gcd(D2[i+1], L[i+1])

M = [None]*n

for i in xrange(n):
    M[i] = gcd(D1[i], D2[i])

print max(M)

Submission status: Accepted

Solution code:
def make_divisors(n,m):
    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)
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            divisors.append(i)
            if i != m // i:
                divisors.append(m//i)

    divisors.sort()
    return divisors

N=int(input())

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

if len(A)==1:
  print(A[0])
  exit()

div=(make_divisors(A[0],A[1]))
div=list(set(div))
div.sort(reverse=True)
if len(A)<=2:
  print(div[0])
  exit()
for i in div:
  count=0
  for a in A[2:]:
    if a%i!=0:
      count+=1
    if count==2:
      break
  if count==0 or (count==1 and A[0]%i==0 and A[1]%i==0):
    print(i)
    exit()

Submission status: Accepted

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


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


A1 = make_divisors(A[0])
A2 = make_divisors(A[1])
experiment = []
for i in range(0, len(A1)):
    experiment.append([A1[i], 1])

flag = 1
for i in range(0, len(A2)):
    for j in range(0, len(A1)):
        if A2[i] == A1[j]:
            experiment[j][1] = 2
            flag = 0
    if flag == 1:
        experiment.append([A2[i], 1])
    flag = 1

for i in range(2, N):
    for j in range(0, len(experiment)):
        if A[i] % experiment[j][0] != 0:
            experiment[j][1] -= 1
max = experiment[0][0]
for i in range(0, len(experiment)):
    if experiment[i][1] > 0 and experiment[i][0] > max:
        max = experiment[i][0]

print("{}".format(max))

Submission status: Accepted

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

    return divisors

n=int(input())
at=[int(i) for i in input().split()]
a=set(at)
d={}
for i,j in enumerate(a):
    t=div(j)
    for k in t:
        if k in d:
            d[k]+=1
        elif i==0 or k not in d:
            d[k]=1
ans=1
for i in d:
    x=0
    for j in at:
        if j%i: x+=1
    if x<2: ans=max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b,t = LI()
    k = t//a
    print(k*b)
    return

#B
def B():
    n = I()
    v = LI()
    c = LI()
    ans = 0
    for i in range(n):
        if v[i] > c[i]:
            ans += (v[i]-c[i])
    print(ans)
    return

#C
def C():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    n = I()
    a = LI()
    m = math.ceil(n**0.5)
    f = [0 for i in range(m)]
    for i in range(m):
        b = a[m*i:min(n,m*(i+1))]
        if b:
            g = b[0]
            for j in b[1:]:
                g = gcd(g,j)
            f[i] = g
        else:
            f.pop(-1)
    ans = 1
    for i in range(n):
        j = i//m
        c = f[:j]+f[j+1:]+a[m*j:i]+a[i+1:min(n,m*(j+1))]
        g = c[0]
        for k in c[1:]:
            g = gcd(g, k)
        ans = max(ans,g)
    print(ans)
    return

#D
def D():
    n = I()
    a = LI()
    k = 0
    for i in a:
        if i < 0:
            k += 1
    ans = 0
    m = float("inf")
    for i in a:
        ans += abs(i)
        m = min(m,abs(i))
    if k%2:
        ans -= 2*m
    print(ans)
    return


#Solve
if __name__ == "__main__":
    C()