помогите решить задачу на питоне

Question

Вот условие: Забавная игра Вы с друзьями играете в следующую игру. Друзья пишут на доске подряд N натуральных чисел. Ваша задача — найти как можно больше подряд идущих чисел, которые бы делились на одно и то же число, большее 1. Так как вручную искать ответ сложно, вы решили написать программу, которая сделает работу за вас.

Входные данные

В первой строке входного файла задано число N(1 ≤ N ≤ 100000). Во второй строке записано через пробел N целых чисел A1...AN(1 ≤ Ai ≤ 1000, 1 ≤ i ≤ N). Это те самые числа, которые написали ваши друзья. Они даны в том же порядке, в котором они расположены на доске.

Выходные данные

Ваша программа должна вывести в выходной файл одно целое число — наибольшее количество подряд идущих чисел заданной последовательности, которые бы делились на одно и то же натуральное число, большее 1.

Вот мое решение, однако оно не проходит по времени:

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


input()
a = [int(i) for i in input().split()]
mx = 0
for i in range(len(a)):
    cur_g = a[i]
    p = 0
    if len(a) - i < mx:
        break
    for j in range(i, len(a)):
        p += 1
        cur_g = gcd(cur_g, a[j])
        if cur_g == 1:
            break
        if mx < p:
            mx = p
print(mx)

Также была идея решить с помощью динамического программирования, но там тоже TL

Answer 1

Как минимум

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

Кроме того, не вычичслять постоянно len(a), а сделать вначале один раз,

len_a=len(a)

а затем использовать эту переменную.

Кроме того, вызов рекурсивной реализации функции gcd внутри циклв тоже может существенно ухудшить время выполнения.

Answer 2

import random, time

def examp1(a):
    """оригинальный"""
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)

    mx = 0
    for i in range(len(a)):
        cur_g = a[i]
        p = 0
        if len(a) - i < mx:
            break
        for j in range(i, len(a)):
            p += 1
            cur_g = gcd(cur_g, a[j])
            if cur_g == 1:
                break
            if mx < p:
                mx = p
    return mx

def examp2(a):
    """оптимизировано"""
    def gcd(a, b):
        return gcd(b, a % b) if b else a

    la = len(a)
    mx = 0
    for i, cur_g in enumerate(a):
        if la - i < mx:
            break
        p = 0
        for j in range(i, la):
            cur_g = gcd(cur_g, a[j])
            if cur_g == 1:
                break
            p += 1
            if mx < p:
                mx = p
    return mx


def time_(fn, a, x=25):
    """замерять время"""
    tt = []
    for _ in range(x):
        t = time.monotonic()
        fn(a)
        t = time.monotonic() - t
        tt.append(t)
    return sum(tt) / x

if __name__ == '__main__':
    N = 100000
    a = [random.randint(1, 1000) for _ in range(N)]
    t1 = time_(examp1, a)
    t2 = time_(examp2, a)
    print(f'examp1={t1:.2} сек, examp2={t2:.2} сек, выигрыш={(t1/t2)-1:.2%}')

out:

examp1=0.46 сек, examp2=0.37 сек, выигрыш=22.97%

БЛОГ НА HUSL

помогите решить задачу на питоне

Ответы (2 шт):