Fibonacci Modulo a Small Number
National Olympiad — National round (2018 season)
Submission name: fib.cpp
Problem summary
Compute the n-th Fibonacci number modulo m, with F1=F2=1.
Input
n m.
Output
Fn modulo m.
Constraints
1 ≤ n ≤ 1000000000; 2 ≤ m ≤ 1000.
Worked example
Input and output for the worked example discussed below.
Input
13 13
Output
12
Solution analysis
- The matrix [[1,1],[1,0]] advances a pair of consecutive Fibonacci numbers. Its n-th power has Fn in its top-right entry.
- Use binary exponentiation: start with the identity, multiply the answer when the current exponent bit is 1, square the base, then halve the exponent. Reduce every entry modulo m after arithmetic.
- For n=13, F13=233 and 233 modulo 13 is 12. Reducing during multiplication is valid because addition and multiplication respect congruence; the huge exact Fibonacci number is never constructed.
Why it works
The Fibonacci transition matrix correctly advances the recurrence, and binary exponentiation computes its exact n-th power modulo m.
Complexity: O(log n) time, because 2×2 matrix multiplication is constant-size, and O(1) space.
Watch out. Use the stated 1,1 indexing. Keep the identity matrix modulo m and do not run a billion ordinary recurrence steps.
Commented C++17 solution
An independently written complete program with standard headers.
// The Fibonacci transition matrix correctly advances the recurrence, and binary exponentiation computes its
// exact n-th power modulo m..
#include<array>
#include<iostream>
using namespace std;
using Matrix=array<array<int,2>,2>;
Matrix multiply(const Matrix&a,const Matrix&b,int modulo){
Matrix result{};
for(int row=0;row<2;row++){
for(int column=0;column<2;column++){
for(int middle=0;middle<2;middle++){
result[row][column]=(result[row][column]+a[row][middle]*b[middle][column])%modulo;
}
}
}
return result;
}
int main(){
int exponent,modulo;
cin>>exponent>>modulo;
Matrix answer{{{1,0},{0,1}}};
Matrix base{{{1,1},{1,0}}};
while(exponent>0){
if(exponent%2==1){
answer=multiply(answer,base,modulo);
}
base=multiply(base,base,modulo);
exponent/=2;
}
cout<<answer[0][1]<<'\n';
}