Discussion @ 1860. Fiborial @ Timus Online Judge

No subject takiemtam 24 Sep 2011 13:22

F[3]=6 ????

Re: No subject vk 24 Sep 2011 13:25

I think so.
My question is similar

Re: No subject tryit1 24 Sep 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 svr 10 Oct 2011 15:46

I think that precompaled (mod 100000007) fibbonachi numbers 1 1 2 3 5 7 .. may help

Re: No subject luckysundog 11 Oct 2011 18:00

10^6 fibonacci numbers?

Re: No subject svr 11 Oct 2011 18:05

Yes! All Ok, this methods gaves easy AC

Re: No subject luckysundog 11 Oct 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 Oct 2011 19:33

But i use *precalculated* Fibonacci array. And also Eratosthenes Sieve.

Re: No subject svr 11 Oct 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 Oct 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

Re: No subject morbidel 26 Sep 2011 16:52

F[3] is 6 so it has 4 divisors (1, 2, 3, 6). So answer for N=3 is 4.

Discussion of Problem 1860. Fiborial