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:
import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if num[0]!=num[1] and all([x%num[1]==0 for x in data[1::]])==False:
    count=int(num[1]/2)+1
print(count)
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if 2<len(data):
    if num[0]!=num[1] and num[1]!=num[2]:
        count=int(math.sqrt(num[1])+1)
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

Submission status: Wrong Answer

Solution code:
import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if num[0]!=num[1]:
    count=int(num[1]/2+1)
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

Submission status: Wrong Answer

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

c=0
for i in reversed(range(1,m)):
    cnt=0
    for j in range(n):
        if a[j]%i==0:
            cnt+=1
    if cnt>=n-1:
        c=i
        break
print(c)

Submission status: Wrong Answer

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

from fractions import gcd
l,r = [0]*(n+1),[0]*(n+1)
for i in range(n):
    l[i+1] = gcd(l[i],a[i])
    r[n-i-1] = gcd(r[i+1],a[n-i-1])

ans = 1
for i in range(n):
    g = gcd(l[i],r[i+1])
    ans = max(ans,g)
print(ans)

Submission status: Wrong Answer

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

c=0
for i in range(1,m):
    cnt=0
    for j in range(n):
        if a[j]%i==0:
            cnt+=1
    if cnt>=n-1:
        c=i
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
c=0
for i in range(1,m):
    cnt=0
    for j in range(n):
        if a[j]%i==0:
            cnt+=1
    if cnt>=2:
        c=i
print(c)

Submission status: Wrong Answer

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

n=int(input())
a=list(map(int,input().split()))
max=0
for i in range(n-1):
    for j in range(i+1,n):
        p=gcd(a[i],a[j])
        if p>max:
            max=p
            ci=i
            cj=j
print(max)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

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

