Ускорьте программу

Question

count = int(input())
for i in range(1, count + 1):
    a = j = i
    while a < count:
        j += 1
        a += j
    if a == count:
        print(i)
        break

Ищется наименьшее i, для введённого числа равному count.
i - это число, при котором последовательность i + (i + 1) + (i + 2) + ... (i + n) = count
При числе 1000001324409 (ответ: 57), тестировочная прога выдаёт:

Превышен лимит времени

По факту прошу придумать новое более быстрое решение.
Спасибо!

Answer 1

По формуле суммы арифметической прогрессии

sum { j in i to n } of j = (i + i+n) / 2 * (n+1) = i + n*(n+1) / 2

Отсюда уравнение:

i + n*(n+1) / 2 = count
n**2 + n - 2*(count-i) = 0
D = 1 + 8*(count-i)

Если дискриминант является полным квадратом, то последовательность, начинающаяся с i существует.

Так что просто перебираем i по возрастанию и проверяем, является ли полным квадратом 1 + 8*(count-i). Получится линейная асимптотика вместо квадратичной в вопросе.

Answer 2

    S1 = int(input())
    S2 = 1
    An1 = 2
    An2 = 1
    while S2 < S1:
        S2 += An1
        An1 += 1
    while S2 != S1:
        S2 -= An2
        if S2 < S1:
            S2 += An1
            An1 += 1
        An2 += 1
    print(An2)

Выше вы видите код, как мне кажется, более простого решения для Python.
А ниже разбор алгоритма:

Задаём сумму первых членов прогрессии;
Находим минимальную сумму арифметической прогрессии, начинающуюся на 1 и большую заданной суммы арифметической прогрессии;
По очереди вычитаем из неё все члены, начиная с единицы, и, когда она меньше заданной суммы, прибавляем следующие члены, пока сумма нашей прогрессии не будет равна заданной;
Выводим ответ!

БЛОГ НА HUSL

Ускорьте программу

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