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:
def gcd (a, b):
	x1, x2 = 0, 1
	y1, y2 = 1, 0
	q = 0
	while b != 0:
		x1, x2 = x2, x1 - q * x2
		y1, y2 = y2, y1 - q * y2
		q = a // b
		a, b = b, a % b
	return a, x2, y2



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

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

max_d = max(d_right[1], d_left[N-2])
for i in range(1, N-1):
	max_d = max(max_d, gcd(d_left[i-1], d_right[i+1])[0])
print(max_d)

Submission status: Accepted

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


def kari():
    a = list(map(int, input().split()))
    b = map(int, input().split())


def start_process(num, data):
    kouyakusuu1, kouyakusuu2, kouyakusuu3 = gcd(data[0], data[1]), max(data[0], data[1]), min(data[0], data[1])
    # print(kouyakusuu2, kouyakusuu3)

    for i in range(2, num):
        if i == 2:
            a = gcd(data[i], kouyakusuu2)
            b = gcd(data[i], kouyakusuu3)
            kari1 = max(a, b)
            kari2 = kouyakusuu1

            kari3 = gcd(data[i], kouyakusuu1)
        else:
            kari1 = gcd(data[i], kouyakusuu2)
            kari2 = kouyakusuu1

            kari3 = gcd(data[i], kouyakusuu1)



        kouyakusuu1 = kari3
        kouyakusuu2 = max(kari1, kari2)



    print(max(kouyakusuu1, kouyakusuu2))

# def start_process(num, data):
#     for i in range(num)

def main():
    num = int(input())
    data = list(map(int, input().split()))
    start_process(num, data)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import fractions

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


def inl():
    return list(map(int, input().split()))


def inls():
    return input().split()


def Yesif(cond):
    print('Yes' if cond else 'No')


def YESIF(cond):
    print('YES' if cond else 'NO')


def yesif(cond):
    print('yes' if cond else 'no')


N = inp()
A = inl()

ans = set()
ans.add(A[1])
gcd = A[0]
for i, a in enumerate(A):
    if i == 0:
        continue

    news = set()
    for ss in ans:
        news.add(fractions.gcd(ss, a))
    ans = news

    new_gcd = fractions.gcd(gcd, a)
    if new_gcd < gcd:
        ans.add(gcd)
    gcd = new_gcd

print(max(ans))

Submission status: Accepted

Solution code:
import fractions

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

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

Submission status: Accepted

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

new_ans = 0
li = [0]*n
li2 = [0]*n

li[0] = a[0]
li2[n-1] = a[n-1]
for i in range(1,n):
    li[i] =fractions.gcd(li[i-1], a[i])

for i in range(1,n)[::-1]:
    li2[i-1] =fractions.gcd(li2[i], a[i-1])

ans =0
for i in range(1,n-1):
    tmp = fractions.gcd(li[i-1],li2[i+1])
    if ans < tmp:
        ans = tmp
ans = max(ans, li[n-2], li2[1])
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
g = A[0]
mini_index_1 = 0
mini_index_2 = 0
glist = [0]
for i in range(N):
    ng = gcd(g, A[i])
    if ng < g:
        mini_index_1 = i
        mini_index_2 = i-1
        g = ng
        glist.append(i)
# print(mini_index_1)

ans = 1
gcddd = 0

for gindex in glist:
    gcddd = 0
    for i in range(N):
        if gindex == i:
            continue
        else:
            if gcddd == 0:
                gcddd = A[i]
            else:
                gcddd = gcd(gcddd, A[i])
    ans = max(ans, gcddd)
print(ans)

Submission status: Accepted

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

def gcd(x,y):
    if(y==0):
        return x
    return gcd(y,x%y)
pre = [dat[0]]
for d in dat[1:]:
    pre.append(gcd(pre[-1],d))
pre = [-1]+pre[:-1]
pos = [dat[-1]]
for d in dat[:-1][::-1]:
    pos.append(gcd(pos[-1],d))
