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:
import sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

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


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        if a >= b:
            return self.I
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

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


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(self.sz - 1)):
            self.seg[i + 1] = self.func(self.seg[2 * i + 2], self.seg[2 * i + 3])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

Solution code:
# test
import sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

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


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[i * 2], self.seg[i * 2 + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[k * 2], self.seg[k * 2 + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz * 2
        else:
            b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

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


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[i + i], self.seg[i + i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[k + k], self.seg[k + k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz + self.sz
        else:
            b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

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


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz + self.sz
        else:
            b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

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


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b = self.sz * 2 if b == self.N else self.sz + b
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in reversed(range(1,self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = list(map(int,readline().split()))
    seg = SegmentTree(N , gcd , 0)
    for i,n in enumerate(L):
        seg.assign(i , n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Accepted

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

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

n=int(input())
A=list(sorted(map(int,input().split())))
D0=list(reversed(make_divisors(A[0])))
D1=list(reversed(make_divisors(A[1])))

ans=1
for d in D0:
    if d==1:
        continue
    cnt=0
    for a in A:
        if a%d!=0:
            cnt+=1
        if cnt>1:
            break
    if cnt<=1:
        ans=max(d,ans)
        break

for d in D1:
    if d==1:
        continue
    cnt=0
    for a in A:
        if a%d!=0:
            cnt+=1
        if cnt>1:
            break
    if cnt<=1:
        ans=max(d,ans)
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

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

def main():
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in reversed(range(1,self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    m = map(int,readline().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in reversed(range(1,self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = list(map(int,readline().split()))
    seg = SegmentTree(N , gcd , 0)
    for i,n in enumerate(L):
        seg.assign(i , n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in reversed(range(1,self.sz)):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = list(map(int,read().split()))
    seg = SegmentTree(N , gcd , 0)
    for i,n in enumerate(L):
        seg.assign(i , n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = list(map(int,read().split()))
    seg = SegmentTree(N , gcd , 0)
    for i,n in enumerate(L):
        seg.assign(i , n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

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

def main():
    N = int(readline())
    L = list(map(int,read().split()))
    seg = SegmentTree(N , gcd , 0)
    for i,n in enumerate(L):
        seg.assign(i , n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

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

def main():
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = copy.deepcopy(I)
        self.seg = [copy.deepcopy(I) for i in range(self.sz * 2)]

    def assign(self, k, x):
        self.seg[k + self.sz] = copy.deepcopy(x)

    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = copy.deepcopy(x)
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = copy.deepcopy(self.I)
        R = copy.deepcopy(self.I)
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    N = int(readline())
    m = map(int, read().split())
    seg = SegmentTree(N, gcd, 0)
    for i in range(N):
        seg.assign(i, next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from fractions import gcd

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = copy.deepcopy(I)
        self.seg = [copy.deepcopy(I) for i in range(N * 2)]

    def assign(self, k, x):
        self.seg[k + self.sz] = copy.deepcopy(x)

    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = copy.deepcopy(x)
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = copy.deepcopy(self.I)
        R = copy.deepcopy(self.I)
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    N = int(readline())
    m = map(int, read().split())
    seg = SegmentTree(N, gcd, 0)
    for i in range(N):
        seg.assign(i, next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, N)))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from fractions import gcd

class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I] * (N * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()