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

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

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

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

Submission status: Accepted

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

import fractions

head = {}
head[0] = aa[0]
for i in range(1, n):
    head[i] = fractions.gcd(head[i - 1], aa[i])

tail = {}
tail[n - 1] = aa[-1]
for i in range(n - 2, -1, -1):
    tail[i] = fractions.gcd(tail[i + 1], aa[i])

candidate = 1
for i in range(0, n):
    if i == 0:
        gcd2 = tail[i + 1]
        candidate = max(gcd2, candidate)
    elif i == n - 1:
        gcd1 = head[i - 1]
        candidate = max(gcd1, candidate)
    else:
        gcd1 = head[i - 1]
        gcd2 = tail[i + 1]
        candidate = max(fractions.gcd(gcd1, gcd2), candidate)

print(candidate)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
L = [0] * N
R = [0] * N
for i in range(N - 1):
    L[i + 1] = gcd(L[i], A[i])
for i in range(N - 1, 0, -1):
    R[i - 1] = gcd(R[i], A[i])
ans = 0
for i in range(N):
    ans = max(gcd(L[i], R[i]), ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	dp_l = [0]*(N+2)
	dp_r = [0]*(N+2)

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

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

	ans = 1
	for i in range(1, N+1):
		this_ans=gcd(dp_l[i-1], dp_r[i])
		ans = max(ans, this_ans)

	print(ans)



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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

r=[]
l=[]
resr = ai[0]
resl = ai[n-1]
r.append(ai[0])
l.append(ai[n-1])
for i in range(1,n):
	resr=gcd(resr,ai[i])
	r.append(resr)
	resl=gcd(resl,ai[n-1-i])
	l.append(resl)

#print(r)
#print(l)

resmax = 1
for i in range(n):
	if i == 0:
		res = l[n-1-1]
	elif i == n-1:
		res = r[n-1-1]
	else:
		res = gcd(r[i-1], l[n-1-i-1])
	if res > resmax:
		resmax = res

print(int(resmax))

Submission status: Accepted

Solution code:
from functools import reduce

def gcd(m, n):
    # 入力を m, n (m ≧ n) とする。
    tmp = max(m,n)
    n = min(m,n)
    m = tmp
    # n = 0 なら、 m を出力してアルゴリズムを終了する。
    if n == 0:
        return m
    # m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。
    return gcd(n, m % n)

def gcda(arr, left, right):
    return reduce((lambda a,b:gcd(a,b)), arr[left:right+1], gcd(arr[left], arr[right]))

n = int(input())
nums = [ int(s) for s in input().split(" ")]

if n == 2:
    print(max(nums))
    exit()

left_n = [0 for _ in range(n)]
right_n = [0 for _ in range(n)]

left_n[0] = nums[0]
right_n[n-1] = nums[n-1]

for i in range(n-1):
    left_n[i+1] = gcd(left_n[i], nums[i+1])
    right_n[n-2-i] = gcd(right_n[n-1-i], nums[n-2-i])

# print(left_n)
# print(right_n)

maxgcd = 0
for i in range(n):
    if i == 0:
        maxgcd = max(maxgcd, right_n[1])
    if i == n-1:
        maxgcd = max(maxgcd, left_n[n-2])
    else:
        maxgcd = max(maxgcd, gcd(right_n[i+1], left_n[i-1]))

print(maxgcd)

Submission status: Accepted

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

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

n=int(input())
A=list(map(int,input().split()))
L=[0]*(n+1)
R=[0]*(n+1)
for i in range(n):
    L[i+1]=gcd(L[i],A[i])
for i in reversed(range(n)):
    R[i]=gcd(R[i+1],A[i])
ans=0
for i in range(n):
    ans=max(ans,gcd(L[i],R[i+1]))
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import fractions
from functools import reduce
N = int(input())
A = [int(i) for i in input().split()]

def gcd(nums):
    return reduce(fractions.gcd,nums)

ans = 1
A.sort()
gcd1 = gcd(A)
for i in range(N):
    A[i] //= gcd1

ans *= gcd1

gcd2 = A[0]
for i in range(1,N):
    gcd2 = fractions.gcd(gcd2,A[i])
    if gcd2 == 1:
        key = i
        break

a = copy.deepcopy(A)
a.remove(A[0])
b = copy.deepcopy(A)
b.remove(A[key])

ans *= max(gcd(a),gcd(b))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n = int(input())
a = list(map(int,input().split()))
a.sort()
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass #sortされていない
 
#0番目を使わない場合
res = gcdlist(a[1::])
 
#else
p = sorted(divisor(a[0]))
for i in range(len(p)-1,-1,-1):
    if p[i]<=res:
        break
    cnt = 1
    for j in range(1,n):
        if a[j]%p[i]==0:
            cnt += 1
    if cnt >= n-1:
        res = p[i]
        break
print(res)

Submission status: Accepted

Solution code:
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)
 
