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

Правка ru1, от amazing-hash, 2016-03-19 21:23:55

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

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

История

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