|
|
вернуться в форум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++;
}
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 F[3] is 6 so it has 4 divisors (1, 2, 3, 6). So answer for N=3 is 4. |
|
|