my_gcd = reduce(gcd, A)
A = [a // my_gcd for a in A]

flag = False
my_gcd_2 = 0
my_gcd_3 = 0

for i in range(N):
    a = A[i]
    if my_gcd_2 == 0:
        my_gcd_2 = a
    else:
        if gcd(my_gcd_2, a) == 1:
            if flag is False:
                if i == 1:
                    my_gcd_3 = a
                flag = True
                continue
            else:
                my_gcd_2 = -1
        if my_gcd_3 and gcd(my_gcd_3, a) == 1:
            my_gcd_3 = -1
        if my_gcd_2:
            my_gcd_2 = gcd(my_gcd_2, a)
        if my_gcd_3:
            my_gcd_3 = gcd(my_gcd_3, a)

else:
    ans_1 = my_gcd * my_gcd_2
    ans_2 = my_gcd * my_gcd_3
    print(max(ans_1, ans_2, my_gcd))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

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

my_gcd = reduce(gcd, A)
A = [a // my_gcd for a in A]

flag = False
my_gcd_2 = 0
my_gcd_3 = 0

for a in A:
    if my_gcd_2 == 0:
        my_gcd_2 = a
    else:
        if my_gcd_2 and gcd(my_gcd_2, a) == 1:
            if flag is False:
                my_gcd_2 = my_gcd_2
                my_gcd_3 = a
                flag = True
                continue
            else:
                my_gcd_2 = -1
        if my_gcd_3 and gcd(my_gcd_3, a) == 1:
            my_gcd_3 = -1
        if my_gcd_2:
            my_gcd_2 = gcd(my_gcd_2, a)
        if my_gcd_3:
            my_gcd_3 = gcd(my_gcd_3, a)

else:
    ans_1 = my_gcd * my_gcd_2
    ans_2 = my_gcd * my_gcd_3
    print(max(ans_1, ans_2, my_gcd))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

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

my_gcd = reduce(gcd, A)
A = [a // my_gcd for a in A]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

flag = False
my_gcd_2 = 0
for a in A:
    if len(prime_factorize(a)) <= 1:
        if not flag:
            flag = True
        else:
            print(my_gcd)
            break
    else:
        if my_gcd_2 == 0:
            my_gcd_2 = a
        else:
            my_gcd_2 = gcd(my_gcd_2, a)
else:
    print(my_gcd * my_gcd_2)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

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

my_gcd = reduce(gcd, A)
A = [a // my_gcd for a in A]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

flag = False
my_gcd_2 = 0
for i in range(N):
    if len(prime_factorize(A[i])) <= 1:
        if not flag:
            flag = True
        else:
            print(my_gcd)
            break
    else:
        if my_gcd_2 == 0:
            my_gcd_2 = A[i]
        else:
            my_gcd_2 = gcd(my_gcd_2, A[i])
else:
    print(my_gcd * my_gcd_2)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import numpy as np
from functools import reduce

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

my_gcd = reduce(gcd, A)
A //= my_gcd

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

flag = False
for i in range(N):
    if len(prime_factorize(A[i])) <= 1:
        if not flag:
            idx = i
            flag = True
        else:
            print(my_gcd)
            exit()
if flag:
    A = A.tolist()
    A = A[:idx] + A[idx + 1:]
    print(reduce(gcd, A) * my_gcd)

Submission status: Wrong Answer

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
l = [0]*(n+1)
l[1] = a[0]
r = [0]*(n+1)
r[n-1] = a[n-1]
for i in range(1, n):
  l[i+1] = fractions.gcd(l[i], a[i])
  r[n-1-i] = fractions.gcd(r[n-i], r[n-i])

m = 0
for i in range(n):
  m = max(m, fractions.gcd(l[i], r[i+1]))
print(m)

Submission status: Wrong Answer

Solution code:
from fractions  import gcd


n=int(input())
a=list(map(int,input().split()))
inf = 0
num_min =2**(n-1).bit_length()
dat=[inf]*(2*num_min-1)

#初期化
for i in range(n):
    dat[i+num_min-1]=a[i]
for i in range(num_min-2,-1,-1):
    dat[i]=gcd(dat[2*i+1],dat[2*i+2])

#親のノード(n-1)//2
#子のノード2n+1,2n+2

def segfunc(x,y):
    return gcd(x,y)

def update(i,x):
    i+=n-1
    dat[i]=x
    while i>0:
        i=(i-1)//2
        dat[i]=segfunc(dat[2*i+1],dat[2*i+2])
def query(a,b): #半開区間、[a,b)の最小値
    if b<=a:
        return inf
    res=inf
    a += num_min-1
    b += num_min-2
    while b-a>1:
        if a&1==0:
            res = segfunc(res,dat[a])
        if b&1==1:
            res = segfunc(res,dat[b])
        a=a//2
        b=(b-1)//2
    if a==b:
        res = segfunc(res,dat[a])
    else:
        res=segfunc(segfunc(res,dat[a]),dat[b])
    return res

ans=0
for i in range(n):
    left=query(0,i)
    right=query(i+1,n)
    ans=max(ans,gcd(left,right))
print(ans)

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
#隣あうAのgcdのリストを作る
lgcd = []
for i in range(N-1):
  lgcd.append(gcd(A[i],A[i+1]))

n1 = lgcd.count(1)

ans = -1
if n1 == 3:
  ans = 1
if n1 == 1 or 2:
  i1 = [i for i,x in enumerate(lgcd) if x == 1]  
  for i in i1:
    for j in range(2):
      resA = A[i+j]
      del A[i+j]
      l = []
      for k in range(N-2):
        l.append(gcd(A[k],A[k+1]))
        ans = max(ans,min(l))
      A.insert(i+j,resA)
if n1 == 0:
  m = min(lgcd)
  ind = lgcd.index(m)
  for j in range(2):
    resA = A[ind+j]
    del A[ind+j]
    l = []
    for k in range(N-2):
      l.append(gcd(A[k],A[k+1]))
      ans = max(ans,min(l))
    A.insert(ind+j,resA) 

if ans == -1:
  ans = A[0]
print(ans)

Submission status: Wrong Answer

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

GCD_l = [A[0]]
for i in range(1, N-1):
    GCD_l.append(fractions.gcd(GCD_l[-1], A[i]))

A = A[::-1]
GCD_r = [A[0]]
for i in range(1, N-1):
    GCD_r.append(fractions.gcd(GCD_r[-1], A[i]))
GCD_r = GCD_r[::-1]

ans = 1
for i in range(N):
    if i == 0:
        ans = max(ans, GCD_r[0])
    elif i == N-1:
        ans = max(ans, GCD_l[N-2])
    else:
        ans = max(ans, fractions.gcd(GCD_l[i-1], GCD_r[N-i-1]))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
A = LI()
# L = list(accumulate(A, gcd))
# R = list(accumulate(reversed(A), gcd))
tmpl = 0
tmpr = 0
L = []
R = []
for i in range(n):
    tmpl = gcd(tmpl, A[i])
    tmpr = gcd(tmpr, A[-1-i])
    L.append(tmpl)
    R.append(tmpr)

L = [0] + L + [0]
R = [0] + list(reversed(R)) + [0]
# print(L)
# print(R)

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
A = LI()
# L = list(accumulate(A, gcd))
# R = list(accumulate(reversed(A), gcd))
tmpl = 0
tmpr = 0
L = [0]
R = [0]
for i in range(n):
    tmpl = gcd(tmpl, A[i])
    tmpr = gcd(tmpr, A[-1-i])
    L.append(tmpl)
    R.append(tmpr)


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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
A = LI()
# L = list(accumulate(A, gcd))
# R = list(accumulate(reversed(A), gcd))
tmpl = A[0]
tmpr = A[-1]
L = [tmpl]
R = [tmpr]
for i in range(1, n):
    L.append(gcd(tmpl, A[i]))
    R.append(gcd(tmpr, A[-1-i]))

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

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    """
    「中間の値に関してうんぬん　→　その値の左右の区間から計算」
    は定石と思っていい気がする。

    言われてみればA[i]を除いたGCDはgcd(A[:i])とgcd(A[i+1:])から求まるわなあ
    素因数分解してとか考える以前の話だった。。。
    """

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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)
#print(gcd_l_li)
#print(gcd_r_li)

ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  # かきかえる整数が右端のときと左端のとき
for target in range(1, n-1):
    ans = max(ans, gcd(gcd_l_li[target-1], gcd_r_li[target-1]))
print(ans)

Submission status: Wrong Answer

Solution code:
# abc125_c.py
import math
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def is_prime2(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    i = 1
    while i**2 <= N:
        if N%i == 0:
            return True
        i += 1
    return False

N = int(input())
A = list(map(int,input().split()))
max_gcd = 1
# print("A : ",A)
prime_cnt = 0
for i in range(N-1):
    A_tmp = A[:i]+A[i+1:]
    target = gcd_list(A_tmp)
    if is_prime2(A[i]):
        prime_cnt += 1
    if prime_cnt>1:
        max_gcd = 1
        break
    if max_gcd < target:
        max_gcd = target
print(max_gcd)

Submission status: Wrong Answer

Solution code:
# abc125_c.py
import math
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = list(map(int,input().split()))
max_gcd = 1
# print("A : ",A)
for i in range(N-1):
    A_tmp = A[:i]+A[i+1:]
    target = gcd_list(A_tmp)
#    print(target)
    if max_gcd < target:
        max_gcd = target
print(max_gcd)

Submission status: Wrong Answer

Solution code:
# abc125_c.py
import math
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = list(map(int,input().split()))
max_gcd = 0
# print("A : ",A)
for i in range(N-1):
    A_tmp = A[:i]+A[i+1:]
    target = gcd_list(A_tmp)
#    print(target)
    if max_gcd < target:
        max_gcd = target
print(max_gcd)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
import operator
from functools import reduce
from collections import Counter, defaultdict

def read():
    N = int(input().strip())
    A = map(int, input().strip().split())
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = []
    for p in primes:
        while x % p == 0:
            factors.append(p)
            x //= p
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    primes = prime_factorization_preprocess(AMAX)
    x = [[0 for p in primes] for i in range(N)]

    counts_all = [INF for p in primes]
    for i, a in enumerate(A):
        factors = prime_factorization(a, primes)
        c = Counter(factors)
        for j, p in enumerate(primes):
            x[i][j] = c[p]
            counts_all[j] = min(counts_all[j], c[p])
    

    return -1


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
import operator
from functools import reduce
from collections import Counter, defaultdict

def read():
    N = int(input().strip())
    A = map(int, input().strip().split())
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = []
    for p in primes:
        while x % p == 0:
            factors.append(p)
            x //= p
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    primes = prime_factorization_preprocess(AMAX)
    x = [[0 for p in primes] for i in range(N)]

    counts_all = [INF for p in primes]
    for i, a in enumerate(A):
        factors = prime_factorization(a, primes)
        c = Counter(factors)
        for j, p in enumerate(primes):
            x[i][j] = c[p]
            counts_all[j] = min(counts_all[j], c[p])
    

    # [1, l] の区間における最小値
    sl = [[x[i][j] for j in range(len(primes))] for i in range(N)]
    # [r, N] の区間における最小値
    sr = [[x[i][j] for j in range(len(primes))] for i in range(N)]

    for i in range(N-1):
        for j in range(len(primes)):
            sl[i+1][j] = min(sl[i][j], sl[i+1][j])
            sr[N-2-i][j] = min(sr[N-1-i][j], sr[N-2-i][j])
    
    counts_one_out = [0 for p in primes]
    for i in range(N-1):
        for j in range(len(primes)):
            one_out = INF
            if i > 0:
                one_out = min(one_out, sl[i-1][j])
            if i < N-1:
                one_out = min(one_out, sr[i+1][j])
            counts_one_out[j] = max(counts_one_out[j], one_out)

    ans0 = reduce(operator.mul, [primes[i]**counts_all[i] for i in range(len(primes))])
    ans1 = reduce(operator.mul, [primes[i]**counts_one_out[i] for i in range(len(primes))])
    return max(ans0, ans1)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
import operator
from functools import reduce
from collections import Counter, defaultdict

def read():
    N = int(input().strip())
    A = map(int, input().strip().split())
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = []
    for p in primes:
        while x % p == 0:
            factors.append(p)
            x //= p
    return factors


def solve(N, A, AMAX = 10**2, INF=10**9):
    primes = prime_factorization_preprocess(AMAX)
    x = [[0 for p in primes] for i in range(N)]

    counts_all = [INF for p in primes]
    for i, a in enumerate(A):
        factors = prime_factorization(a, primes)
        c = Counter(factors)
        for j, p in enumerate(primes):
            x[i][j] = c[p]
            counts_all[j] = min(counts_all[j], c[p])
    

    # [1, l] の区間における最小値
    sl = [[x[i][j] for j in range(len(primes))] for i in range(N)]
    # [r, N] の区間における最小値
    sr = [[x[i][j] for j in range(len(primes))] for i in range(N)]

    for i in range(N-1):
        for j in range(len(primes)):
            sl[i+1][j] = min(sl[i][j], sl[i+1][j])
            sr[N-2-i][j] = min(sr[N-1-i][j], sr[N-2-i][j])
    
    counts_one_out = [0 for p in primes]
    for i in range(N-1):
        for j in range(len(primes)):
            one_out = INF
            if i > 0:
                one_out = min(one_out, sl[i-1][j])
            if i < N-1:
                one_out = min(one_out, sr[i+1][j])
            counts_one_out[j] = max(counts_one_out[j], one_out)

    ans0 = reduce(operator.mul, [primes[i]**counts_all[i] for i in range(len(primes))])
    ans1 = reduce(operator.mul, [primes[i]**counts_one_out[i] for i in range(len(primes))])
    return max(ans0, ans1)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
def left(i):
    if i < 1:
        return 0
    return gcd(left(i-1), A[i-1])
def right(i):
    if i+1 > n-1:
        return 0
    # ここA[i+1]じゃなくてA[i]
    return gcd(right(i+1), A[i]) 
ans = 0
for i in range(n):
    # ここright(i)じゃなくてright(i+1)
    ans = max(ans, gcd(left(i), right(i+1)))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
#たね：gcdは交換法則がなりたち、どこからでも計算していい
#だけど、逆演算ができない 
#(gcd(x,4)==2　を満たすxは2以上の偶数ならなんでもよく
#つまり一つに定まらない）
#そのかわり、"最後の一個以外"を計算してしまうことはできる

#初見殺しじゃねーか
from fractions import gcd
def resolve():
    N,=pin()
    A=tupin()
    lgcd,rgcd=[0]*(N),[0]*(N)
    ltemp,tempr=A[0],A[-1]
    for g in range(N):
        ltemp=gcd(ltemp,A[g])
        lgcd[g]=ltemp
        print(tempr,A[N-g-1])
        tempr=gcd(tempr,A[N-g-1])
        
        rgcd[N-g-1]=tempr
    print(lgcd,A,rgcd)
    ans=1
    for i in range((N)):
        a,t=0,0
        if i==0:
            t=rgcd[1]
        elif i==N-1:
            t=lgcd[N-2]
        else:
            t=gcd(lgcd[i-1],rgcd[i+1])
        ans=max(ans,t)
    print(ans)
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
#たね：gcdは交換法則がなりたち、どこからでも計算していい
#だけど、逆演算ができない 
#(gcd(x,4)==2　を満たすxは2以上の偶数ならなんでもよく
#つまり一つに定まらない）
#そのかわり、"最後の一個以外"を計算してしまうことはできる

#初見殺しじゃねーか
from fractions import gcd
def resolve():
    N,=pin()
    A=tupin()
    lgcd,rgcd=[0]*(N),[0]*(N)
    ltemp,tempr=A[0],A[-1]
    for g in range(N):
        ltemp=gcd(ltemp,A[g])
        lgcd[g]=ltemp
        #print(tempr,A[N-g-1])
        tempr=gcd(tempr,A[N-g-1])
        
        rgcd[N-g-1]=tempr
    ##print(lgcd,A,rgcd)
    ans=1
    for i in range((N)):
        a,t=0,0
        if i==0:
            t=rgcd[1]
        elif i==N-1:
            t=lgcd[N-1]
        else:
            t=gcd(lgcd[i-1],rgcd[i+1])
        ans=max(ans,t)
    print(ans)
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

L=[0]*n
R=[0]*n
L[0]=A[0]
R[n-1]=A[n-1]
res=0

for i in range(1,n):
	L[i]=gcd(L[i-1],A[i])
for i in range(0,n-1):
	R[n-i-2]=gcd(R[n-i-1],A[n-i-2])

for i in range(1,n-1):
	res=max(res,gcd(L[i-1],R[i+1]))
	
print(max(res,L[n-1],R[0]))

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

L=[0]*n
R=[0]*n
L[0]=A[0]
R[n-1]=A[n-1]
res=0

for i in range(1,n):
	L[i]=gcd(L[i-1],A[i])
for i in range(0,n-1):
	R[n-i-2]=gcd(R[n-i-1],A[n-i-2])

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

L=[0]*n
R=[0]*n
L[0]=A[0]
R[n-1]=A[n-1]
res=0

for i in range(1,n):
	L[i]=gcd(L[i-1],A[i-1])
for i in range(0,n-1):
	R[n-i-2]=gcd(R[n-i-1],A[n-i-1])

for i in range(1,n-1):
	res=max(res,gcd(L[i-1],R[i+1]))
	
res=max(res,L[n-1],R[0])
print(res)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    return gcd(b, a%b) if b else a
N = int(input())
a = list(map(int,input().split()))
gcdl = [a[0]]
gcdr = [a[N-1]]
for i in range(1,N-1):
    gcdl.append(gcd(gcdl[i-1],a[i]))
    gcdr.append(gcd(gcdr[i-1],a[N-i-1]))
import numpy as np
ans = np.maximum(gcdl[N-2],gcdr[N-2])
gcdr.sort()
for i in range(1,N-1):
    if ans < gcd(gcdl[i],gcdr[i]):
        ans = gcd(gcdl[i],gcdr[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def Eratosthenes(n):
	''' n 以下の素数をエラトステネスの篩で生成 '''
	tbl = np.ones(n+1, dtype=bool)
	tbl[0:2] = False
	for i in range(2, int(np.sqrt(n))+1):
		if tbl[i]:
			tbl[2*i::i] = False
	return np.arange(n+1)[tbl]

def ABC125C(n, a):
    MAX = int(np.sqrt(1000000000))
    prime = Eratosthenes(MAX)
    gcm = []
    MAX = int(np.sqrt(max(a)))
    for div in prime:
        if div > MAX:
            break
        while True:
            b = a % div
            if sum(b == 0) == n:
                # print("div =", div)
                gcm.append((div, -1)) # a[*] 全ての約数
                a /= div
            elif sum(b == 0) == n-1:
                j = np.where(b != 0)[0][0]
                temp = a[j]
                a /= div
                a[j] = temp
                gcm.append((div, j)) # 仮の約数　a[j] だけが約数を持たない
                # print(f"div = {div},  diff. at {j}")
                break
            else:
                break
    gcm = gcm[::-1]
    diff_pos = -99 # 約数を持たない数の位置
    GCM = 1
    for i in range(len(gcm)):
        a = gcm.pop(0)
        if a[1] != -1 and diff_pos == -99:
            diff_pos = a[1]
        if a[1] == -1 or a[1] == diff_pos:
            GCM *= a[0]
    print(GCM)

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

Submission status: Wrong Answer

Solution code:
# from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
As = list(map(int, input().split()))

def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

class segmented_tree:
    X_unit = 1 << 30
    X_f = lambda self, a, b: gcd(a,b)
    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (2*N)
        
    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x 
        # 後ろから入れていく
        for i in range(self.N-1, 0, -1):
            self.X[i] = self.X_f(self.X[i<<1], self.X[i<<1|1])

    # 1点更新
    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i<<1],self.X[i<<1|1])
    
    # 区間取得
    def fold(self, l, r):
        l += self.N
        r += self.N
        vl = self.X[l]
        vr = self.X[r-1]
        # 外から決めていく
        while l < r:
            # print(l,r)
            if l & 1:
                vl = self.X_f(self.X[l], self.X[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.X_f(self.X[r], self.X[r])
            l >>= 1
            r >>= 1
        return self.X_f(vl,vr)
  
st = segmented_tree(n)
st.build(As)
mx = 0
for i in range(n):
    if i == 0:
        a = st.fold(i+1,n)
    else:
        a = st.fold(0,i)
    if i+1 < n:
        b = st.fold(i+1,n)
    else:
        b = a        
    mx = max(mx,gcd(a,b))
print(mx)