Если t^a ≠ 1 (mod p) (где p — модуль), то можно быстрым возведением в степень посчитать числитель и знаменатель дроби, им же найти обратный к знаменателю (пользуясь теоремой Ферма/Эйлера: a^p - 2·a = 1 (mod p) и перемножить.

То, что выше описал Егор, не будет работать, если t не взаимно просто с p. Однако можно решить эту задачу и в таком случае, не пользуясь никакими делениями. Если не ошибаюсь, это была задача на одном из первых раундов последних SNWS.

.

Заметим, что если k чётно, то . Иначе можно посчитать просто: f(k) = t^a·f(k - 1) + 1. За логарифмическое число шагов таким образом мы вычислим требуемую сумму.

В текущей версии решение работает за O(log²k) (на каждом шаге может понадобиться вызывать быстрое возведение в степень). Но можно аккуратно написать и просто пересчитывать выражение в скобках mdash; тогда сложность выйдет вообще O(logk).