N=int(input())
A=[int(i) for i in input().split()]
X=[0 for i in range(N)]
Y=[0 for i in range(N)]
for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])
Z=[gcd(X[i],Y[i]) for i in range(N)]
print(max(Z))

Submission status: Accepted

Solution code:

import fractions
N = int(input())
A = list(map(int, input().split()))
x = [0] * N
y = [0] * N
tmp = A[0]
for i in range(1, N):
    t = fractions.gcd(tmp, A[i])
    x[i] = int(tmp / t)
    tmp = t
tmp = A[N - 1]
for i in range(N - 2, -1, -1):
    t = fractions.gcd(tmp, A[i])
    y[i] =  int(tmp / t)
    tmp = t
m = 0
for i in range(1, N - 1):
    a = fractions.gcd(x[i], y[i])
    if m < a:
        m = a
print(tmp * max(m, y[0], x[N - 1]))

Submission status: Accepted

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
gcd = lambda x, y: gcd(y, x % y) if x % y else y
L = list(itertools.accumulate(A, func=gcd))
R = list(itertools.accumulate(A[::-1], func=gcd))[::-1]
ans = max(R[1], L[-2])
for i in range(1, N - 1):
    ans = max(ans, gcd(L[i - 1], R[i + 1]))
print(ans)
# https://img.atcoder.jp/abc125/editorial.pdf

Submission status: Accepted

Solution code:
import fractions
import functools
import sys

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

if len(a) == 2:
  print(max(a))
  sys.exit()
  
