Problem p03061 (python)

Fixed submission:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
A = read_ints()

from fractions import gcd
# 累積GCDを使って解く
# 累積の概念は広く使えるxor,min,max,積等...
# 差ではなく左右から挟み込んで演算という概念をしっかりと身につけよう

left = []
right = []
tmp_fo = 0
tmp_re = 0
for fo, re in zip(A, A[::-1]):
    tmp_fo = gcd(tmp_fo, fo)
    tmp_re = gcd(tmp_re, re)
    left.append(tmp_fo)
    right.append(tmp_re)

right = right[::-1]

ans = 0
for i in range(1, N-1):
    ans = max(ans, gcd(left[i - 1], right[i + 1]))

ans = max(ans, right[1], left[-2])

print(ans)

Buggy submission (verdict: Runtime Error):
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


import numpy as np

N = read_a_int()
A = np.array(read_ints())


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

    return a


import math


def is_prime(n):
    if n == 1:
        return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


gcd_tmp = A[0]
for a in A[1:]:
    gcd_tmp = gcd(gcd_tmp, a)

A_gcd = A//gcd_tmp

# delidx = None
for i, a in enumerate(A_gcd):
    if is_prime(a):
        delidx = i
        break


ans = A[delidx-1]
for i, a in enumerate(A[:delidx].tolist()+A[delidx+1:].tolist()):
    ans = gcd(ans, a)

print(ans)

Buggy submission (verdict: Runtime Error):
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


import numpy as np

N = read_a_int()
A = np.array(read_ints())


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

    return a


import math


def is_prime(n):
    if n == 1:
        return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


gcd_tmp = A[0]
for a in A[1:]:
    gcd_tmp = gcd(gcd_tmp, a)

A_gcd = A//gcd_tmp

# delidx = None
for i, a in enumerate(A_gcd):
    if is_prime(a):
        delidx = i
        break


ans = A[delidx-1]
for i, a in enumerate(A):
    if i == delidx:
        continue
    ans = gcd(ans, a)

print(ans)