# Print a particular nth Fibonacci number in C++ up to range 10^18

In this tutorial, we are going to learn how to print a particular Fibonacci number up to range 10^18 in C++. We are going to use a hash map for this particular problem. As we know we cannot use an array for storing so many values so using the hash map is a proper choice for this particular type of problem.

Consider fib(n) to be the (n+1) th Fibonacci number. We will have two cases when n is even and another one when n is odd. Consider a variable k which is equal to n/2.

For the first case when n is even we will use this relation :

• fib(n) = fib(k)*fib(k) + fib(k-1)*fib(k-1)

For the second case when n is odd we will use this relation :

• fib(n) = fib(k)*fib(k+1) + fib(k-1)*fib(k)

Lets try to implement our above idea to get the solution of this problem.

## Program to print a particular Fibonacci number in C++

Cpp source code:

```// Program to print a particular Fibonacci number
#include<bits/stdc++.h>
using namespace std;

// Declaring hashmap
map<long long int ,long long int>F;
int fib(long long int n)
{
if(F.count(n)) // Checking if we have already calcuted that Fibonacci number
{
return F[n];
}
long long int k=n/2;
if(n%2==0)
{
return F[n]=(fib(k)*fib(k)+fib(k-1)*fib(k-1))%1000000007;
}
else
{
return F[n]=(fib(k)*fib(k+1)+fib(k-1)*fib(k))%1000000007;
}
}
// Driver Code
int main()
{
long long int n;
cout<<"Enter the ith number: ";
cin>>n;

F[0]=F[1]=1;
cout<<"\nThe "<<n <<  " th Fibonacci number is "<<fib(n-1)<<"\n";

return 0;
}```

Input/Output:

```Enter the ith number: 10000

The 10000 th Fibonacci number is 910095538```
• Time Complexity of this code is O( log n * log log n ).

You may also learn,

check if a given matrix is sparse or not in C++

Solution of Tower Of Hanoi Problem in C++

Do not forget to comment if you find anything wrong in the post or you want to share some information regarding the same.