Fibonacci modulo m
Fibonacci numbers: F₀ = 0, F₁ = 1, Fn = Fn−1 + Fn−2. Find the remainder of Fn divided by m, for n up to 10¹⁸, when the Fibonacci number itself has more than two hundred quadrillion digits.
Input
The first line holds the number of queries q (1 ≤ q ≤ 10,000). Each of the following lines holds n and m (0 ≤ n ≤ 10¹⁸, 1 ≤ m ≤ 10⁹).
Output
For each query, Fn mod m on a separate line.
Examples
Example 1
6 0 10 1 10 2 10 10 1000 50 1000000007 90 1000000000
0 1 1 55 586268941 370816120
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 4 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A step of the recurrence takes the pair (Fn, Fn−1) to the pair (Fn+1, Fn), and does it linearly. How can a linear transformation of a pair of numbers be written?
2The idea
As a matrix: (Fn+1, Fn) = [[1, 1], [1, 0]] · (Fn, Fn−1). So n steps are the n-th power of the matrix, and the power is computed by fast exponentiation in log₂ n matrix multiplications. The result is [[1, 1], [1, 0]]n = [[Fn+1, Fn], [Fn, Fn−1]].
3Walkthrough
The same loop as for numbers, only the multiplication is a 2×2 matrix one, and the remainder is taken of every element. The initial “answer” is the identity matrix. With m = 1 all the remainders are zeros, so the identity matrix is carefully written as (1 mod m): otherwise for n = 0 the answer would come out as 1 instead of 0.
In Go, with m ≤ 10⁹ every product is less than 10¹⁸, and the sum of two is less than 2·10¹⁸: uint64 is enough. For moduli around 10¹⁸ it would no longer be.
3+Solution
4Complexity
60 squarings of the matrix and at most 60 extra multiplications, each 8 multiplications of numbers: about a thousand operations per query instead of 10¹⁸.
5Common mistakes
- Looping over the recurrence. 10¹⁸ iterations is thirty years even in a fast language.
- The remainder only at the end. Fibonacci numbers grow exponentially: without a remainder after every multiplication Python will compute with gigantic numbers, and Go will overflow as early as F₉₄.
- m = 1. The identity matrix 1 mod 1 is the zero matrix, and the answer to any query is 0.
Algorithms behind it
O(log n) multiplications
2 problems
NUM
Algorithm
Matrices and recurrences
A matrix power: walks of length k in a graph, linear recurrences, the transfer matrix and Markov chains.
O(m³ log k) for A^k of size m × m
2 problems