Problem:


Score : 300 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, written on the blackboard.

You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.

Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Sample Input 1

3
7 6 8

Sample Output 1

2

If we replace 7 with 4, the greatest common divisor of the three integers on the blackboard will be 2, which is the maximum possible value.

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Wrong Answer

Solution code:
def gcdf(a,n,a0):
#    a.sort()
#    a0=a[0]
    a0=min(a)
    a=[int(x%a0) for x in a if x%a0 != 0]
    if len(a)==0:
        return a0
    else:
#        a0=min(a)
        return gcdf(a,n,a0) 

n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)

if n==2:
    print(max(a))
else:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        a0=acpy[0]
        gcdx=gcdf(acpy,n-1,a0)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)

Submission status: Wrong Answer

Solution code:
def gcdf(a,n,a0):
    a.sort()
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
    if len(a)==0:
        return a0
    else:
        a0=min(a)
        return gcdf(a,n,a0) 

n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)

if n==2:
    print(max(a))
else:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        a0=acpy[0]
        gcdx=gcdf(acpy,n-1,a0)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)

Submission status: Wrong Answer

Solution code:
def gcdf(a,n,a0):
#    a.sort()
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
    if len(a)==0:
        return a0
    else:
        a0=min(a)
        return gcdf(a,n,a0) 

n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)

if n==2:
    print(max(a))
else:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        a0=acpy[0]
        gcdx=gcdf(acpy,n-1,a0)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)

Submission status: Wrong Answer

Solution code:
def gcdf(a,n,a0):
    a.sort()
#    print("a1:",a)
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a0=min(a)
#        print("a0",a0)
        return gcdf(a,n,a0) 

#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 81]
n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)

#print(a)
if n==2:
    print(max(a))
else:
    gcdv=0
#    a.sort()
    for i in range(n):
#        print("--------")
        acpy=list(a)
        del acpy[i]
        a0=acpy[0]
        gcdx=gcdf(acpy,n-1,a0)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)

Submission status: Wrong Answer

Solution code:
def gcdf(a,n,a0):
#    print("a1:",a)
    a0=a[0]
    a=[x%a0 for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a.sort()
        a0=min(a)
#        print("a0",a0)
        return gcdf(a,n,a0) 

#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 48]
n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)

#print(a)
if n==2:
    print(max(a))
else:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        a0=acpy[0]
        gcdx=gcdf(acpy,n-1,a0)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import fractions

N=int(input())

l=[list(map(int,input().split()))]

while len(l[-1])!=1:
    temp=[]
    for i in range(len(l[-1])//2):
        temp.append(fractions.gcd(l[-1][2*i],l[-1][2*i+1]))
    if len(l[-1])%2==1:
        temp.append(l[-1][-1])
    l.append(temp)

print(l)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    A = Scanner.map_int()
    L = [0] * N
    R = [0] * N
    for i in range(N-1):
        L[i+1] = Math.gcd(L[i], A[i])
    for i in reversed(range(N-1)):
        R[i] = Math.gcd(R[i+1], A[i+1])
    ans = 0
    for i in range(N-1):
        ans = max(ans, Math.gcd(L[i], R[i]))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def gcdf(a,n):
#    print("a:",a)
    a0=a[0]
    ramin=10**9
    ramin0=20**9
    while ramin0!=ramin:
        ramin0=ramin
        for i in range(n):
            a[i]=a[i]%a0
            if a[i]==0:
                a[i]=a0
#            ra=a[i]%a0
#            print(i,a[i],a0,ramin)
            if ramin>a[i] and a[i]!=0:
                ramin=a[i]
        a0=min(a)
#        print("a:",a,ramin)
    return ramin


#n=2
#a=[1000000000, 1000000000]
#n=4
#a=[15, 18, 24, 36]
n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)

#print(a)
if n==2:
    print(max(a))
else:
    gcdv=0
    a.sort()
    for i in range(n):
#        acpy=list(a)
#        del acpy[i]
#        gcdx=gcdf(acpy,n-1)
        gcdx=gcdf(a,n-1)
