Как посчитать n-ную сумму ряда?

Question

[Jordan_Fride]

Задача на алгоритмы.
Условие: Посчитайте

Входные данные: x, d, q, n.
Ограничения:


Простым суммированием выдает Таймлимит. Подскажите, как быть

Answer 1

[galaxy]

Можно посчитать аналитически. Формулу выводить целиком не буду (ее даже записать будет геморрой тут), но идея такая:
исходный общий член ряда a_i = x*qⁱ + i*d*qⁱ
первая часть - обычная геометрическая прогрессия, вторая интереснее, с точностью до константы: i*qⁱ
Чтобы найти сумму такого ряда, можно записать ее так:
q
+
q² + q²
+
q³ + q³ + q³
+
...
+
qⁿ + ... + qⁿ

и просуммировать не по строкам, а по столбцам. Каждый столбец - геометрическая прогрессия с суммой (qⁿ⁺¹ - q^k)/(q - 1)
Это дело надо просуммировать по k - тут константа + общий член геометрической прогрессии, все просто. Ответ: (n*qⁿ⁺¹ - (qⁿ⁺¹ - q)/(q-1)) / (q-1)

Потом соберите все воедино с константами в одну формулу.

Comments

[Jordan_Fride]

Я просто восхищаюсь. Как научиться мыслить так широко?! Большое спасибо, добрый человек

[xmoonlight]

Jordan_Fride, главное теперь, чтобы таймлимит также не выдавало!))