UVa 10229

From Algorithmist
Jump to navigation Jump to search


10229 - Modular Fibonacci[edit]

Summary[edit]

Get the F(n) Fibonacci's Number then get its modulo on .

Explanation[edit]

Solving this problem requires you to calculate Fibonacci in lg(n) time. It's by dividing n into n/2 size problem at each instance.

Gotchas[edit]

  • Use a 64 bit integer representation for the Fibonacci's number as a 32 bit will overflow.
  • Use the Q-Fibonacci Matrix to get the output in O(log n) and avoid TLE.

Implementations[edit]

Input[edit]

11 7
11 6

Output[edit]

89
25

Code[edit]

http://snipt.org/kgogl