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):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
 
n = int(input())
a = list(map(int,input().split()))
 
b = [a[0]]
c = [a[-1]]
 
for i in range(1,n):
     j = n-1-i
     b.append(gcd(b[-1],a[i]))
     c.append(gcd(c[-1],a[j]))
     
ans = max(b[-2],c[-2])
for i in range(n):
     ans = max(ans,gcd(b[i],c[n-3-i]))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

gcd_num = a_list[0]
for a in a_list[1:]:
    gcd_num = gcd(gcd_num, a)

b_list = []

for a in a_list:
    b_list.append(a // gcd_num)

first = False
b_list.sort(reverse=True)
gcd_b = b_list[0]
for i, b in enumerate(b_list[1:]):
    tmp = gcd(gcd_b, b)
    if tmp == 1:
        if not first:
            first = True
            if i == 0:
                gcd_b = max(gcd_b, b)
            gcd_b = gcd_b
        else:
            gcd_b = 1
            break
    else:
        gcd_b = tmp
first = False
gcd_b3 = b_list[1]
b_list.append(b_list[0])

for i, b in enumerate(b_list[1:]):
    tmp = gcd(gcd_b3, b)
    if tmp == 1:
        if not first:
            first = True
            gcd_b3 = gcd_b3
        else:
            gcd_b3 = 1
            break
    else:
        gcd_b3 = tmp

print(gcd_num * max(gcd_b, gcd_b3))

Submission status: Accepted

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

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


def get_custum(xlist):
    prev = None
    gcm_list = []
    for a in xlist:
        if prev is None:
            gcm_list.append(a)
            prev = a
            continue
        ret = calc_gcm(a, prev)
        gcm_list.append(ret)
        prev = ret

    for boundary, gcm in enumerate(gcm_list):
        if gcm == gcm_list[-1]:
            break

    gcm_1 = None
    for i, a in enumerate(xlist):
        if i == boundary - 1:
            continue
        if gcm_1 is None:
            gcm_1 = a
            continue
        gcm_1 = calc_gcm(a, gcm_1)

    gcm_2 = None
    for i, a in enumerate(xlist):
        if i == boundary:
            continue
        if gcm_2 is None:
            gcm_2 = a
            continue
        gcm_2 = calc_gcm(a, gcm_2)

    return max(gcm_1, gcm_2)

ret1 = get_custum(alist)
alist.reverse()
ret2 = get_custum(alist)

print(max(ret1, ret2))

Submission status: Accepted

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[0]=A[N-1]
for i in range(1,N-1):
   l[i]=gcd(l[i-1],A[i])
   r[i]=gcd(r[i-1],A[N-1-i])
gcdlist = [1,l[N-2],r[N-2]]
for i in range(N-2):
   gcdlist.append(gcd(l[i],r[N-3-i]))

print(max(gcdlist))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(sys.getrecursionlimit())
N = int(input())
A = list(map(int,input().split(" ")))

def gcd (a: int,b: int) -> int:
    if a < b: a,b = b,a
    return a if b == 0 else gcd(b,a%b)
def lcm (a: int,b: int) -> int:
    return a // gcd(a,b) * b

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


if N == 2:
    print(max(A))
    exit(0)
else:
    ans = max(gcdBackWard[1],gcdForward[N-2])
    for i in range(1,N-1):
        ans = max(ans,gcd(gcdForward[i-1],gcdBackWard[i+1]))
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

left_gcd = deque()
left_gcd.append(0)
right_gcd = deque()
right_gcd.append(0)

for i in range(n):
    left_gcd.append(gcd(left_gcd[-1], a[i]))
    right_gcd.appendleft(gcd(right_gcd[0], a[(n - 1) - i]))

max_gcd = 0

for i in range(n):
    get_gcd = gcd(left_gcd[i], right_gcd[i + 1])
    if get_gcd > max_gcd:
        max_gcd = get_gcd

print(max_gcd)

Submission status: Accepted

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

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

l=make_divisors(a[0])
l2=make_divisors(a[1])
le=len(l)
le2=len(l2)         
an=[0]*le
an2=[0]*le2
for i in range(n):
    for j in range(le):
        if a[i]%l[j]==0:
            an[j]+=1
    for j in range(le2):
        if a[i]%l2[j]==0:
            an2[j]+=1
ans=1
ans2=1
for i in range(le):
    if an[i]>=n-1:
        ans=max(ans,l[i])
for i in range(le2):
    if an2[i]>=n-1:
        ans2=max(ans2,l2[i])

print(max(ans,ans2))

Submission status: Accepted

Solution code:
import math
import fractions
from collections import Counter as ct

def gcd_list(l):
    for n,i in enumerate(l):
        if n==0:cur=i
        cur=fractions.gcd(cur,i)
    return cur

def yakusulist(n):
    ans=[]
    for i in range(1,int(math.sqrt(n+1))+1):
        if n%i==0:
            ans.append(i)
            ans.append(n//i)
    return(set(ans))
    
def warennnokaomaera(n):
    warenai=0
    for k,i in enumerate(A):
        if i%n and warenai==0:
            warenai+=1
            continue
        if i%n and warenai:return(False)
    return(True)

N=int(input())
data=[int(i) for i in input().split()]
datagcd=gcd_list(data)
A=[i//datagcd for i in data]
if N>2:
    co=ct(A)
    alpha=sorted(co.keys())
    if len(alpha)>=3:
        min3=[alpha[0],alpha[1],alpha[2]]
        p,q,r=[yakusulist(n) for n in min3]
        pq=p&q
        qr=q&r
        rp=r&p
        overtwo=pq|qr|rp
        overtwo=sorted(list(overtwo),reverse=True)
        for i in overtwo:
            if warennnokaomaera(i):
                print(datagcd*i)
                break
    elif len(alpha)==2:#Aの数の種類が2種類以下->1個書き換えで違う数ってどっちかが一個じゃないと無理、それ以外はそのまま
        if co[alpha[0]]==1:
            print(datagcd*alpha[1])
        elif co[alpha[1]]==1:
            print(datagcd*alpha[0])
        else:print(datagcd)
    else:print(datagcd)
else:print(max(data))

Submission status: Accepted

Solution code:
N = input()

A = map(int,raw_input().split())

B = []
C = []

for i in A:
    if i not in B:
        B.append(i)
    elif i not in C:
        C.append(i)

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

ans = 0;
for i in range(len(B)):
    res = 0
    for j in range(len(B)):
        if B[i] not in C:
            if i == j:
                continue
        res = gcd(res,B[j])
    ans = max(ans,res)
        

if ans == 0:
    if len(B) == 1:
        print B[0]
    else:
        print 1
else:
    print ans

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter
N = int(input())
A = list(map(int,input().split()))

ctr = Counter(A)
solos = []
for k,v in ctr.items():
    if v > 1: continue
    solos.append(k)
solos.sort()

if len(solos) == 0:
    g = A[0]
    for a in A:
        g = gcd(g,a)
    print(g)
    exit()

g1 = g2 = None
for k in ctr.keys():
    if k != solos[0]:
        if g1 is None:
            g1 = k
        else:
            g1 = gcd(g1,k)
    if len(solos) > 1 and k != solos[1]:
        if g2 is None:
            g2 = k
        else:
            g2 = gcd(g2,k)

if g2 is None: g2 = 0
print(max(g1,g2))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
def gcd(a, b):
    P = max(a, b)
    Q = min(a, b)
    R = P%Q
    P = Q
    Q = R
    while R != 0:
        R = P%Q
        P = Q
        Q = R
    return P

candidate = [(gcd(A[0], A[1]), True), (A[0], False), (A[1], False)]
for i in range(2, N):
    nxt_cand = []
    for v, b in candidate:
        if(v == 1):
            continue
        if(b == True and gcd(v, A[i]) < v):
            nxt_cand.append((v, False))
            nxt_cand.append((gcd(v, A[i]), True))
        else:
            nxt_cand.append((gcd(v, A[i]), b))
    if(len(nxt_cand)==0):
        nxt_cand = [(1, False)]
    candidate = nxt_cand[::]

print(max(candidate)[0])

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
# N=3
# A=[12 ,15 ,18]
l=[0]*N
r=[0]*N
l[0]=A[0]
r[0]=A[N-1]
for i in range(1,N-1):
    l[i]=gcd(l[i-1],A[i])
    r[i]=gcd(r[i-1],A[N-1-i])    
gcdlist = [1,l[N-2],r[N-2]]
for i in range(N-2):
    gcdlist.append(gcd(l[i],r[N-3-i]))
#print(gcdlist)
print(max(gcdlist))

Submission status: Accepted

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


def g():
  from functools import reduce
  n = int(input())
  vs = list(map(int, input().split()))
  
  while True:
    n = len(vs)
    
    if n < 10:
      mrr = 0
      for i, v in enumerate(vs):
        rr = reduce(gcd, vs[:i]+vs[i+1:])
        mrr = max(rr, mrr)
      return mrr
    
    v1 = vs[:n//2]
    v2 = vs[n//2:]
    
    r1 = reduce(gcd, v1)
    r2 = reduce(gcd, v2)
    if r1 == r2:
      return r1
    if r1 > r2:
      vs = v2
    else:
      vs = v1
  
  
print(g())

Submission status: Accepted

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

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

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

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

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

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

    # メモ化で高速化?
    def divisions(self, n):
        if n in self.ds_memo:
            return self.ds_memo[n]

        for c in self.T:
            if n % c == 0:
                rs = set([c])
                for cc in self.divisions(n // c):
                    rs.add(cc)
                    rs.add(cc * c)
                self.ds_memo[n] = rs
                return rs

        rs = set([n])
        self.ds_memo[n] = rs
        return rs

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


def main():
    n = I()
    a = sorted(LI())
    pr = Prime(10**9)
    p = collections.defaultdict(int)

    for b in a:
        for k in pr.divisions(b):
            p[k] += 1

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

    return r


print(main())

Submission status: Accepted

Solution code:
N=int(input())

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


a=sorted(a)

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



l=1
r=10**9
a.sort()
ans=[a[0],a[1]]
k=-1
nexts=0
stock=0
s_2=-1


ans=gcd(a[0],a[1])
for j in range(2,len(a)):
    if(stock!=2):
        s=gcd(ans,a[j])
        if(s<ans and stock==0):
            stock+=1
            nexts=s
        elif(s<ans and stock==1):
            if(s==nexts):
                stock-=1
                ans=s
            else:
                stock+=1
                s_2=s
                s_1=nexts
                #ans=max(s,nexts)
    else:
        s_1=gcd(s_1,a[j])
        s_2=gcd(s_2,a[j])
if(s_2==-1):
    ans1=ans
else:
    ans1=max(s_1,s_2)
    
ans=a[0]
for j in range(2,len(a)):
    ans=gcd(ans,a[j])
ans2=ans
ans=a[1]
for j in range(2,len(a)):
    ans=gcd(ans,a[j])

ans3=ans

    

print(max([ans1,ans2,ans3]))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
anses=set()
for i in [0,1]:
    for j in range(1, int(a[i]**0.5)+1):
        if a[i] % j == 0:
            anses.add(j)
            if j != a[i] // j:
                anses.add(a[i] // j)
anses=sorted(anses,reverse=True)
for ans in anses:
    solvenum=0
    for j in a:
        if j%ans==0:
            solvenum+=1
    if solvenum==n or solvenum==n-1:
        print(ans)
        break

Submission status: Accepted

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

def gcd_array(A):
    n = len(A)
    s = A[0]
    i = 1
    Down = [0]
    while(i < n):
        t = gcd(s,A[i])
        if t < s:
            Down.append(i)
        s = t
        i += 1
    return s,Down

if __name__ == "__main__":
    N = int(input())
    B = list(map(int,input().split()))
    max = 0
    d,Down = gcd_array(B)
    C = [i//d for i in B]
    c = C[0]
    K = 1
    for j in Down:
        A = [i for i in C]
        c = A.pop(j)
        l = gcd_array(A)[0]
        if K < l:
            K = l
    print(K * d)

Submission status: Accepted

Solution code:
import copy

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


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


def calc(B):
    lo, hi = 1, 10 ** 9 + 1
    while abs(hi - lo) > 1:
        X = copy.deepcopy(B)
        m = (hi + lo) // 2

        skipped = False
        while len(X) > 1:
            a, b = X.pop(), X.pop()
            GCD = gcd(a, b)
            if GCD < m:
                if skipped is False:
                    skipped = True
                    X.append(a)
                    continue
                else:
                    hi = m
                    break
            X.append(GCD)
        else:
            if X[0] >= m:
                lo = m
            else:
                hi = m
    return lo


ans1 = calc(A)
ans2 = calc(A[::-1])

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

input()
a = list(map(int, input().split()))
b = list(accumulate(a, gcd))
c = list(accumulate(reversed(a), gcd))
print(max(b[-2], c[-2], *map(gcd, b[:-2], c[-3::-1])))

Submission status: Accepted

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

A.sort()
flag = 0

for i in reversed(range(int(A[1])+1)):
    for k in range(N):
        if A[k]%i != 0:
            flag+=1
            if flag >1:
                flag = 0
                break
        if k >= N-1:
            print(i)
            exit()

Submission status: Accepted

Solution code:
'''
import math

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

def gcd_list(arr):

    ans = arr[0]
    for c in arr[1::]:
        ans = gcd(ans , c)
    return ans
'''
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

N = int(input())

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

af = A[0]
ag = A[1]

F = make_divisors(af)
G = make_divisors(ag)
F.sort(reverse=True)
G.sort(reverse=True)
del F[-1]
del G[-1]

'''
print(F)
print(G)
'''

ansf = 1
ansg = 1

for i in F:
    count = 0
    for j in A:
        if j % i != 0:
            count += 1
            if count == 2:
                break

    if count == 1:
        ansf = i
        break
    if count == 0:
        ansf = i
        break

for i in G:
    count = 0
    for j in A:
        if j % i != 0:
            count += 1
            if count == 2:
                break

    if count == 1:
        ansg = i
        break

print(max(ansf,ansg))
'''
g = gcd_list(A)
print(g)

for i in range(N):
    tmp = A.pop(0)
    if g < gcd_list(A):
        g = gcd_list(A)
    A.append(tmp)

print(g)
'''

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
from fractions import gcd
 
def all_gcd(numbers):
    result = numbers[0]
    for v in numbers:
        result = gcd(result, v)
    return result
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    # x[i] = gcd 0 to i
    x = []
    for i in range(n):
        prev = 0 if i == 0 else x[i - 1]
        x.append(gcd(a[i], prev))
    # y[i] = gcd i to n
    y = [0] * n
    y[n-1] = a[n-1]
    for i in range(2, n + 1):
        y[n-i] = gcd(y[n-i+1], a[n-i])

    max_gcd = 0
    for i in range(n):
        if i == 0:
            now_gcd = y[1]
        elif i == n-1:
            now_gcd = x[n-2]
        else:
            now_gcd = gcd(x[i-1], y[i+1])
        if now_gcd > max_gcd:
            max_gcd = now_gcd
    print(max_gcd)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a = input()
l = map(int, raw_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

def gcd(l):
	l = sorted(l, reverse=True)
	l1 = make_divisors(l[0])
	l2 = make_divisors(l[1])
	l_mix = list(set(l1 + l2))
	l_mix = sorted(l_mix)
	r = 0
	for i in l_mix:
		f = 0
		for j in l:
			if j % i != 0:
				f += 1
			if f > 1:
				break
		if f <= 1:
			r = i
	return r 

print gcd(l)

Submission status: Accepted

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

import fractions
from functools import reduce

def gcds(numbers):
  return reduce(fractions.gcd,numbers)
def gcd2(*numbers):
  return reduce(fractions.gcd,numbers)
  

mx = 0

lisgcd = [0]*n
rlisgcd = [0]*n

lisgcd[0] = lis[0]
rlisgcd[n-1] = lis[n-1]

for i in range(n-1):
  lisgcd[i+1] = gcd2(lisgcd[i],lis[i])
  
for i in range(n-2,-1,-1):
  rlisgcd[i] = gcd2(rlisgcd[i+1],lis[i])
  
for i in range(n):
  if i == 0:
    if mx < rlisgcd[1]:
      mx = rlisgcd[1]
  elif i == n-1:
    if mx < lisgcd[n-1]:
      mx = lisgcd[n-1]
  else:
    t = gcd2(lisgcd[i],rlisgcd[i+1])
    if mx < t:
      mx = t
print(mx)

Submission status: Accepted

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

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

    divisors.sort(reverse=True)
    return divisors

divisors = make_divisors(A[-1])
answer = 1
for d in divisors:
  NG = 0
  for a in A:
    if a % d != 0:
      NG += 1
    if NG > 1:
      break
  if NG <= 1:
    answer = d
    break
    
divisors = make_divisors(A[-2])
for d in divisors:
  NG = 0
  for a in A:
    if a % d != 0:
      NG += 1
    if NG > 1:
      break
  if NG <= 1:
    if d > answer:
      print(d)
    else:
      print(answer)
    break

Submission status: Accepted

Solution code:
import fractions

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

if N == 2:
  print(max(A))
else:
  ans = [A[1], A[0]]
  for i in range(2,N):
    ans_0 = max(fractions.gcd(ans[0], A[i]),fractions.gcd(ans[1], A[i]))
    ans_1 = fractions.gcd(ans[0], ans[1])
    ans = [ans_0, ans_1]
  print(max(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
GA=[a[0]]
GB=[a[n-1]]
G=gcd(a[0],a[1])
GA.append(G)
for i in range(2,n-1):
  G=gcd(G,a[i])
  GA.append(G)
G=gcd(a[n-1],a[n-2])
GB.append(G)
for j in range(n-3,0,-1):
  G=gcd(G,a[j])
  GB.append(G)
GB.reverse()
ans=[]
for i in range(len(GA)-1):
  ans.append(gcd(GA[i],GB[i+1]))
ans.append(GA[len(GA)-1])
ans.append(GB[0])
if n!=2:
  print(max(ans))
else:
  print(max(a))

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
s=[[0]for _ in range(n)]
#print(s)
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(reverse=True)
    return divisors

l.sort()
ans=1

b=l[1]
bl=make_divisors(b)
for i in bl:
    check=True
    for j in range(1,n):
        if l[j]%i!=0:
            check=False
            break
    if check:
        ans=max(ans,i)
        break
a=min(l)
al=make_divisors(a)
#print(al)
for i in al:
    cnt=0
    for j in range(n):
        if l[j]%i!=0:
            cnt+=1
        if cnt>1:
            break
    if cnt==0 or cnt==1:
        ans=max(ans,i)
        break
print(ans)

Submission status: Accepted

Solution code:

n = int(input())
a = [int(m) for m in input().split()]
a.sort()
m0 = a[0]
m1 = a[1]
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



mm0 = make_divisors(m0)
mm1 = make_divisors(m1)
mm = mm0 + mm1
mm.sort()
si = 0
candi = 0
for g in mm:
    si = 0
    for i in range(n):
        if a[i] % g != 0:
            si += 1
            if si == 2:
                break
    else:
        candi = g
print(candi)

Submission status: Accepted

Solution code:
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return a

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

l=[0]*N
l[0]=a[0]

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

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

ans=0
for i in range(N):
    if i==0: tmp=r[1]
    elif i==N-1: tmp=l[N-2]
    else: tmp=egcd(l[i-1],r[i+1])
    ans=max(tmp,ans)

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
read = input
n = int(read())
A = list(map(int, read().split()))
def gcd(a, b):
#     print(a,b)
    if a > b:
        a,b = b,a
    return a if b %a ==0 else gcd(b%a, a)
def cal(ac, x):
    if len(ac) == 0:
        ac.append(x)
        return ac
    nxt = gcd(ac[-1], x)
    ac.append(nxt)
    return ac
A1 = list(reduce(cal, A, []))
A.reverse()
A2 = list(reduce(cal, A, []))
A2.reverse()
mx = 1
for i in range(n):
    if i == 0:
        mx =max(A2[ 1 ], mx)
        continue
    elif i == n-1:
        mx = max(A1[ -2 ], mx)
        continue
    else: # i < n-1 && i > 0
        nxt = gcd(A1[i-1], A2[i+1])
        mx = max(nxt, mx)
print(mx)
# A.reverse()
# A1, A2, n, A

Submission status: Accepted

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

if n == 2:
    print(max(a[0], a[1]))
    exit()

noskip = gcd(a[0], a[1])
skipped = max(gcd(a[0], a[2]), gcd(a[1], a[2]))

for i in range(2, n):
    skipped = max(gcd(skipped, a[i]), noskip)
    noskip = gcd(noskip, a[i])

print(max(noskip, skipped))

Submission status: Accepted

Solution code:
import math

words = lambda t : list(map(t, input().split()))


def gcd (a,b):
    if a > b:
        t = b
        b = a
        b = t
    v = b
    while (a % b != 0):
        t = a % b
        a = b
        b = t
        v = b
    return v


n = int(input())
a = words(int)

if n == 2:
    print(max(a[0],a[1]))

else:
    cgcdm1 = max(gcd(a[0],a[1]),gcd(a[1],a[2]),gcd(a[2],a[0]))
    allgcd = gcd(a[0],gcd(a[1],a[2]))

    for i in range(3,len(a)):
        cgcdm1 = max(gcd(cgcdm1,a[i]),allgcd)
        allgcd = gcd(allgcd, a[i])

    print(cgcdm1)


def gcd (a,b):
    if a > b:
        t = b
        b = a
        b = t
    v = b
    while (a % b != 0):
        t = a % b
        a = b
        b = t
        v = b
    return v

Submission status: Accepted

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

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

b = [a[0]]
c = [a[-1]]

for i in range(1,n):
     j = n-1-i
     b.append(gcd(b[-1],a[i]))
     c.append(gcd(c[-1],a[j]))
     
ans = max(b[-2],c[-2])
for i in range(n):
     ans = max(ans,gcd(b[i],c[n-3-i]))
print(ans)

Submission status: Accepted

Solution code:
def GCD(x,y):
    if x==0:
        return y 
    elif y==0:
        return x
    elif x>y:
        return GCD_ordered(x,y)
    else:
        return GCD_ordered(y,x)

def GCD_ordered(x,y):
    z=x%y
    if z!=0:
        return GCD_ordered(y,z)
    if z ==0:
        return y




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

tmp_forward=A[0]
tmp_backward=A[-1]
gcd_forward=[0,tmp_forward]
gcd_backward=[0,tmp_backward]

for i in range(1,N):
    tmp_forward = GCD(tmp_forward,A[i])
    gcd_forward.append(tmp_forward)
    
    tmp_backward = GCD(tmp_backward,A[-i-1])
    gcd_backward.append(tmp_backward)
#     print("forward",tmp_forward)
#     print("backward",tmp_backward)

# print("forward",gcd_forward)
# print("backward",gcd_backward)

ans=0

for i in range(0,N):
    tmp_gcd = GCD(gcd_forward[i],gcd_backward[(N-1)-i])
#     print(tmp_gcd)
    if ans < tmp_gcd:
        ans = tmp_gcd
      
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
a = list(map(int, input().split()))
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0+1)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        if data[2*k+1] == INF:
            data[k] = data[2*k+2]
        elif data[2*k+2] == INF:
            data[k] = data[2*k+1]
        else:
            data[k] = gcd(data[2*k+1], data[2*k+2])

for i in range(N):
    update(i, a[i])

ans = 0
for i in range(N):
    update(i, INF)
    ans = max(ans, data[0])
    update(i, a[i])

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int, input().split()))
from fractions import gcd
gcd_all=gcd(a[0],a[1])
gcd_eli=[a[0],a[1]]
for i in range(2,n):
    temp0=gcd(gcd_eli[0],a[i])
    temp1=gcd(gcd_eli[1],a[i])
    gcd_eli=sorted([temp0,temp1,gcd_all])[1:]
    gcd_all=gcd(gcd_all,a[i])
print(max(gcd_all,max(gcd_eli)))

Submission status: Accepted

Solution code:
import fractions
# fraction
from functools import reduce


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


def main():
    result = sub()
    print(result)


def sub():
    N = int(input())
    As = [int(i) for i in input().split()]

    lh_gcds = [0] * N
    for i in range(N):
        if i == 0:
            lh_gcds[i] = As[i]
        else:
            lh_gcds[i] = fractions.gcd(lh_gcds[i-1], As[i])

    rh_gcds = [0] * N
    for i in range(N-1, -1, -1):
        if i == N-1:
            rh_gcds[i] = As[i]
        else:
            rh_gcds[i] = fractions.gcd(rh_gcds[i+1], As[i])

    max_gcd = 1
    for i in range(N):
        if i == 0:
            max_gcd = max(max_gcd, rh_gcds[1])
        if i == N-1:
            max_gcd = max(max_gcd, lh_gcds[-2])
        else:
            max_gcd = max(max_gcd, fractions.gcd(lh_gcds[i-1], rh_gcds[i+1]))
    return max_gcd


if __name__ == '__main__':
    main()

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

#スペース入力
n = int(input())
a = input().split()

A = [int(element) for element in a]

A.sort()

a_min = A[0]
a_min2 = A[1]


a_min_divs = make_divisors(a_min)
a_min2_divs = make_divisors(a_min2)

a_min_divs.remove(1)
a_min2_divs.remove(1)

max_div = 1

results = [1]


for diver in a_min_divs:
    thr = 0
    for num in A:
        # print(num)
        # print(diver)
        # print(num % diver)
        if num % diver != 0:
            thr = thr+1
            if thr > 1:

                break
            else:
                continue
    if thr < 2:
        results.append(diver)

for diver in a_min2_divs:
    thr = 0
    for num in A:
        # print(num)
        # print(diver)
        # print(num % diver)
        if num % diver != 0:
            thr = thr+1
            if thr > 1:

                break
            else:
                continue
    if thr < 2:
        results.append(diver)



print(max(results))

Submission status: Accepted

Solution code:

def main():
    N = int(input())
    A = [int(n) for n in input().split()]
    fore = [0]*N
    back=[0]*N
    fore[0] = A[0]
    back[-1] = A[-1]
    for i in range(1, N):
        fore[i] = gcd(fore[i-1], A[i])
    for i in reversed(list(range(0, N-1))):
        back[i] = gcd(back[i+1], A[i])
    maximum = 0
    for i in range(N):
        f = fore[i-1] if i != 0 else 0
        b = back[i+1] if i != N-1 else 0
        m = gcd(f, b)
        maximum = max(m, maximum)
    print(maximum)
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
main()