#        gcdx=gcd(acpy)
#        gcdx=functools.reduce(gcd,acpy)
#        gcdx=functools.reduce(math.gcd,acpy)
        if gcdx>gcdv:
            gcdv=gcdx
        aa=a[0]
        del a[0]
        a.append(aa)
    print(gcdv)

Submission status: Wrong Answer

Solution code:
def gcdf(a,n):
    a0=a[0]
    ramin=10**9
    ramin0=20**9
    while ramin0!=ramin:
        ramin0=ramin
        for i in range(1,n):
            ra=a[i]%a0
#            print(ra,a0,i,ramin)
            if ramin>ra and ra!=0:
                ramin=ra
        a0=ramin
    return ramin


#n=2
#a=[1000000000, 1000000000]
n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)
#print(a)
if n==2:
    print(max(a))
else:
    gcd=0
    a.sort()
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy,n-1)
        if gcdx>gcd:
            gcd=gcdx
    print(gcd)

Submission status: Wrong Answer

Solution code:
def gcdf(a,n):
    a0=a[0]
    ramin=10**9
    ramin0=20**9
    while ramin0!=ramin:
        ramin0=ramin
        for i in range(1,n):
            ra=a[i]%a0
#            print(ra,a0,i,ramin)
            if ramin>ra and ra!=0:
                ramin=ra
        a0=ramin
    return ramin


#n=2
#a=[1000000000, 1000000000]
n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)
#print(a)

gcd=0
a.sort()
for i in range(n):
    acpy=list(a)
    del acpy[i]
    gcdx=gcdf(acpy,n-1)
    if gcdx>gcd:
        gcd=gcdx
print(gcd)
#for i in range(n):

Submission status: Wrong Answer

Solution code:
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd,numbers)
def gcd_list(numbers):
    return reduce(fractions.gcd,numbers)
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=[]
for i in range(n):
    ans.append(gcd(*(a[:i]+a[i+1:])))
#print(ans)
if len(set(ans))==1:
    print(ans[0])
else:
    ans=list(set(ans))
    ans.sort()
    print(ans[1])

Submission status: Wrong Answer

Solution code:
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
left = [0] * (n + 1)
right = [0] * (n + 1)
middle = [0] * (n + 1)

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

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

for i in range(n - 1):
    middle[i] = gcd(left[i], right[i + 1])

print(max(middle))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
max_gcd = 1
def gcd(a,b):
    if b == 0:
        return a
    else:
        return(gcd(b,a%b))

for i in range(n):
    if i == 0:
        b = a[1:n]
    elif i == n-1:
        b = a[:i]
    else:
        b = a[:i] + a[i+1:n]
#    print(b)
    for j in range(1,len(b)):
        b[j] = gcd(max(b[j],b[j-1]),min(b[j],b[j-1]))
    if len(b)>1:
        c = gcd(max(b[0],b[1]),min(b[0],b[1]))
    else:
        c = b[0]
    if max_gcd<c:
        max_gcd = c
print(max_gcd)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
L = [0]
R = [0]
import fractions
def GCD(a,b):
    if a*b != 0:
        return fractions.gcd(a,b)
    else:
        return max(a,b)
for i in range(N-1):
    x = A[i]
    y = A[-i-1]
    L.append(GCD(L[i],x))
    R.append(GCD(R[i],y))
ans = 0
for i in range(N):
    x = L[i]
    y = R[i-1]
    ans = max(GCD(x,y),ans)
print(ans)

Submission status: Wrong Answer

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

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

if n < 3:
  print(max(a))
else:
  ll, lr = [0]*n, [0]*n
  ll[0], lr[n-1] = a[0], a[n-1]
  for i in range(1,n):
    ll[i] = gcd(ll[i-1], a[i])
    lr[n-i-1] = gcd(lr[n-i], a[n-i-1])
  print(max(ll[n-1], lr[1], *[gcd(l,r) for l,r in zip(ll[:n-1], lr[2:])]))

Submission status: Wrong Answer

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

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

ll, lr = [0]*n, [0]*n
ll[0], lr[n-1] = a[0], a[n-1]
for i in range(1,n):
  ll[i] = gcd(ll[i-1], a[i])
  lr[n-i-1] = gcd(lr[n-i], a[n-i-1])

