Задача источник: Даны целые числа 1≤n≤10^18 и 2≤m≤10^5, необходимо найти остаток от деления n-го числа Фибоначчи на m.

Так как 5 последних цифр в числах последовательности Фибоначчи повторяются с периодичностью 150000 членов. То достаточно просчитать 300000 чисел Фибоначчи по модулю 10^6 например и потом получать ответ sequence[n % 150000 + 150000] % m. Я вообще правильно рассуждаю? Что-то мне подсказывает что я не прав.

Подскажите идею, как реализовать функцию прибавления на интервале в "Дереве отрезков", без рекурсивной реализации? Например для суммы. То есть после модификации отвечать на сумму на интервале.

Как решать эту задачу? http://codeforces.com/gym/100267/problem/B