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

Обсуждение задачи 1860. Фибориалы

No subject
Послано takiemtam 24 сен 2011 13:22
F[3]=6 ????
Re: No subject
Послано vk 24 сен 2011 13:25
I think so.
My question is similar
Re: No subject
Послано tryit1 24 сен 2011 17:17
How to solve this, i get TLE ? I have the prime factors in 3 maps

while(i<=n){
      M3=M1;
      M3+=M2;
      M3+=factorization(i);
      M1=M2,M2=M3,M3.clear();
i++;
}
Re: No subject
Послано morbidel 26 сен 2011 16:52
F[3] is 6 so it has 4 divisors (1, 2, 3, 6). So answer for N=3 is 4.
Re: No subject
Послано svr 10 окт 2011 15:46
I think that precompaled (mod 100000007) fibbonachi numbers 1 1 2 3 5 7 .. may help
Re: No subject
Послано luckysundog 11 окт 2011 18:00
10^6 fibonacci numbers?
Re: No subject
Послано svr 11 окт 2011 18:05
Yes! All Ok, this methods gaves easy AC
Re: No subject
Послано luckysundog 11 окт 2011 19:26
0.171s without precompiled arrays.
Precompiled fibonacci array doesn't really help because total algorithm complexity is not linear.
Re: No subject
Послано luckysundog 11 окт 2011 19:33
But i use *precalculated* Fibonacci array. And also Eratosthenes Sieve.
Re: No subject
Послано svr 11 окт 2011 21:02
My algo without Sieve.
If i=p^k*Q then in F[n] it comes as p^(k*Fib[n-i]) and this moment I need Fib[n-i] precalculed.

Edited by author 11.10.2011 21:03
Re: No subject
Послано luckysundog 13 окт 2011 04:46
Yeah, it's right. But:
> i=p^k*Q
 - then you need list of all primes <= 10^6, right? This list is very large, so i used sieve.

p.s. Does the fibonacci sequence (mod 10^9+7) get periodic?

Edited by author 13.10.2011 04:51