pos = pos[::-1]
pos = pos[1:]+[-1]
res = 1
for i in range(n):
    if pre[i]==-1:
        res = max(res,pos[i])
    elif pos[i]==-1:
        res = max(res,pre[i])
    else:
        res = max(res,gcd(pre[i],pos[i]))
print(res)

Submission status: Accepted

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

def GCM(m,n):
    while n>0:
        m,n = n,m%n
    return m

fGCM = [0 for i in range(N)]
bGCM = [0 for i in range(N)]

fGCM[0]=A[0]
bGCM[N-1]=A[N-1]

for i in range(N-1):
    j = N-1-i
    fGCM[i+1]=GCM(fGCM[i],A[i+1])
    bGCM[j-1]=GCM(bGCM[j],A[j-1])

eGCM=[0 for i in range(N)]
eGCM[0]=bGCM[1]
eGCM[N-1]=fGCM[N-2]
for i in range(1,N-1):
    eGCM[i] = GCM(fGCM[i-1],bGCM[i+1])

ans = max(eGCM)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
end = sorted(a)[1]

for i in range(end+1, 0, -1):
  x = 0
  for j in a:
    if j % i != 0:
      x += 1
    if x >= 2:
      break
  if x <= 1:
    print(i)
    break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate

try:
    from math import gcd
except Exception:
    from fractions import gcd

def solve(N: int, A: "List[int]"):
    gcds0 = list(accumulate(A, gcd))
    gcds1 = list(accumulate(A[::-1], gcd))[::-1]

    ret = 0
    for i in range(N):
        if i == 0:
            ret = max(ret, gcds1[i+1])
        if i == (N-1):
            ret = max(ret, gcds0[i-1])
        else:
            ret = max(ret, gcd(gcds0[i-1], gcds1[i+1]))
    print(ret)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
import fractions
a_list=list(map(int,input().split()))
f_list=[a_list[0]]
r_list=[a_list[n-1]]
for i in range(n-1):
    f=fractions.gcd(f_list[i],a_list[i+1])
    r=fractions.gcd(r_list[i],a_list[n-i-2])
    f_list.append(f)
    r_list.append(r)
Max=max(r_list[n-2],f_list[n-2])
for i in range(n-2):
    number=fractions.gcd(f_list[i],r_list[n-3-i])
    if number>Max:
        Max=number
print(Max)

Submission status: Accepted

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
import heapq
import math
import bisect


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


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

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

    ans = 0
    for i in range(N):
        ans = max(ans, gcd(pre[i], suf[i+1]))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
K = 17
N = int(input())
A = [0] * (2**K-1) + [int(a) for a in input().split()] + [0] * (2**K-N)
for i in range(2**K-1)[::-1]:
    A[i] = gcd(A[2*i+1], A[2*i+2])

def calc(i0):
    g = 0
    for k in range(K):
        i = (i0^(1<<k)) + (2**K-1)
        for l in range(k):
            i = (i-1) // 2
        g = gcd(g, A[i])
    return g
ma = 0
for i in range(N):
    ma = max(ma, calc(i))
print(ma)

Submission status: Accepted

