This question has already been answered:

There is such a task:

Given integers 1 ≤ n ≤ 10 18 and 2 ≤ m ≤ 10 5 , it is necessary to find the remainder after dividing the n-th Fibonacci number by m.

My decision:

def fib_mod(n, m): # put your code here if n == 0: return 0 number_before = 0 number_current = 1 for i in range(n - 1): temp = number_current number_current += number_before number_current %= m number_before = temp return number_current def main(): n, m = map(int, input().split()) print(fib_mod(n, m)) if __name__ == "__main__": main()

The solution seems to be correct, but this algorithm does not pass time testing. I can not understand how else it can be accelerated ...

Reported as a duplicate by pavel , ߊߚߤߘ , jfs python 12 Feb '17 at 21:34 .

A similar question was asked earlier and an answer has already been received. If the answers provided are not exhaustive, please ask a new question .

  • Well, as you understand, up to 10 ^ 18 you should not be counted ... But - I hint: the remnants cannot but be periodic. Try to find a period, and then - everything is simple, right? - Harry
  • @Harry is not sure that it will become much easier, the period can be up to 10 ^ 10, - pavel
  • @pavel For m <= 10,000, the maximum period is 37499. And, there 10 ^ 5 - well, here 374999 ... - Harry
  • @Harry I wrote code for the sake of interest to find this maximum value, but it takes too long to execute. 375,000 found - pavel
  • 2
    Possible duplicate question: How to calculate a huge Fibonacci number modulo? this is an illustration of the comment @Harry - pavel

1 answer 1

The short answer is the wrong idea. This task is clearly from the PD category. The correct solution will work for O(log N) operations. How to achieve this: consider the initial Fibonacci numbers {1,1}. (Or {0,1} I didn’t go much into the condition).

For the next one, multiply this by {{0,1}, {1,1}} Then we get a pair {1,2} and so on. Multiply again - it will be {2,3}.

Thus, F[i,i+1] = {1,1} * ({{0,1},{1,1}} ) ^ i But then we use fast exponentiation (carefully with the number of characters, do not forget use the module).