# SPOJ – POWFIB (Fibo and non fibo) Time Limit Exceeds

Posted on

Problem

Problem

Find (a^b)%M, where

a = Nth non-fibonacci number

b = Nth fibonacci number modulo M

M = 1000000007

Consider fibonacci series 1,1,2,3,…..

INPUT

First line contains T , the number of test cases.

Each next T lines contains a number N.

OUTPUT

Print T lines of output where each line corresponds to the required answer.

EXAMPLE

`Input:`

`3`

`3`

`2`

`1`

`Output:`

`49`

`6`

`4`

Constraints

`1<=T<=100000`

`1<=N<=10^7`

Here is my code for the problem link

``````#include <cstdio>
#include <unordered_map>
using namespace std;

typedef long long int ll;

ll M = 1000000007;

ll mulmod(ll a, ll b)       //modular multiplication
{
ll x = 0;
ll y = a%M;
while(b>0)
{
if(b%2)
x = (x+y)%M;
y = (y+y)%M;
b/=2;
}
return x%M;
}

ll modulo(ll a, ll b)       //modular exponentiation
{
ll x = 1;
ll y = a;
while(b)
{
if(b%2)
x = mulmod(x,y);
y = mulmod(y,y);
b/=2;
}
return x%M;
}

unordered_map<ll,ll> Fib;

ll fibo(ll n)       //n+1 th fibonacci number
{
if(n<2)
return 1;
if(Fib.find(n) != Fib.end())
return Fib[n];
Fib[n] = (fibo((n+1) / 2)*fibo(n/2) + fibo((n-1) / 2)*fibo((n-2) / 2)) % M;
return Fib[n];
}

ll nonfibo(ll n)        //nth non-fibonacci number
{
ll a = 1, b = 2, c = 3;
while(n>0)
{
a = b;
b = c;
c = a+b;
n-=(c-b-1);
}
n+=(c-b-1);
return n + b;
}

int main()
{
ll t;
scanf("%lld",&t);
while(t--)
{
ll n;
scanf("%lld",&n);
printf("%lldn",modulo(nonfibo(n),fibo(n-1)));
}
return 0;
}
``````

It exceeds the time limit, how do I improve the code?

Solution

Here, you are using modular exponentiation and modular multiplication, which are fast enough.
Your `nonfibo` function is also taking only `O(lg(n))` time.
But your method for computing `nth` fibonacci number is not much efficient. Try using this Linear Recurrence Solving Method.