Solution code:
import functools
import fractions
N = int(input())
A = [int(x) for x in input().split()]
GCD = functools.reduce(fractions.gcd, A)
B = sorted([a // GCD for a in A], reverse=True)
def ggcd(B, cancel):
  gcd = B[0]
  for b in B[1:]:
    _gcd = fractions.gcd(gcd, b)
    if _gcd == 1 and cancel > 0:
      _gcd = gcd
      cancel -= 1
    gcd = _gcd
  return gcd
print(GCD * max(ggcd(B, 1), ggcd(B[1:], 0)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

ans = max(cum_left[N - 2], cum_right[N - 2])
for i in range(1, N - 1):
    ans = max(ans, gcd(cum_left[i - 1], cum_right[N - 2 - i]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

N=int(input())
A=list(map(int,input().split()))
X=[A[0]]
Y=[A[-1]]
for i in range(N):
    X.append(gcd(X[-1],A[i]))
    Y.append(gcd(Y[-1],A[N-1-i]))
X=X[1:]
Y=Y[1:]
Y=Y[::-1]
ans=1
for i in range(N):
    if i==0:
        ans_=Y[i+1]
    elif i==N-1:
        ans_=X[i-1]
    else:
        ans_=gcd(X[i-1],Y[i+1])
    ans=max(ans,ans_)
print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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

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

g = gcd(A[0], A[1])
X = set([A[0], A[1]])

for a in A[2:]:
  XX = set([g])
  g = gcd(g, a)
  for x in X:
    XX.add(gcd(x, a))
  X = XX

print(max(X))

Submission status: Accepted

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

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    left = [0] * n
    right = [0] * n
    left[0] = arr[0]
    right[-1] = arr[-1]
    for i in range(1, n):
        left[i] = gcd(left[i - 1], arr[i])
        right[n - i - 1] = gcd(right[n - i], arr[n - i - 1])
    m = max(left[-2], right[1])
    for i in range(1, n - 1):
        m = max(m, gcd(left[i - 1], right[i + 1]))
    print(m)
    return 0

main()

Submission status: Accepted

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

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

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

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

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


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

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
fir = l[0]
sec = l[1]
lfir = []
for i in range(1,int(fir**.5)+2):
  if fir % i == 0:
    lfir.append(i)
    lfir.append(fir//i)
for i in range(1,int(sec**.5)+2):
  if sec % i == 0:
    lfir.append(i)
    lfir.append(sec//i)
ok = 1
lfir = sorted(list(set(lfir)))
for i in lfir:
  cnt = 0
  for j in l:
    if j%i:
      cnt += 1
  if cnt < 2:
    ok = i
print(ok)

Submission status: Accepted

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

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

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

bad_id = 0
max_div = 1
for j in range(10):
    if j == 5:
        bad_id == 0
        a.reverse()
    bid = bad_id
    init = False
    for i, item in enumerate(a):
        if i == bid:
            continue
        if not init:
            val = item
            div = val
            init = True
        else:
            val = gcd(div, item)
            if val != div:
                bad_id = i
                div = val
    max_div = max(div, max_div)
    
print(max_div)

Submission status: Accepted

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

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

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

    # divisors.sort()
    return divisors

if n == 2:
    print(max(a))
else:
    list1 = make_divisors(a[0])
    list2 = make_divisors(a[1])
    list1.sort()
    list2.sort()
    flag1 = 0
    cand1 = 0
    for i in range(len(list1)):
        flag1 = 0
        for j in range(n):
            if a[j] % list1[i] != 0:
                flag1 += 1
        if flag1 <= 1:
            cand1 = list1[i]
    cand2 = 0
    for i in range(len(list2)):
        flag2 = 0
        for j in range(n):
            if a[j] % list2[i] != 0:
                flag2 += 1
        if flag2 <= 1:
            cand2 = list2[i]
    print(max(cand1,cand2))

Submission status: Accepted

Solution code:
from fractions import gcd


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


gcd_l = [0] * n
gcd_r = [0] * n
for i in range(n):
    if i == 0:
        gcd_l[i] = A[i]
        gcd_r[-i-1] = A[-i-1]
    else:
        gcd_l[i] = gcd(gcd_l[i-1], A[i])
        gcd_r[-i-1] = gcd(gcd_r[-i], A[-i-1])

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

Submission status: Accepted

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

N=int(input())
A=list(map(int,input().split()))
d1,d2=[],[]
g1,g2=A[0],A[-1]
d1.append(g1)
d2.append(g2)
for n in range(1,N-1):
    g1=gcd(g1,A[n])
    g2=gcd(g2,A[-1-n])
    d1.append(g1)
    d2.append(g2)
dmax=max(d1[N-2],d2[N-2])
for n in range(N-2):
    d=gcd(d1[n],d2[N-3-n])
    if d>dmax:
        dmax=d
print(dmax)

Submission status: Accepted

Solution code:
def gcd(a, b):
  if a < b:
    a, b = b, a
  if b == 0:
    return a
  c = a % b
  return gcd(b, c)
  
n=int(input())
a=list(map(int,input().split()))
g1=[0 for i in range(n)]
g2=[0 for i in range(n)]
g1[0]=a[0]
g2[n-1]=a[n-1]
for i in range(1,n):
  g1[i]=gcd(g1[i-1],a[i])
for i in range(n-2,-1,-1):
  g2[i]=gcd(g2[i+1],a[i])
ans=1
for i in range(n-2):
  a=gcd(g1[i],g2[i+2])
  ans=max(ans,a)
ans=max(ans,g1[n-2],g2[1])
print(ans)

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools
import fractions

# ひとつ入力
n = int(input())
# リストに入れる
a = [int(i) for i in input().split()]

hidari = [0]*n
migi   = [0]*n
hidari[0] = a[0]
for i in range(1,n):
    hidari[i]=fractions.gcd(hidari[i-1],a[i])
migi[n-1] = a[n-1]
for i in range(n-2,-1,-1):
    migi[i]=fractions.gcd(migi[i+1],a[i])

saidai=max(migi[1],hidari[n-2])
for i in range(1,n-1):
    saidai = max(saidai, fractions.gcd(hidari[i-1],migi[i+1]))
#    print(fractions.gcd(hidari[i-1],migi[i+1]))
#print(hidari,migi)
print(saidai)

Submission status: Accepted

Solution code:
import collections as c
ip = lambda : map(int, input().split())

#################
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
dp = [[0,0,0] for _ in range(N+1)]
dp[1] = [A[0],0,A[0]]
dp[2] = [gcd(dp[1][0],A[1]),dp[1][0],max(A[1] ,gcd(dp[1][2],A[1]))]
for i in range(3,N+1):
    dp[i][0] = gcd(dp[i-1][0],A[i-1])
    dp[i][1] = dp[i-1][0]
    dp[i][2] = max(gcd(dp[i-1][1],A[i-1]),gcd(dp[i-1][2],A[i-1]))

print(max(dp[N]))

Submission status: Accepted

Solution code:
import fractions as math
n=int(input())
a=list(map(int,input().split()))
s=[0 for i in range(n)]
e=[0 for i in range(n)]
l=[0 for i in range(n)]
s[0]=a[0]
e[-1]=a[-1]
for i in range(1,n):
    s[i]=math.gcd(s[i-1],a[i])
    e[n-1-i]=math.gcd(e[n-i],a[n-1-i])
for i in range(1,n-1):
    l[i]=math.gcd(s[i-1],e[i+1])
l[0]=e[1]
l[-1]=s[n-2]
print(max(l))

Submission status: Accepted

Solution code:
import math

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

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

M = A[-1]
P = [1,M]
for k in range(2,math.ceil(math.sqrt(M))+1):
    if M % k == 0:
        P.append(k)
        P.append(M//k)
M = A[-2]
P.append(M)
for k in range(2,math.ceil(math.sqrt(M))+1):
    if M % k == 0:
        P.append(k)
        P.append(M//k)
P = set(list(P))
ans = 1
for p in P:
    t = 0
    for k in range(N):
        if A[k]%p != 0:
            t += 1
        if t == 2:
            break
    if t <= 1:
        ans = max(ans,p)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split(" ")]
f = [0] * n
r = [0] * n

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

f[0] = a[0]
r[0] = a[n - 1]
for i in range(1, n):
    f[i] = gcd(f[i - 1], a[i])
    r[i] = gcd(r[i - 1], a[n - i - 1])

m = max(f[n - 2], r[n - 2])
for i in range(0, n - 2):
    g = gcd(f[i], r[n - i - 3])
    if g > m:
        m = g

print(m)

Submission status: Accepted

Solution code:
#テンプレート
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
#テンプレート終わり

N = int(input())
A = list(map(int,input().split()))
cumulativeGcdLeft = [A[0]]
cumulativeGcdRight = [A[N-1]]
for i in range(N-1):
    cumulativeGcdLeft.append(fractions.gcd(A[i+1],cumulativeGcdLeft[i]))
    cumulativeGcdRight.append(fractions.gcd(A[N-1-i-1],cumulativeGcdRight[i]))
ans = 1
# print(cumulativeGcdLeft)
# print(cumulativeGcdRight)
for i in range(N):
    if i == 0:
        candidate = cumulativeGcdRight[N-2]
    elif i == N-1:
        candidate = cumulativeGcdLeft[N-2]
    else:
        left = cumulativeGcdLeft[i-1]
        right = cumulativeGcdRight[N-i-2]
        candidate = fractions.gcd(left,right)
        # print(i,left,right,candidate)
    ans = max(ans,candidate)
print(ans)

Submission status: Accepted

Solution code:
#0WA n==1 mod saikikilimit exit
import sys
input = sys.stdin.readline

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


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

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

GCD=[]
GCD_INV=[]


x=A[0]
for a in A:
    x=gcd(x,a)
    GCD.append(x)

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

GCD_INV=GCD_INV[::-1]
    
ANS=max(GCD[-2],GCD_INV[1])

for i in range(1,N-1):
    ANS=max(ANS,gcd(GCD[i-1],GCD_INV[i+1]))

print(ANS)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from fractions import gcd

def main():
    N = II()
    A = LI()
    G1 = [A[0]]
    for a in A:
        G1.append(gcd(G1[-1], a))
    G2 = [A[-1]]
    for a in A[::-1]:
        G2.append(gcd(G2[-1], a))
    G2 = G2[::-1]
    G1[0] = A[-1]
    G2[-1] = A[0]
    ans = 1
    for g1, g2 in zip(G1, G2[1:]):
        ans = max(ans, gcd(g1, g2))
    return ans

print(main())

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

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

    if N==2:
        print(max(a))
        return 

    l = [-1] * N
    r = [-1] * N

    l[0] = a[0]
    r[-1] = a[-1]

    for i in range(1, N):
        l[i] = gcd(l[i-1], a[i])

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

    # print(l)
    # print(r)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
def gcd(a, b):
  if b > a:
    a, b = b, a
  r = a % b
  if r == 0:
    return b
  return gcd(b, r)

from_left = [1] * N
from_left[0] = A[0]
from_right = [1] * N
from_right[N-1] = A[N-1]

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

#print(from_left)
#print(from_right)
res = 0
for i in range(N):
  if i == 0:
    res = max(res, from_right[1])
  elif i == N-1:
    res = max(res, from_left[N-2])
  else:
	  res = max(res, gcd(from_left[i-1], from_right[i+1]))

print(res)

Submission status: Accepted

Solution code:
import fractions

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

X=[A[0]]
Y=[A[-1]]


a=A[0]
for i in range(1,n):
    a=fractions.gcd(A[i],a)
    X.append(a)
b=A[-1]
for i in range(1,n):
    b=fractions.gcd(A[-i-1],b)
    Y.append(b)
    
    
M=[X[-1],Y[-1],X[-2],Y[-2]]
for i in range(1,n-1):
    m=fractions.gcd(X[i-1],Y[-i-2])
    M.append(m)
print(max(M))

Submission status: Accepted

Solution code:
from fractions import gcd

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

if n == 1:
    ans = 1000000000
elif n == 2:
    ans = max(a)
else:
    l = [a[0]]
    for i in range(1, n):
        l.append(gcd(l[-1], a[i]))
    r = [a[-1]]
    for i in range(n - 1, -1, -1):
        r.append(gcd(r[-1], a[i]))
    r = list(reversed(r))
    ans = max(l[-2], r[1])
    for i in range(1, n - 1):
        ans = max(ans, gcd(l[i - 1], r[i + 1]))
print(ans)

Submission status: Accepted

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

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

gcd_from_left = [0]*N # 自分のindexは含まないようなもの
gcd_from_right = [0]*N

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

ans = 0

for a,b in zip(gcd_from_left, gcd_from_right):
  x = gcd(a,b)
  if ans < x:
    ans = x
    
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N, *A = map(int, open(0).read().split())

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

Submission status: Accepted

Solution code:
from fractions import gcd

def input_ints():
    return list(map(int, input().split()))

def main():
    n = int(input())
    a = input_ints()
    x = [a[0]]
    y = [a[-1]]
    for i in range(n-1):
        x.append(gcd(x[-1], a[i + 1]))
        y.append(gcd(y[-1], a[n - i - 2]))
    ans = max(x[-2],y[-2])
    for i in range(1, n-1):
        ans = max(ans,gcd(x[i-1],y[-i-2]))
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    gcd1 = [0] * N  # [0..a]
    gcd2 = [0] * N  # [a..N-1]
    gcd1[0] = A[0]
    for i in range(1,N):
        gcd1[i] = gcd(gcd1[i-1],A[i])
    gcd2[N-1] = A[N-1]
    for i in range(N-2,-1,-1):
        gcd2[i] = gcd(gcd2[i+1],A[i])

    ans = 0
    ans = max(ans, gcd2[1])
    ans = max(ans, gcd1[N-2])
    for i in range(1,N-1):
        ans = max(ans, gcd(gcd1[i-1], gcd2[i+1]))
    return ans

print(solve())

Submission status: Accepted

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

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

mae = [a[0]]

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

#print(mae)

a = list(reversed(a))
usi = [a[0]]
for i in range(1,n):
    usi.append(gcd(usi[i-1],a[i]))
usi = list(reversed(usi))
#print(usi)

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

ans = max(ans, mae[-2])

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from fractions import gcd
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    n = int(input())
    a = sorted(readlist())

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

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

    res = 0
    for i in range(n):
        res = max(res, gcd(gcd_arr[i], gcd_arr_rev[i + 1]))
    print(res)


# region template

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


class ostream:
    def __lshift__(self, a):
        if a is endl:
            sys.stdout.write(b"\n")
            sys.stdout.flush()
        else:
            sys.stdout.write(str(a))
        return self


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
cout, endl = ostream(), object()

readline = sys.stdin.readline
readlist = lambda var=int: [var(n) for n in readline().split()]
input = lambda: readline().rstrip(b"\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import fractions

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    GCDbefore = {}
    GCDafter = {}
    GCDbefore[-1] = 0
    for i in range(N):
        GCDbefore[i] = fractions.gcd(GCDbefore[i-1], A[i])
    GCDafter[N] = 0
    for i in range(N):
        GCDafter[N-1-i] = fractions.gcd(GCDafter[N-i], A[N-1-i])
    ans = 0
    for i in range (N):
        ans = max(ans, fractions.gcd(GCDbefore[i-1], GCDafter[i+1]))
    print(ans)

Submission status: Accepted

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


@functools.lru_cache(maxsize=None)
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


max_gcd = [[0]*n for i in range(3)]
max_gcd[0][0] = a[0]
max_gcd[0][1] = gcd(a[0], a[1])
max_gcd[1][1] = a[0]
max_gcd[2][1] = a[1]

for i in range(2, n):
    max_gcd[0][i] = gcd(max_gcd[0][i-1], a[i])
    max_gcd[1][i] = max(max_gcd[0][i-1], gcd(max_gcd[1][i-1], a[i]))
    max_gcd[2][i] = max(max_gcd[0][i-1], gcd(max_gcd[2][i-1], a[i]))

print(max(max_gcd[1][n-1],max_gcd[2][n-1]))

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
p = aaa[0]
f = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    f.append(p)
aaa.reverse()
p = aaa[0]
b = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    b.append(p)
b.reverse()

f = [b[0]] + f
b = b + [f[-1]]

print(max(gcd(p, q) for p, q in zip(f, b)))