My Weblog

Blog about programming and math

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

Advertisements

October 13, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: