ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1133. Последовательность Фибоначчи

This problem has fine precalc solution
Послано Cat36 15 май 2009 18:43
)
Re: This problem has fine precalc solution
Послано chonglinsun 10 июл 2009 11:54
esaselp em llet
Re: This problem has fine precalc solution
Послано chonglinsun 10 июл 2009 11:54
tell me please
Re: This problem has fine precalc solution
Послано Cat36 13 июл 2009 11:08
sorry, bad english
This sequence can be calculated as k1*((1+sqrt(5))/2)^n +k2*((1-sqrt(5))/2)^n
By precalculation we can find such prime p, what:
 1. p>4000000000;
 2. exist such n, what n*n==5 (mod p)
So, this sequence by modulo p can be calculated us k1*a^n + k2*b^n, where a,b,k1,k2 - integer

It's all

Edited by author 13.07.2009 11:09
sqrt(5) = 2162366358 mod 4000000019
Послано ASK 4 ноя 2010 23:35
Note that if you go this road, you are better using Java, since you will need modPow and modInverse.
Re: This problem has fine precalc solution
Послано Artem Khizha [DNU] 16 янв 2011 16:40
What about its complexity?