Задача на числа Фибонначи

Revision ru2, by amazing-hash, 2016-03-19 21:26:12

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

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian amazing-hash 2016-03-19 21:27:57 24 Мелкая правка: 'Фибоначчи и потом п' -> 'Фибоначчи по модулю 10^6 например и потом п'
ru2 Russian amazing-hash 2016-03-19 21:26:12 0 (опубликовано)
ru1 Russian amazing-hash 2016-03-19 21:23:55 558 Первая редакция (сохранено в черновиках)