gcd_a = functools.reduce(fractions.gcd, a)
a=[i//gcd_a for i in a]

so = 0
cnt = 0
gcd_0 = functools.reduce(fractions.gcd, a[1:])
for i in range(1,len(a)):
  if fractions.gcd(a[0],a[i]) == 1:
    so = i
    cnt+=1
    if cnt == 2:
      print(max(gcd_a,gcd_0*gcd_a))
      sys.exit()

a_i = [i for i in a if i != a[so]]
gcd_i = functools.reduce(fractions.gcd, a_i)

print(max(gcd_0,gcd_i)*gcd_a)

Submission status: Accepted

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


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

if N == 2:
    print(max(A))
else:
    AF = [1] * (N - 1)
    AB = [1] * (N - 1)

    AF[0] = A[0]
    AB[0] = A[-1]

    for i in range(1, N - 1):
        AF[i] = m(AF[i - 1], A[i])
        AB[i] = m(AB[i - 1], A[- (i + 1)])
    L = max(AF[-1], AB[-1], max([m(AF[i], AB[N - 3 - i]) for i in range(N - 2)]))

    print(L)

Submission status: Accepted

Solution code:
from functools import reduce


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


N = int(input())
a_list = list(map(int, input().split()))
gcd_list = [a_list[-1]]
for idx in range(N - 2, 0, -1):
    gcd_list.append(gcd(gcd_list[N - 2 - idx], a_list[idx]))
max_gcd_a = gcd_list[-1]
gcd_list.append(1)
gcd_list.reverse()

for idx in range(1, N):
    if idx != 1:
        left_gcd = gcd(left_gcd, a_list[idx - 1])
    else:
        left_gcd = a_list[0]
    if idx < N - 1:
        right_gcd = gcd_list[idx + 1]
    else:
        right_gcd = left_gcd

    gcd_a = gcd(left_gcd, right_gcd)
    if max_gcd_a < gcd_a:
        max_gcd_a = gcd_a

print(max_gcd_a)

# どれか１つを除いた時の最大公約数で最大のもの

Submission status: Accepted

Solution code:
from functools import reduce
import numpy as np


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


def gcd(*n):
    return reduce(_gcd, n)


def my_bisect(x):

    def find_pos(left, right):
        return left + (right - left - 1) // 2

    def func(left, right, prev):
        if right - left == 1:
            return left
        pos = find_pos(left, right)
        g1 = gcd(*x[left:pos+1])
        g2 = gcd(*x[pos+1:right])
        if prev is not None:
            g1, g2 = gcd(g1, prev), gcd(g2, prev)
        if g1 < g2:
            return func(left, pos + 1, max(g1, g2))
        else:
            return func(pos + 1, right, max(g1, g2))
    return func(0, len(x), None)


N = int(input())
A = list(map(int, input().split()))
print(gcd(*np.delete(A, my_bisect(A))))

Submission status: Accepted

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


N = int(input())
A = input().split()
for i in range(N):
    A[i] = int(A[i])
    
if N == 2:
    print(max(A[0],A[1]))
if N >= 3:
    gcd_all = gcd(A[0], A[1])
    gcd_without_1 = A[0]
    gcd_without_2 = A[1]
    gcd_without_1 = max(gcd_all, max( gcd(gcd_without_1, A[i]),gcd(gcd_without_2, A[i])))
    gcd_all = gcd(gcd_all,A[2])
    for i in range(3,N):
        gcd_without_1 = max(gcd_all, gcd(gcd_without_1, A[i]))
        gcd_all = gcd(gcd_all,A[i])
    print(max(gcd_all, gcd_without_1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import Counter
import collections
INF = float("inf")


def factorial(n):
    # 試し割りによる素因数分解
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def GCDs(*a):
    # リストで入力しないよう注意。
    if len(a) == 0:
        return -1  # エラー

    if len(a) == 1:
        return a[0]

    res = a[0]
    for i in range(1, len(a)):
        res = GCD(res, a[i])
    return res


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


def solve(N: int, A: "List[int]"):
    c1 = make_divisors(A[0])
    c2 = make_divisors(A[1])
    c = sorted(list(set(c1 + c2)))

    OKs = []
    for cv in c:
        if sum([1 if a % cv == 0 else 0 for a in A]) >= N-1:
            OKs.append(cv)
    print(max(OKs))

    # b = A[0]
    # m = INF
    # mi = -1
    # for i in range(N):
    #     g = GCD(A[i], b)
    #     print(g)
    #     if m > g:
    #         m = g
    #         mi = i
    # buf = None
    # for i in range(N):
    #     if mi == i:
    #         continue
    #     if buf is None:
    #         buf = A[i]
    #     else:
    #         buf = GCD(buf, A[i])
    # print([buf, GCDs(*A[1:])])
    # print("回答: ", max([buf, GCDs(*A[1:])]))
    # # print(g)

    # s = SegmentTree(N)
    # for i in range(N):
    #     s.update(i, A[i])
    # # print("tree ", s.tree)
    # g = []
    # for i in range(N):
    #     # iを覗いたGCDをとる
    #     if i == 0:
    #         g.append(s.query(1, N))
    #     elif i == N-1:
    #         g.append(s.query(0, N-1))
    #     else:
    #         # print(s.query(0, i), s.query(i+1, N))
    #         g.append(GCD(s.query(0, i), s.query(i+1, N)))
    # # print(g)
    # # print("回答2: ", max(g))
    # print(max(g))

    # g = []
    # for i in range(N):
    #     buf = None
    #     for j in range(N):
    #         if i == j:
    #             continue
    #         if buf is None:
    #             buf = A[j]
    #         else:
    #             buf = GCD(buf, A[j])
    #     g.append(buf)
    # # print(g)
    # print("正解：", max(g))

    return


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:
N = int(input())
A = sorted(list(map(int, input().split())))

if N == 2:
  print(max(A))
  exit()
  
#A0, A1, A2の約数のリストをとって和集合にする
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()
    divisors.reverse()
    return divisors
rawcdivisors = set(make_divisors(A[0]))|set(make_divisors(A[1]))|set(make_divisors(A[2]))

#各ループで、これが答えとなるかチェック
#初期値は、答えとなる可能性のある整数のうち最大のもの
cnum = A[1]

cdivisors = set(list(rawcdivisors))
#これより大きいものをcdivisorsから省く
for divnum in list(rawcdivisors):
  if divnum > cnum: cdivisors.remove(divnum)

ans = 0
for i in sorted(list(cdivisors),reverse=True): #secminaから1までチェック
  ngcnt = 0 #各iでngcntを初期化
  for a in A:
#    print('i, a: '+str(i)+', '+str(a))
    if a % i != 0: #公約数じゃなければ+1
      ngcnt += 1
      if ngcnt >= 2: break #2になったら望みなし
  if ngcnt >= 2: continue #2だったら望みなし
  else:
    ans = i #1以下ならiが答え
    break
  
  
print(ans)

Submission status: Accepted

Solution code:
import fractions

n = int(input())
a = list(map(int, input().split()))
gcd_0 = fractions.gcd(a[0],a[1])
gcd_1 = min(a[0], a[1])
for i in range(2,n):
    gcd_1 = max(gcd_0, fractions.gcd(gcd_1, a[i]))
    gcd_0 = fractions.gcd(gcd_0, a[i])

gcd_0 = fractions.gcd(a[0],a[1])
gcd_2 = max(a[0], a[1])
for i in range(2,n):
    gcd_2 = max(gcd_0, fractions.gcd(gcd_2, a[i]))
    gcd_0 = fractions.gcd(gcd_0, a[i])
    
print(max(gcd_2,gcd_1))

Submission status: Accepted

Solution code:
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
A = IL()

A.sort()
ABS = []
for i in range(1,N):
    ABS.append(A[i]-A[i-1])

ABS.sort()
num = A[1]
cnt = 0
for i in range(num+1,0,-1):
    cnt = 0
    for j in range(N):
        if A[j]%i==0:
            continue
        else:
            cnt += 1
        if cnt == 2:
            break
    else:
        print(i)
        exit()

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 125
# https://atcoder.jp/contests/abc125
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

cache = {}


def gcd(a, b):
    if a not in cache:
        cache[a] = {}
    if b in cache[a]:
        return cache[a][b]
    if b == 0:
        cache[a][b] = a
        return a
    n = gcd(b, a % b)
    cache[a][b] = n
    return n

def main_lte(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn = [An[0]] * N
    nn[0] = An[1]
    for i in range(1, N):
        for j in range(N):
            if i == j:
                continue
            nn[j] = gcd(nn[j], An[i])
    print(int(max(nn)))

def main(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn0 = gcd(An[0], An[1])
    nn1 = set((An[0], An[1]))
    for i in range(2, N):
        t1 = nn0
        nn0 = gcd(nn0, An[i])
        t2 = [gcd(n, An[i]) for n in nn1]
        nn1 = set(t2)
        nn1.add(t1)
    n = max(nn1)
    print(int(n))

N = i2n()
An = i2nn()
main(N, An)

Submission status: Accepted

Solution code:

import numpy as np
N = int(input())
As=input().split()
A = np.array([int(s) for s in As])
del(As)

min2A = A[A.argsort()[1]]
minA = np.amin(A)
if np.sum((A%min2A)==0)>=N-1:
    print(min2A)
elif np.sum((A%minA)==0)>=N-1:
    print(minA)
else:
    for i in range(2,min2A+1):
        if (min2A%i == 0) or (minA%i == 0):
            if(min2A%i == 0):
                j = int(min2A/i)
            elif(minA%i == 0):
                j=int(minA/i)
            if np.sum((A%j)==0)>=N-1:
                print(j)
                break

Submission status: Accepted

Solution code:
# GCD
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

# struct
class struct:
  def __init__(self,a,b,c):
    self.a=a
    self.b=b
    self.c=c

n=int(input())
if n==2:
  a,b=map(int,input().split())
  print(max(a,b))
  exit()
elif n==3:
  a,b,c=map(int,input().split())
  print(max(gcd(a,b),gcd(a,c),gcd(b,c)))
  exit()
else:
  l=list(map(int,input().split()))
  a=l[0]
  b=l[1]
  c=l[2]
  d=l[3]
  l2=[]
  l2.append(struct(a,b,gcd(a,b)))
  l2.append(struct(a,c,gcd(a,c)))
  l2.append(struct(a,d,gcd(a,d)))
  l2.append(struct(b,c,gcd(b,c)))
  l2.append(struct(b,d,gcd(b,d)))
  l2.append(struct(c,d,gcd(c,d)))
  l2=sorted(l2,key=lambda x:(x.c,x.a,x.b))
  l3=[l2[0].a,l2[0].b,l2[1].a,l2[1].b]
  jama=10000000000000000
  if l3.count(l3[0])>1:
    jama=l3[0]
  if l3.count(l3[1])>1:
    jama=l3[1]
  if l3.count(l3[2])>1:
    jama=l3[2]
  if l3.count(l3[3])>1:
    jama=l3[3]
  mein=100000000000000000
  if jama==a:
    mein=gcd(gcd(b,c),d)
  if jama==b:
    mein=gcd(gcd(a,c),d)
  if jama==c:
    mein=gcd(gcd(a,c),d)
  if jama==d:
    mein=gcd(gcd(b,c),a)
  for x in l[4:]:
    xx=gcd(mein,x)
    yy=gcd(mein,jama)
    if xx<yy:
      jama=x
      mein=yy
    else:
      mein=xx
  print(mein)

Submission status: Accepted

Solution code:
import sys
from functools import reduce
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def gcd_list(numbers):
    return reduce(gcd, numbers)
n = ni()
a = nl()
if len(a) == 2:
    print(max(a))
    exit()
minn = 10 ** 9 + 1
idx = -1
for i in range(n - 2):
    if minn >= gcd_list([a[i], a[i + 1], a[i + 2]]):
        minn = gcd_list([a[i], a[i + 1], a[i + 2]])
        idx = i
gcd1 = 0
gcd2 = 0
gcd3 = 0
for i in range(n):
    if i != idx:
        gcd1 = gcd(gcd1, a[i])
    if i != idx + 1:
        gcd2 = gcd(gcd2, a[i])
    if i != idx + 2:
        gcd3 = gcd(gcd3, a[i])
print(max(gcd1, gcd2, gcd3))

Submission status: Accepted

Solution code:
N = int(input()) 
def gcd(m, n):
  a = max(m,n)
  b = min(m,n)
  if a%b==0:
    return b
  while not a % b == 0:
      a, b = b, a % b
  return b

arr = [int(item) for item in input().split()]
a = [arr[0]]
b = [arr[-1]]
for i in range(1, N):
  a.append(gcd(a[i-1], arr[i]))
  b.append(gcd(b[i-1], arr[N-i-1]))
ans = max(a[-2], b[-2])
b = b[::-1]
for i, j in zip(a[:-2], b[2:]):
  ans = max(ans, gcd(i,j))
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)

    # divisors.sort()
    return divisors

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    numdct = {}
    for i in range(2):
        for div in make_divisors(a[i]):
            if(not div in numdct):
                numdct[div] = 0
            numdct[div] += 1

    dellist = []
    for i in range(2, n):
        for num in numdct.keys():
            if(a[i] % num != 0):
                numdct[num] -= 1
                if(numdct[num] == 0):
                    dellist.append(num)
        for d in dellist:
            del numdct[d]
        dellist.clear()
    
    numlist = sorted(numdct.items(), key=lambda x: -x[1])

    maxnum = 0
    for item in numlist:
        if(item[1] > 0):
            if(maxnum <= item[0]):
                maxnum = item[0]
        else:
            break

    print(maxnum)

Submission status: Accepted

Solution code:
from fractions import gcd

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

if N == 2:
    print(max(A))
    import sys
    sys.exit()

g = gcd(A[0], A[1])
lmax = 1
num = 0
for i in range(2,N):
    cand = gcd(g, A[i])
    if cand < g:
        l = int(g / cand)
        g = cand
        if lmax < l:
            lmax = l
            num = A[i]
A = A[1:] + [A[0]]
g = gcd(A[0], A[1])
for i in range(2,N):
    cand = gcd(g, A[i])
    if cand < g:
        l = int(g / cand)
        g = cand
        if lmax < l:
            lmax = l
            num = A[i]
A = A[1:] + [A[0]]
g = gcd(A[0], A[1])
for i in range(2,N):
    cand = gcd(g, A[i])
    if cand < g:
        l = int(g / cand)
        g = cand
        if lmax < l:
            lmax = l
            num = A[i]
if num == A[0]:
    A = A[1:]
    flag = False
    N -= 1
elif num == A[1]:
    A = [A[0]] + A[2:]
    flag = False
    N -= 1
else:
    flag = True
g = gcd(A[0], A[1])
for i in range(2,N):
    if A[i] == num and flag:
        flag = False
    else:
        g = gcd(g, A[i])
print(g)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
gcdL = [0] * N
gcdR = [0] * N

gcdL[0] = A[0]
gcdR[-1] = A[-1]

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


for i in range(1, N):
    gcdL[i] = gcd(gcdL[i-1], A[i])
for i in range(1, N):
    gcdR[-i-1] = gcd(gcdR[-i], A[-i-1])

ans = gcdR[1]  # No 1
# print(ans)
for i in range(1, N-1):
    tmp = gcd(gcdL[i-1], gcdR[i+1])
    # print(tmp)
    ans = max(tmp, ans)
ans = max(ans, gcdL[-2])
# print(gcdL[-2])
print(ans)

Submission status: Accepted

Solution code:
import fractions as f

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

if N == 2:
    print(max(A))
else:
    A = sorted(A)
    l1,l2 = [],[]
    c1,c2 = 0,0
    for i in range(1,N):
        a = f.gcd(A[0],A[i])
        l1 += [a]
        if a == 1:
            c1 += 1
            if c1 >= 2:
                break
    for j in range(2,N):
        a = f.gcd(A[1],A[j])
        l2 += [a]
        if a == 1:
            c2 += 1
            if c2 >= 1:
                break

    if c1 >= 2 and c2 >= 1:
        print(1)
    else:
        ans1, ans2 = 1,1
        if c1 < 2:
            l1.pop(l1.index(min(l1)))
            ans1 = l1[0]
            for i in range(1,len(l1)):
                ans1 = f.gcd(ans1,l1[i])
        if c2 < 1:
            ans2 = l2[0]
            for i in range(1,len(l2)):
                ans2 = f.gcd(ans2,l2[i])
        print(max(ans1,ans2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            for j in range(2*i, N, i):
                sieve[j] = 0
            P.append(i)
    return P

P = set(primes(32000))
D = defaultdict(list)
C = set()
for a in A:
    removes = []
    for p in P:
        cnt = 0
        while a%p==0:
            cnt += 1
            a //= p
        if cnt:
            D[p].append(cnt)
        else:
            if p in C:
                removes.append(p)
            else:
                C.add(p)
    P = P - set(removes)
    if a > 1:
        D[a].append(1)

D = {k:[0]*(len(v) == N-1) + sorted(v) for k, v in D.items() if len(v) >= N-1}

ori = 1
for k, v in D.items():
    ori *= k**v[0]

ans = max(ori, 1)
for a in A:
    tmp = 1 * ori
    for p in D.keys():
        cnt = 0
        while a%p==0:
            cnt += 1
            a //= p
        if cnt == D[p][0]:
            tmp *= p**(D[p][1] - D[p][0])
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

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

tmp = A[0]
for i in range(N):
    tmp = gcd(tmp, A[i])
    
    
for i in range(N):
    A[i] //= tmp
 
A.sort(reverse=True)

v1 = A[0]
count1 = 0
for i in range(N):
    tmp1 = v1
    v1 = gcd(v1, A[i])
    if  v1 == 1:
        count1 += 1
        if count1 == 1:
            v1 = tmp1
        
        
v2 = A[1]
count2 = 0
for i in range(N):
    tmp2 = v2
    v2 = gcd(v2, A[i])
    if v2 == 1:
        count2 += 1
        if count2 == 1: 
            v2 = tmp2

if 1:
    s1 = 1
    s2 = 1
    if count1 == 1 and v1 <= 10 ** 9:
        s1 = v1
    if count2 == 1 and v2 <= 10 ** 9:
        s2 = v2
    print(tmp * max(s1, s2))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc125/tasks/abc125_c

import itertools
from collections import Counter
from collections import defaultdict
import bisect

memo = {}


def gcd(a, b):
    if a in memo:
        if b in memo[a]:
            return memo[a][b]
    ans = gcd_core(a, b)
    if a in memo:
        memo[a][b] = ans
    else:
        memo[a] = {}
        memo[a][b] = ans
    return ans


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


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

    ming = 0

    cand = []

    for i in range(N):
        temp = gcd(A[i], ming)
        # print(temp)
        if temp != ming:
            cand.append(i)
        ming = temp

    # print(index)

    answers = []
    for c in cand:
        ans1 = 0
        for i in range(N):
            if i != c:
                ans1 = gcd(A[i], ans1)
        answers.append(ans1)

    print(max(answers))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
gu = [0 for i in range(N)]
gl = [0 for i in range(N)]
if N == 2:
  if A[0] > A[1]:
    print(A[0])
  else:
    print(A[1])
else:
  max = 0
  gu[0] = A[0]
  for i in range(1,N-1):
    y = gu[i-1]
    x = A[i]
    gu[i] = gcd(y,x)
    
  gl[0] = A[N-1]
  for i in range(1,N-1):
    y = gl[i-1]
    x = A[N-1-i]
    gl[i] = gcd(y,x)

  for i in range(N):
    if i == 0:
      x = gl[N-2]
    elif i == N-1:
      x = gu[N-2]
    else:
      y = gu[i-1]
      x = gl[N-2-i]
      x = gcd(y,x)
    if max < x:
      max = x
  print(max)

Submission status: Accepted

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) #再帰定義
    
list_gcd = [(gcd(A[0],A[1]),False),(A[0],True),(A[1],True)]
#print(list_gcd)

for i in range(2,len(A)):
    next_gcd = []
    for j in list_gcd:
        if j[1]:
            this_gcd = (gcd(j[0],A[i]),True)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
        else:
            this_gcd = (gcd(j[0],A[i]),False)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
                
            this_gcd = (j[0],True)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
    list_gcd = next_gcd
    #print(list_gcd)
         
out = 1
for i in list_gcd:
    if i[0] > out:
        out = i[0]
        
print(out)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

    if len(A) == 3:
        gcd1 = gcd(A[0], A[1])
        gcd2 = gcd(A[0], A[2])
        gcd3 = gcd(A[1], A[2])
        print(max(gcd1, gcd2, gcd3))
        return

    gcd1 = gcd(A[0], A[1])
    gcd2 = gcd(A[0], A[2])
    gcd3 = gcd(A[1], A[2])
    yet_used_gcd = max(gcd1, gcd2, gcd3)
    not_used_gcd = gcd(gcd1, A[2])

    for i in range(3, N):
        yet_used_gcd = gcd(yet_used_gcd, A[i])
        if yet_used_gcd < not_used_gcd:
            yet_used_gcd = not_used_gcd
        not_used_gcd = gcd(not_used_gcd, A[i])

    if yet_used_gcd > not_used_gcd:
        print(yet_used_gcd)
    else:
        print(not_used_gcd)

main()

Submission status: Accepted

Solution code:
# from web
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    b = sorted(make_divisors(a[0]), reverse = True)
    res = b[0]
    for i in b:
        c = [_ % i != 0 for _ in a]
        if sum(c) <= 1:
            res = i
            break
    a2 = a[1:]
    a2.sort()
    b2 = sorted(make_divisors(a2[0]), reverse = True)
    res2 = b2[0]
    for i in b2:
        c = [_ % i != 0 for _ in a]
        if sum(c) <= 1:
            res2 = i
            break
    print(max(res,res2))

Submission status: Accepted

Solution code:
from functools import reduce
import numpy as np


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


def gcd(*n):
    return reduce(_gcd, n)


def my_bisect(x):

    def find_pos(left, right):
        return left + (right - left - 1) // 2

    def func(left, right, prev):
        if right - left == 1:
            return [left]
        if right - left == 2:
            return [left, left+1]
        pos = find_pos(left, right)
        g1 = gcd(*x[left:pos+1])
        g2 = gcd(*x[pos+1:right])
        if prev is not None:
            g1, g2 = gcd(g1, prev), gcd(g2, prev)
        if g1 < g2:
            return func(left, pos + 1, max(g1, g2))
        else:
            return func(pos + 1, right, max(g1, g2))
    return func(0, len(x), None)


N = int(input())
A = list(map(int, input().split()))
print(max([gcd(*np.delete(A, i)) for i in my_bisect(A)]))