Last Two Fibonacci Digits
National Olympiad — Regional round (2010 season)
Submission name: fib.cpp
Problem summary
For F1=F2=1 and Fn=Fn−1+Fn−2, print the last two digits of Fn, including a leading zero when needed.
Source clarification. The official statement prints n<10^9 but also gives n=9876543210 as an example. The implementation deliberately supports the example and larger 64-bit indices.
Input
The index n.
Output
Exactly two decimal digits representing Fn modulo 100.
Constraints
The printed bound is 6 < n < 10^9, but official example 3 uses n=9876543210. The solution accepts any positive unsigned 64-bit index.
Worked example
An independently prepared example for this explanation.
Input
13
Output
33
Solution analysis
- Compute Fibonacci numbers modulo 100 throughout. The fast-doubling identities F(2k)=F(k)·(2F(k+1)−F(k)) and F(2k+1)=F(k)²+F(k+1)² allow us to halve the index at each recursive call.
- Return a pair (F(n),F(n+1)). From the pair for k=floor(n/2), compute the even and odd formulas; choose the appropriate pair depending on the parity of n.
- For n=13, F13=233, so the output is 33. For n=600 the remainder is zero and must be printed as 00. Fast doubling also handles the third example beyond the printed numeric bound.
Why it works
The base pair (F0,F1)=(0,1) is correct. The standard Fibonacci addition identities imply both doubling formulas. Assuming the half-index pair correct therefore yields the correct pair for n, proving the recursion by induction. Reducing arithmetic modulo 100 preserves the required remainder.
Watch out. Normalize the subtraction in 2b−a before taking the modulus. Print two digits even for remainders below 10.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iomanip>
#include<iostream>
#include<utility>
using namespace std;
pair<int,int>fibonacci(unsigned long long n){
if(n==0){
return {0,1};
}
auto[a,b]=fibonacci(n/2);
int even=a*((2*b-a+100)%100)%100;
int odd=(a*a+b*b)%100;
if(n%2==0){
return {even,odd};
}
return {odd,(even+odd)%100};
}
int main(){
// Compute the exact archive answer using the method explained above.
unsigned long long n;
cin>>n;
cout<<setw(2)<<setfill('0')<<fibonacci(n).first<<'\n';
}