# My Weblog

## Project Euler Problem 304

Project euler problem 304 is bit easy problem from my perspective. You just need to a way to find out fast way to calculate Fibonacci numbers. You can use matrix multiplication to compute fibonacci numbers in o(log n) time. For this problem
|F(n)| = | 1 1|^(n-2)
|F(n-1)| = |1 0|
Here is excellent article about linear recurrence on topcoder.

```#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<gmpxx.h>
typedef mpz_class _int;
using namespace std;
_int MOD=_int(3)*_int(7)*_int(13)*_int(67)*_int(107)*_int(630803);
_int fibo(_int n)
{
_int tmp[2][2]={{0,0},{0,0}},ret[2][2]={{1,0},{0,1}},fib[2][2]={{1,1},{1,0}};
while(n!=0)
{
if(n%2==1)
{
memset(tmp,0,sizeof tmp);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) tmp[i][j] =(tmp[i][j]+ret[i][k]*fib[k][j])%MOD;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) ret[i][j]=tmp[i][j];

}
memset(tmp,0,sizeof tmp);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) tmp[i][j] =(tmp[i][j]+fib[i][k]*fib[k][j])%MOD;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) fib[i][j]=tmp[i][j];
n/=2;

}

return (ret[0][0]+ret[0][1])%MOD;
}

int main()
{

_int p=1,n,sum=0;
for(_int i=0;i<14;i++) p=p*10;
for(int i=0;i<100000;i++)
{
mpz_nextprime(n.get_mpz_t(),p.get_mpz_t());
sum= (sum+fibo(n-2))%MOD;
p=n;
}
cout<<sum%MOD<<endl;

}
```

Compile g++ filename.cpp -lgmpxx -lgmp