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: Wrong Answer

Solution code:
from sys import stdin
import fractions

class SegmentTree():

    def __init__(self, n):
        self.n = 1
        # nに最も近い2のべき乗を計算
        while self.n < n:
            self.n *= 2

        # ノードの個数は2n-1個
        self.dat = [0] * (self.n * 2 - 1)
        
    def update(self, i, x):
        i = i + self.n - 1
        self.dat[i] = x

        while(i > 0):
            i = (i-1) // 2
            self.dat[i] = fractions.gcd(self.dat[i * 2 + 1], self.dat[i * 2 + 2])

    def __get_value(self, a, b, k, l, r):
        if r < a or b < l:
            return 0
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.__get_value(a, b, 2*k+1, l, (l+r)//2)
            vr = self.__get_value(a, b, 2*k+2, (l+r)//2+1, r)
            return fractions.gcd(vl, vr)

    def get_value(self, a, b):
        return self.__get_value(a, b, 0, 0, self.n-1)

if __name__ == "__main__":
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    st = SegmentTree(N)
    for i in range(N):
        st.update(i, A[i])
    
    ans = - (10 ** 10)
    for i in range(1, N+1):
        M_i = fractions.gcd(st.get_value(0, i), st.get_value(i+1, N))
        ans = max(ans, M_i) 

    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import fractions

class SegmentTree():

    def __init__(self, n):
        self.n = 1
        # nに最も近い2のべき乗を計算
        while self.n < n:
            self.n *= 2

        # ノードの個数は2n-1個
        self.dat = [0] * (self.n * 2 - 1)
        
    def update(self, i, x):
        i = i + self.n - 1
        self.dat[i] = x

        while(i > 0):
            i = (i-1) // 2
            self.dat[i] = fractions.gcd(self.dat[i * 2 + 1], self.dat[i * 2 + 2])

    def __get_value(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.__get_value(a, b, 2*k+1, l, (l+r)//2)
            vr = self.__get_value(a, b, 2*k+2, (l+r)//2+1, r)
            return fractions.gcd(vl, vr)

    def get_value(self, a, b):
        return self.__get_value(a, b, 0, 0, self.n-1)

if __name__ == "__main__":
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    st = SegmentTree(N)
    for i in range(N):
        st.update(i, A[i])
    
    ans = - (10 ** 10)
    for i in range(1, N+1):
        M_i = fractions.gcd(st.get_value(0, i), st.get_value(i+1, N))
        ans = max(ans, M_i) 

    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import*
from fractions import*
n,*a=map(int,open(0).read().split())
b=list(accumulate([0]+a,gcd))
c=list(accumulate([0]+a[::-1],gcd))
print(max(gcd(s,t)for s,t in zip(b,c[2::-1])))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# def
def substitution(n, i, k, num):
    for j in range(n - 1):
        k[j] = num[(i + j) % n]

# input
n = int(input())
num = [int(a) for a in input().split()]
num.sort(reverse=True)
# initialize
k = [0] * int(n - 1)
max = 0

# Search
for i in range(n):

    if n < 3:
        max = num[0]
        break
    substitution(n, i, k, num)

    p = k[0]
    for j in range(1, n - 1):
        q = k[j]
        while 1:
            tmp = p % q
            if tmp == 0:
                p = q
                if max < q:
                    max = q
                break
            else:
                p = q
                q = tmp

print(max)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# def
def substitution(n, i, k, num):
    for j in range(n - 1):
        k[j] = num[(i + j) % n]

# input
n = int(input())
num = [int(a) for a in input().split()]
num.sort(reverse=True)
# initialize
k = [0] * int(n - 1)
max = 0

# Search
for i in range(n):

    substitution(n, i, k, num)

    p = k[0]
    for j in range(1, n - 1):
        q = k[j]
        while 1:
            tmp = p % q
            if tmp == 0:
                p = q
                if max < q:
                    max = q
                break
            else:
                p = q
                q = tmp

print(max)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
lcum = [A[0]] + [0] * (N-1)
rcum = [A[N-1]] + [0] * (N-1)
for i in range(1, N):
    lcum[i] = gcd(lcum[i-1], A[i])
    rcum[i] = gcd(A[N-i], rcum[i-1])
ans = max(lcum[-1], rcum[-1])
for i in range(1, N-1):
    ans = max(ans, gcd(lcum[i-1], rcum[N-2-i]))
print(ans)

Submission status: Wrong Answer

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

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

data_ans=[]
data1=[A[0]]
data2=[A[N-1]]
l=A[0]
m=A[N-1]
for i in range(1,N-2):
  l=gcd(l,A[i])
  m=gcd(m,A[N-i])
  data1.append(l)
  data2.append(m)
l=gcd(l,A[N-2])
m=gcd(m,A[1])
data_ans.append(l)
data_ans.append(m)
for i in range(0,N-2):
  data_ans.append(gcd(data1[i],data2[N-3-i]))
print(max(data_ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
def gcd(L):
    while True:
        NL = []
        rs = 0
        minb = L[0]
        
        for l in L:
            b = minb
            r = l % b
            if r != 0 :
                if minb < r:
                    minb = r
                rs += r
                NL.append(r)
        L = NL
        if rs == 0:
            return minb

            

gcds = []
max = 0
for i in range(1,len(A)+1):
    g = gcd(A[0:i-1]+A[i:])
    #print(i,g,(A[0:i-1]+A[i:]))
    if max < g:
        max = g
print(max)

Submission status: Wrong Answer

Solution code:

from fractions import gcd

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

L = [a[0]]
R = [a[-1]]

for i in range(1, n):
    L.append(gcd(L[-1], a[i]))
    R.append(gcd(R[-1], a[-i - 1]))
R.reverse()

ans = max(L[-2], R[-2])

for i in range(1, n - 1):
    ans = max(ans, gcd(L[i - 1], R[-i]))

print(ans)

Submission status: Wrong Answer

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


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

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

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

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

print(max(num))

Submission status: Wrong Answer

Solution code:
n = int(input())
v = list(map(int, input().split()))
m = 1
gf = []
gp = []


def gcd(x, y):
    if x < y:
        x += y
        y = x - y
        x -= y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


gf.append(v[0])
for i in range(n-1):
    gf.append(gcd(gf[i], v[i+1]))

gp.append(v[n-1])
for i in range(n-1):
    gp.append(gcd(gp[i], v[n-2-i]))

m = gp[n-2]

for i in range(n-1):
    b = gcd(gf[i], gp[n-3-i])
    if m < b:
        m = b
if m < gf[1]:
    m = gf[n-2]

print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
v = list(map(int, input().split()))
m = 1
gf = []
gp = []


def gcd(x, y):
    if x < y:
        x += y
        y = x - y
        x -= y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


gf.append(v[0])
for i in range(n-1):
    gf.append(gcd(gf[i], v[i+1]))

gp.append(v[n-1])
for i in range(n-1):
    gp.append(gcd(gp[i], v[n-2-i]))

m = gp[n-2]

for i in range(n):
    b = gcd(gf[i], gp[n-3-i])
    if m < b:
        m = b

print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
v = list(map(int, input().split()))
m = 1
gf = []
gp = []


def gcd(x, y):
    if x < y:
        x += y
        y = x - y
        x -= y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


gf.append(v[0])
for i in range(n-1):
    gf.append(gcd(gf[i], v[i+1]))

gp.append(v[n-1])
for i in range(n-1):
    gp.append(gcd(gp[i], v[n-2-i]))

m = gp[n-2]

for i in range(n):
    b = gcd(gf[i], gp[i])
    if m < b:
        m = b

print(m)

Submission status: Wrong Answer

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

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

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

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

ans = 0
for i in range(N):
  ans = max(ans, gcd(L[i], R[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

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

l_gcd_list = [0]
for i, a in enumerate(A):
    # print("a", a)
    # result = max(result, gcd(previous_gcd, reduce(gcd, A[i+1:] + [0])))
    l_gcd_list.append(gcd(l_gcd_list[-1], a))
    # print("---")
# print(l_gcd_list)

A.sort(reverse=True)
r_gcd_list = [0]
for i, a in enumerate(A):
    # print("a", a)
    # result = max(result, gcd(previous_gcd, reduce(gcd, A[i+1:] + [0])))
    r_gcd_list.insert(0, gcd(r_gcd_list[0], a))
    # print("---")
# print(r_gcd_list)

result = 0
for i, _ in enumerate(A):
    result = max(result, gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(result)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
N = int(input())
A = [int(s) for s in input().split()]
ans = 0
L = [0] * (N)
R = [0] * (N)
for n in range(0, N):
    if n != N-1:
        L[n+1] = gcd(A[n], L[n])
        R[-(n+2)] = gcd(A[-(n+1)], R[-(n+1)])
print(L, R)
for n in range(0, N):
    temp = gcd(L[n], R[n])
    ans = max(temp, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

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

d = A[0]
flg = False
flg2 = False

for i in range(N):
    pd = d
    d = fractions.gcd(d, A[i])
    if d < pd and (not flg):
        d = pd
        flg = True

dd = A[1]
for i in range(N):
    pdd = dd
    dd = fractions.gcd(dd, A[i])
    if dd < pdd and (not flg2):
        dd = pdd
        flg2 = True

print(max(d, dd))

Submission status: Wrong Answer

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

res = min(Aa)
while(True):
  X = [x for x in Aa if x%res!=0]
  if len(X)==1:
    if A.count(X[0]) == 1:
      break
  elif len(X)==0:
    break
  res -= 1
  
print(res)

Submission status: Wrong Answer

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

res = min(A)
while(len([x for x in A if x%res!=0])>1):
  res -= 1
  
print(res)

Submission status: Wrong Answer

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

res = min(A)
while(len([x for x in A if x%res!=0])>1):
  res -= 1
  
print(res)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
left = [0]*n
right = [0]*n
for i in range(1,n):
    left[i] = gcd(left[i-1],a[i-1])
    right[-1-i] = gcd(right[-i],a[-i])
gcds = []
print(a)
print(left,right)
for i in range(n):
    gcds.append(gcd(left[i],right[i]))
print(max(gcds))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
gcd = []
for i in range(N):
    for j in range(N):
        if i == j and i != N - 1:j += 1
        if i == N -1:break
        x = max(A[i],A[j])
        y = min(A[i],A[j])
        if x%y == 0:gcd.append(y)
        else:
            while x%y != 0:
                z = x%y
                x = y
                y = z
            else:gcd.append(z)
print(max(gcd))

Submission status: Wrong Answer

Solution code:
import fractions as fr
N=int(input())
a=list(map(int,input().split()))
x,y,z=[a[0]],[a[N-1]],[]
for i in range(N-1):
	x.append(fr.gcd(x[i],a[i+1]))
	y.append(fr.gcd(y[i],a[N-1-i]))
z.append(y[N-1])
for i in range(1,N-1):
	z.append(fr.gcd(x[i-1],y[N-i]))
z.append(x[N-1])
print(max(z))

Submission status: Wrong Answer

Solution code:
import fractions as fr
N=int(input())
a=list(map(int,input().split()))
x,y,z=[a[0]],[a[N-1]],[]
for i in range(N-1):
	x.append(fr.gcd(x[i],a[i+1]))
	y.append(fr.gcd(y[i],a[N-1-i]))
z.append(y[N-1])
for i in range(1,N-1):
	z.append(fr.gcd(x[i-1],y[N-2-i]))
z.append(x[N-1])
print(max(z))

Submission status: Wrong Answer

Solution code:
import fractions as fr
N=int(input())
a=list(map(int,input().split()))
x,y,z=[a[0]],[a[len(a)-1]],[]
for i in range(N-1):
	x.append(fr.gcd(x[i],a[i+1]))
	y.append(fr.gcd(y[i],a[N-1-i]))
z.append(y[len(y)-1])
for i in range(1,N-1):
	z.append(fr.gcd(x[i-1],y[N-1-i]))
z.append(x[len(x)-1])
print(max(z))

Submission status: Wrong Answer

Solution code:
import fractions as fr
N=int(input())
a=list(map(int,input().split()))
x,y,z=[a[0]],[a[len(a)-1]],[]
for i in range(N-1):
	x.append(fr.gcd(x[i],a[i+1]))
	y.append(fr.gcd(y[i],a[N-1-i]))
z.append(y[len(y)-1])
for i in range(1,N):
	z.append(fr.gcd(x[i-1],y[N-1-i]))
z.append(x[len(x)-1])
print(max(z))

Submission status: Wrong Answer

Solution code:
import fractions as fr
N=int(input())
a=list(map(int,input().split()))
x,y,z=[a[0]],[a[len(a)-1]],[]
for i in range(N-1):
	x.append(fr.gcd(x[i],a[i+1]))
	y.append(fr.gcd(y[i],a[N-2-i]))
z.append(y[1])
for i in range(1,N):
	z.append(fr.gcd(x[i-1],y[N-2-i]))
z.append(x[len(x)-1])
print(max(z))

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=5
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=1
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=1
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[j]%i!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[j]%x!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and x>ans: ans=x

R=a[p]
for i in range(p+1,N):
    R=gcd(R,a[i])

if R>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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

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

l = []
r = []

for i in range(n):
    if i == 0:
        l.append(a[0])
        r.append(a[n-1])
    else:
        l.append(gcd(l[i-1],a[i]))
        r.append(gcd(r[i-1],a[n-i-1]))

r.reverse()
ans = max(l[n-2],r[1])

for i in range(1,n-1):
    if ans < gcd(l[i-1],r[n-i]):
        ans = gcd(l[i-1],r[n-i])

print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=2
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=1
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[j]%i!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[j]%x!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and x>ans: ans=x

R=a[p]
for i in range(p+1,N):
    R=gcd(R,a[i])

if R>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=2
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+2 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[j]%i!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[j]%x!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and x>ans: ans=x

R=a[p]
for i in range(p+1,N):
    R=gcd(R,a[i])

if R>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=2
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[j]%i!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[j]%x!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and x>ans: ans=x

R=a[p]
for i in range(p+1,N):
    R=gcd(R,a[i])

if R>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=5
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[j]%i!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[j]%x!=0:
                cnt+=1
                if cnt==2: break
            elif j==N-1 and x>ans: ans=x

R=a[p]
for i in range(p+1,N):
    R=gcd(R,a[i])

if R>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=10
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[j]%i!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[j]%x!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and x>ans: ans=x

R=a[p]
for i in range(p,N):
    R=gcd(R,a[i])

if R>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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

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


gcd = fractions.gcd


left = [0] * N
right = [0] * N
for i in range(N):
    if i == 0:
        left[0] = A[0]
        right[N-1] = A[-1]
        continue

    left[i] = gcd(left[i-1], A[i])
    right[N-i-1] = gcd(right[N-i], A[N-i-1])

max_gcd = right[1]
for i in range(N):
    if i == 0:
        continue
    elif i == N - 1:
        if max_gcd < left[-1]:
            max_gcd = left[-1]
    else:
        target = gcd(left[i-1], right[i+1])
        if max_gcd < target:
            max_gcd = target

print(max_gcd)

Submission status: Wrong Answer

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

def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
p=30
N=int(input())
if p>N: p=N
a=list(map(int,input().split()))

ans=0
for i in range(p):
    s=cul(i,a[:p])
    if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=100
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()

ans=0        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

R=a[p]
for i in range(p+1,N):
    R=gcd(R,a[i])

if R>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=10
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0


R=a[p]
for i in range(p,N):
    r=gcd(R,a[i])

if r>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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

mat = [[0]*n for i in range(10)]
pns = [25,23,19,17,13,11,7,5,3,2]
for i,num in enumerate(a):
  for j,pn in enumerate(pns):
    if num == 1:
      break
    while num%pn == 0:
      num /= pn
      mat[j][i] += 1

res = 1
flag = True
for j,pn in enumerate(pns):
  powers = sorted(mat[j])
  min1 = powers[0]
  min2 = powers[1]
  
  if flag:
    if min1!=min2:
      min1+=1
      flag = False
  res *= pn ** min1
  
print(res)

Submission status: Wrong Answer

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

mat = [[0]*n for i in range(9)]
pns = [23,19,17,13,11,7,5,3,2]
for i,num in enumerate(a):
  for j,pn in enumerate(pns):
    if num == 1:
      break
    while num%pn == 0:
      num /= pn
      mat[j][i] += 1

res = 1
flag = True
for j,pn in enumerate(pns):
  powers = sorted(mat[j])
  min1 = powers[0]
  min2 = powers[1]
  
  if flag:
    if min1!=min2:
      min1+=1
      flag = False
  res *= pn ** min1
  
print(res)

Submission status: Wrong Answer

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

d = set()
for aa in a[0], a[1]:
    for i in range(1, int(aa ** 0.5) + 1):
        if aa % i == 0:
            d.add(i)
            d.add(aa // i)  # i == aa//iのときは重複する
# aの2要素の約数全列挙

print(d)

g = 1
for dd in d:
    cnt = 0
    for aa in a:
        if aa % dd == 0:
            cnt += 1
    if cnt >= N - 1:
        # N-1個以上の要素を割るなら、求める最大公約数足り得る
        g = max(g, dd)
print(g)


# def is_p(x):
#     if x <= 1: return False
#     for i in range(2, int(x ** 1 / 2) + 1):
#         if x % i == 0:
#             return False
#     else:
#         return True
#
#
# b = (i for i in range(100) if is_p(i))
# t = 1
# for i, bb in enumerate(b, 1):
#     t *= bb
#     t, i
#     if t > 10 ** 9:
#         bb
#         break
# (2, 1)
# (6, 2)
# (30, 3)
# (210, 4)
# (2310, 5)
# (30030, 6)
# (510510, 7)
# (9699690, 8)
# (223092870, 9)
# (6469693230, 10)
# 29
# 小さい方から9個の素数の積で、10**9以内の最大数となる

# 数列で最小の値が素数9個の積で、
# 次に小さい値も重複しない素数9個の積の場合、
# それら素数18個からなる全約数は、
# 2 ** (9 * 2)個あり、
# これら全てについて、10**5個の要素に対し、割り切れるかを試すとTLEになる。
# ただ、10**5個の要素の素因数分解で現れる素数が全く重ならないということは、
# 鳩ノ巣から考えられないんだと思う
# 配列aから2つの要素を取り出したときの、それぞれの約数を全列挙したものの和集合の要素数は、
# 具体的に幾つと見積もればいいのだろうか

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=10
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[i]%i!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[i]%x!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and x>ans: ans=x



print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=10
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[i]%i!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[i]%x!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and x>ans: ans=x

R=a[p]
for i in range(p,N):
    R=gcd(R,a[i])

if R>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=10
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[i]%i!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[i]%x!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and x>ans: ans=x

R=a[p]
for i in range(p,N):
    r=gcd(R,a[i])

if r>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)

Submission status: Wrong Answer

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


def cul(n,a):
    l=len(a)
    b=[a[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=10
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0
for i in range(1,math.ceil(M**0.5)+1 ):
    if M%i==0:
        cnt=0
        for j in range(p,N):
            if a[i]%i!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and i>ans: ans=i
        
        x=M//i
        cnt=0
        for j in range(p,N):
            if a[i]%x!=0:
                cnt+=1
                if cnt==2: break
            elif i==N-1 and x>ans: ans=x

r=a[N-1]
for i in range(N-1,p-1,-1):
    r=gcd(r,a[i])
if r>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),r)
        if s>ans: ans=s

print(ans)