## Search found 5 matches

Sun Oct 05, 2003 2:47 pm
Forum: Volume 102 (10200-10299)
Topic: 10229 - Modular Fibonacci
Replies: 53
Views: 17267
No the algorithm i used, each time divides n by 2 so is clearly log2(n)...

But i didt got the idea u used in the problem... do u process anything before and use it?
Sun Oct 05, 2003 12:10 am
Forum: Volume 102 (10200-10299)
Topic: 10229 - Modular Fibonacci
Replies: 53
Views: 17267
i've found an algorithm that runs in O(log(n)) and i've got an AC for anyone who is curious go to
http://www.ics.uci.edu/~dan/class/161/notes/7/Fib.html

it ran in 0.02 s
Sat Oct 04, 2003 11:27 pm
Forum: Volume 102 (10200-10299)
Topic: 10229 - Modular Fibonacci
Replies: 53
Views: 17267
Look don't say that is obviously going to be TLE, my algorithm runs at O(n), as the maximum input is 2^31 -1 so the max running time is: T = (2^31-1) /(10^9) ~ 2 so its 2 seconds aproximately. Talking about algorithms i only know calculating fibonacci with the obscure formula Fn = 1/sqrt(5)*[ 1/2*(1...
Sat Oct 04, 2003 6:02 pm
Forum: Volume 102 (10200-10299)
Topic: 10229 - Modular Fibonacci
Replies: 53
Views: 17267
Well i tryed also do make this one but i've got a time limit exceeded, i tried the biggest case (2^31 - 1) and in my computer runned in 2s, what's the problem??? Maybe this is more clear than the above... [cpp] #include <stdio.h> unsigned int m, n; unsigned const int mascara[20] = {0, 1, 3, 7, 15, 3...
Sat Oct 04, 2003 6:00 pm
Forum: Volume 102 (10200-10299)
Topic: 10229 - Modular Fibonacci
Replies: 53
Views: 17267
Well i tryed also do make this one but i've got a time limit exceeded, i tried the biggest case (2^31 - 1) and in my computer runned in 2s, what's the problem??? #include <stdio.h> unsigned int m, n; unsigned const int mascara[20] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 163...