F[3]=6 ????

I think so.
My question is similar

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++;
}

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

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

10^6 fibonacci numbers?

Yes! All Ok, this methods gaves easy AC

0.171s without precompiled arrays.
Precompiled fibonacci array doesn't really help because total algorithm complexity is not linear.

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

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

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