Question->http://www.spoj.com/problems/FIBOSUM/ Basically question is to find the sum

of fibonacci numbers starting from N to M I did this question using the factor (1+sqrt(5))/2.I >found N,N+1 using this factor by O(log N) multiplication.Then finally i traversed all the numbers >from N+2 to M and side by side adding their sum.My code takes O(N-M+logN) time.But i am getting >time limit exceeded on this solution.What can i do to improve the time complexity of my solution.I

thought of doing using dynamic programming will it be faster ??plz help

```
#include<iostream>
#include<math.h>
long int power_multiply(long int,long int&);
using namespace std;
int main()
{
long int N,M,a,b,sum=0,c,t;
cin>>t;
while(t--){
cin>>N>>M;
a=power_multiply(N,b);//i passed b as reference so that a=f(n),b=f(n+1) are simultaneously
if(N==M){sum=a;} //calculated
else
{ sum=a+b;
long int i=N+2;
while(i!=M+1)
{
c=b+a;
sum=sum+c;
sum%=1000000007;
a=b;
b=c;
i++;
}
}}//else
cout<<sum<<"\n";
}
return 0;
}
long int power_multiply(long int a,long int &b)//this mulitplication takes O(logN) time
{
double x=(1+sqrt(5))/2,ans=1,y=x;
while(a>0)
{
if(a%2!=0)
{
ans=ans*x;
}
x=x*x;
a=a/2;
}
a=floor(ans/sqrt(5)+0.5); //for finally converting a to its nearest integer
b=floor((ans*y)/sqrt(5)+0.5); //for computing b from answer which i got while
//evaluating 'a' and also converting it to its
//nearest integer
return a;
}
```