print(max(ll[n-1], lr[1], *[gcd(l,r) for l,r in zip(ll[:n-1], lr[2:])]))

Submission status: Wrong Answer

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

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

    if N == 2:
        print(gcd(A[0], A[1]))
        exit()

    A0, A1, A2 = A[:3]
    A_min_sq = int(math.sqrt(A2)) + 1
    
    gcd_ls = set()
    for i in range(A_min_sq, 0, -1):
        div = set()
        c = 0
        if A0 % i == 0:
            div.add(A0 // i)
            c += 1
        if A1 % i == 0:
            div.add(A1 // i)
            c += 1
        if A2 % i == 0:
            div.add(A2 // i)
            c += 1
        if c < 2:
            continue
        gcd_ls.add(i)

        for j in div:
            if A0 % j == 0 and (A1 % j == 0 or A2 % j == 0):
                gcd_ls.add(j)
            elif A1 % j == 0 and A2 % j == 0:
                gcd_ls.add(j)
    gcd_ls = sorted(gcd_ls, reverse=True)

    for i in gcd_ls:
        wa = False
        for j in A:
            if j % i != 0:
                if wa:
                    break
                wa = True
        else:
            print(i)
            exit()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    if N == 2:
        print(gcd(A[0], A[1]))
        exit()

    A0, A1, A2 = A[:3]
    A_min_sq = int(math.sqrt(A2)) + 1
    
    gcd_ls = set()
    for i in range(A_min_sq, 0, -1):
        div = set()
        c = 0
        if A0 % i == 0:
            div.add(A0 // i)
            c += 1
        if A1 % i == 0:
            div.add(A1 // i)
            c += 1
        if A2 % i == 0:
            div.add(A2 // i)
            c += 1
        if c < 2:
            continue
        gcd_ls.add(i)

        for j in div:
            if A0 % j == 0 and (A1 % j == 0 or A2 % j == 0):
                gcd_ls.add(j)
            elif A1 % j == 0 and A2 % j == 0:
                gcd_ls.add(j)
    gcd_ls = sorted(gcd_ls, reverse=True)
    print(gcd_ls)

    for i in gcd_ls:
        wa = False
        for j in A:
            if j % i != 0:
                if wa:
                    break
                wa = True
        else:
            print(i)
            exit()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    if N == 2:
        print(gcd(A[0], A[1]))
        exit()

    A0, A1, A2 = A[:3]
    A_min_sq = int(math.sqrt(A0)) + 1
    
    gcd_ls = set()
    for i in range(A_min_sq, 0, -1):
        div = set()
        c = 0
        if A0 % i == 0:
            div.add(A0 // i)
            c += 1
        if A1 % i == 0:
            div.add(A1 // i)
            c += 1
        if A2 % i == 0:
            div.add(A2 // i)
            c += 1
        if c < 2:
            continue
        gcd_ls.add(i)

        for j in div:
            if A0 % j == 0 and (A1 % j == 0 or A2 % j == 0):
                gcd_ls.add(j)
            elif A1 % j == 0 and A2 % j == 0:
                gcd_ls.add(j)
    gcd_ls = sorted(gcd_ls, reverse=True)

    for i in gcd_ls:
        wa = False
        for j in A:
            if j % i != 0:
                if wa:
                    break
                wa = True
        else:
            print(i)
            exit()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = sorted(map(int, input().split()), reverse=True)

    if N == 2:
        print(gcd(A[0], A[1]))
        exit()

    A0, A1, A2 = A[:3]
    A_max_sq = int(math.sqrt(A0)) + 1
    
    gcd_ls = set([1])
    for i in range(A_max_sq, 1, -1):
        div = set()
        if A0 % i == 0:
            div.add(A0 // i)
        if A1 % i == 0:
            div.add(A1 // i)
        if A2 % i == 0:
            div.add(A2 // i)
        if len(div) < 2:
            continue
        gcd_ls.add(i)

        for j in div:
            if A0 % j == 0 and (A1 % j == 0 or A2 % j == 0):
                gcd_ls.add(j)
            elif A1 % j == 0 and A2 % j == 0:
                gcd_ls.add(j)
    gcd_ls = sorted(gcd_ls, reverse=True)

    for i in gcd_ls:
        wa = False
        for j in A:
            if j % i != 0:
                if wa:
                    break
                wa = True
        else:
            print(i)
            exit()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from __future__ import print_function

import sys
input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


# import math
# import string
import fractions
# from fractions import Fraction
from fractions import gcd

# def lcm(n,m):
#     return int(n*m/gcd(n,m))

# import re
# import array
# import copy
# import functools
# import operator

# import collections
# import itertools
# import bisect
# import heapq

# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace

# from queue import PriorityQueue as pq

# def coprimize(p, q):
#     common = fractions.gcd(p, q)
#     return (p//common , q//common )
# # from itertools import accumulate
# # from collections import deque

# from operator import mul
from functools import reduce

# def combinations_count(n, r):
#     r = min(r, n - r)
#     numer = reduce(mul, range(n, n - r, -1), 1)
#     denom = reduce(mul, range(1, r + 1), 1)
#     return numer // denom

# import random


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


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

    a.append(a[-1])
    ans = 0
    for i in range(n):
        temp = a[i]
        a[i] = a[i + 1]
        ans = max(ans, gcd(a))
        a[i] = temp
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import random
import time

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

if N == 1:
    print(A[0])
elif N == 2:
    print(max(A))
else:
    d1 = gcd(A[0], A[1])
    for i in range(2, N):
        d1 = gcd(d1, A[i])

    xs = [x // d1 for x in A]
    _t = time.time()
    max_d = 0
    while time.time() - _t < 1.5:
        i = random.randint(0, N - 1)
        ys = xs[:i] + xs[i + 1:]
        d2 = gcd(ys[0], ys[1])
        for j in range(2, len(ys)):
            d2 = gcd(d2, ys[j])
        max_d = max(max_d, d2)
    print(d1 * max_d)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import random
import time

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

if N == 1:
    print(A[0])
elif N == 2:
    print(max(A))
else:
    d1 = gcd(A[0], A[1])
    for i in range(2, N):
        d1 = gcd(d1, A[i])

    xs = [x // d1 for x in A]
    _t = time.time()
    max_d = 0
    while time.time() - _t < 1.0:
        i = random.randint(0, N - 1)
        ys = xs[:i] + xs[i + 1:]
        d2 = gcd(ys[0], ys[1])
        for j in range(2, len(ys)):
            d2 = gcd(d2, ys[j])
        max_d = max(max_d, d2)
    print(d1 * max_d)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
def gcd(m, n):
  while n != 0:
    m, n = n, m % n
  return m
gl = [A[0]]
gr = [A[N-1]]
x, y = A[0], A[N-1]
for i in range(1, N):
  x = gcd(x, A[i])
  gl.append(x)
  y = gcd(y, A[N-i-1])
  gr.append(y)
gg = [gr[N-2]]
for i in range(1, N):
  gg.append(gcd(gl[i-1], gr[N-i-2]))
if N != 2:
  print(max(gg))
else:
  print(max(A[0], A[1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
def gcd(m, n):
  while n != 0:
    m, n = n, m % n
  return m
gl = [A[0]]
gr = [A[N-1]]
x, y = A[0], A[N-1]
for i in range(1, N):
  x = gcd(x, A[i])
  gl.append(x)
  y = gcd(y, A[N-i-1])
  gr.append(y)
gg = [gr[N-2]]
for i in range(1, N):
  gg.append(gcd(gl[i-1], gr[N-i-2]))
print(max(gg))

Submission status: Wrong Answer

Solution code:
import sys
import fractions
import math
import itertools

n=int(input())
a=list(map(int,input().split()))
list=[]
ans=0

for i in itertools.combinations(a,2):
	value=fractions.gcd(i[0],i[1])
	if ans<=value:
		ans=value

print(ans)

Submission status: Wrong Answer

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

stack=-1
t=[]
for i in a:
    if stack==i:
        t.append(i)
        stack=-1
    else:
        stack=i
    
    if len(t)>=2:
        break
try:
    print(t[0]*t[1])
except:
    print(0)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length-1] = ls[i]
  for i in range(length-2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if a<=l and r<=b:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(n):
  ans.append(gcd(query(0,i,0,0,length),query(i+1,n,0,0,length)))
print(ans)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length-1] = ls[i]
  for i in range(length-2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if l<=a and b<=r:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(n):
  ans.append(gcd(query(0,i,0,0,length),query(i+1,n,0,0,length)))
print(max(ans))

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length-1] = ls[i]
  for i in range(length-2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if l<=a and b<=r:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(1,n):
  ans.append(gcd(query(0,i,0,0,length),query(i,n,0,0,length)))
print(max(ans))

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length-1] = ls[i]
  for i in range(length//2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if l<=a and b<=r:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(n):
  update(i,0)
  ans.append(query(0,n,0,0,length))
  update(i,ls[i])
print(max(ans))

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length//2+1] = ls[i]
  for i in range(length//2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if l<=a and b<=r:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(n):
  update(i,0)
  ans.append(query(0,n,0,0,length))
  update(i,ls[i])
print(max(ans))

Submission status: Wrong Answer

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc145/tasks/abc145_e
# E - All-you-can-eat
"""
DP1[i][j] =the maximum sum of deliciousness of dishes, which are chosen from 1st- to i-th dishes,
such that he can finish them in j minutes

still WA!!!

"""


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    elif a % b:
        return gcd(b, a % b)
    else:
        return b


N = gi()
A = [0] * N

for i in range(N):
    A[i] = gi()

ans = A[1]

for i in range(2, N):
    ans = gcd(ans, A[i])

bf = 1
bi = -1
for i in range(1, N):
    f = A[i] // gcd(A[0], A[i])
    if f >= bf:
        bf = f
        bi = i

can = A[0]

for i in range(N):
    if i == bi:
        continue
    can = gcd(can, A[i])

print(max(ans, can))

Submission status: Wrong Answer

Solution code:
import os, sys, re, math, fractions

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

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

memo_L = [1] * N
memo_R = [1] * N

for i in range(N):
    if i == 0:
        memo_L[i] = A[i]
        memo_R[i] = A[N-1]
    elif i == N - 1:
        memo_L[i] = gcd(A[i], memo_L[i-1])
        memo_R[i] = gcd(A[0], memo_R[i-1])
    else:
        memo_L[i] = gcd(A[i], memo_L[i-1])
        memo_R[i] = gcd(A[N-1-i], memo_R[i-1])

memo_R.reverse()

ret = 1
for j in range(N):
    if j == 0:
        ret = max(ret, memo_R[1])
    elif j == N-1:
        ret = max(ret, memo_L[j-1])
    else:
        common_gcd = fractions.gcd(memo_L[j-1], memo_R[j+1])
        ret = max(ret, common_gcd)

print(ret)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
	divisors = []
	for i in range(1, int(n**0.5)+1):
		if n % i == 0:
			if i != 1:
				divisors.append(i)
			if i != n // i:
				divisors.append(n//i)
	return divisors
  
n = int(input())
a = [int(i) for i in input().split()]
lst = {}
for i in a:
	divisors = make_divisors(i)
	for j in divisors:
		if str(j) in lst:
			lst[str(j)] += 1
		else:
			lst[str(j)] = 1
            
for k in reversed(sorted([int(i) for i in lst.keys()])):
	if lst[str(k)] >= len(a) - 1:
		print(k)
		break

Submission status: Wrong Answer

Solution code:
import os, sys, re, math

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

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

gcds = set()
memo = []
for i in range(N):
    memo.append([0] * N)
for i in range(N - 1):
    for j in range(i + 1, N):
        if memo[i][j] == 0:
            g = gcd(A[i], A[j])
            gcds.add(g)
            memo[i][j] = g

gcds = sorted(gcds)
print(gcds[1] if len(gcds) >= 2 else gcds[0])

Submission status: Wrong Answer

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


N = int(input())
A = list(map(int, input().split()))
r = 0
b = -1

for i in range(N):
    a = gcd(r, A[i]) if r != 0 else A[i]
    if a < r:
        b = i
    r = a

r3 = 0
for i in range(N):
    if i == b - 1:
        continue
    r3 = gcd(r3, A[i]) if r3 != 0 else A[i]

r4 = 0
for i in range(N):
    if i == b:
        continue
    r4 = gcd(r4, A[i]) if r4 != 0 else A[i]

d = sorted([(gcd(A[i], A[i + 1]), i) for i in range(N - 1)])
t = d[0][1]
r1 = 0
for i in range(N):
    a = A[i-1] if i == t + 1 else A[i]
    if r1 == 0:
        r1 = a
    else:
        r1 = gcd(r1, a)
r2 = 0
for i in range(N):
    a = A[i+1] if i == t else A[i]
    if r2 == 0:
        r2 = a
    else:
        r2 = gcd(r2, a)
print(max(r, r2))

Submission status: Wrong Answer

Solution code:
# 一人消してgcd
n = int(input())
l = sorted(list(map(int, input().split(' '))))
def gcd(b, s):
  return s if b % s == 0 else gcd(s, b % s)

ggcd = {}
for e in range(0, len(l)):
  temp = l[0]
  for i in range(1, len(l)):
    temp = gcd(temp, l[i])
  ggcd[0, e] = temp
for s in range(len(l)):
  temp = l[-1]
  for i in range(s, len(l) - 1):
    temp = gcd(temp, l[i])
  ggcd[s, len(l) - 1] = temp
ans = max(ggcd[0, len(l)-2], ggcd[1, len(l)-1])
for i in range(1, len(l)-2):
  ans = max(ans, gcd(ggcd[(0, i)], ggcd[(i+1, len(l)-1)]))
#print(ggcd)
print(ans)

Submission status: Wrong Answer

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


N = int(input())
A = list(map(int, input().split()))
r = 0
b = -1

for i in range(N):
    a = gcd(r, A[i]) if r != 0 else A[i]
    if a < r:
        b = i
    r = a

r = 0
for i in range(N):
    if i == b:
        continue
    r = gcd(r, A[i]) if r != 0 else A[i]

r2 = 0
for i in range(N):
    if i == b - 1:
        continue
    r2 = gcd(r2, A[i]) if r2 != 0 else A[i]

r3 = 0
for i in range(N):
    if i == b + 1:
        continue
    r3 = gcd(r3, A[i]) if r3 != 0 else A[i]

print(max(r, r2, r3))

Submission status: Wrong Answer

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


N = int(input())
A = list(map(int, input().split()))
r = 0
b = -1

for i in range(N):
    a = gcd(r, A[i]) if r != 0 else A[i]
    if a < r:
        b = i
    r = a

r = 0
for i in range(N):
    if i == b:
        continue
    r = gcd(r, A[i]) if r != 0 else A[i]

r2 = 0
for i in range(N):
    if i == b - 1:
        continue
    r2 = gcd(r2, A[i]) if r2 != 0 else A[i]

print(max(r, r2))

Submission status: Wrong Answer

Solution code:
N = int(input())
As = [int(s) for s in input().split(' ')]
As.sort()
As = list(set(As))
A_max = max(As)

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

ret = 1
if len(As) == 1:
    ret = As[0]
elif len(As) == 2:
    # A1 A2
    ret = gcd(As[0], As[1])
elif len(As) == 3:
    # A1 A2 A3
    ret = max(gcd(As[0], As[1]), gcd(As[0], As[2]),gcd(As[1], As[2]))
else:
    # A1 A2 ... An-1 An
    ret = gcd(As[0], As[1])
    for a in As[2:]:
        new_ret = gcd(ret, a)
        if new_ret < ret:
            break
        ret = new_ret
print(ret)

Submission status: Wrong Answer

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


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

d = sorted([(gcd(A[i], A[i + 1]), i) for i in range(N - 1)])
t = d[0][1]
r1 = 0
for i in range(N):
    a = A[i-1] if i == t + 1 else A[i]
    if r1 == 0:
        r1 = a
    else:
        r1 = gcd(r1, a)
r2 = 0
for i in range(N):
    a = A[i+1] if i == t else A[i]
    if r2 == 0:
        r2 = a
    else:
        r2 = gcd(r2, a)

print(max(r1, r2))