2060.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2060 on 2006-04-14 at 14:29:01 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int P = 1000000000;

int fib(int);
void mul(int64[][2], int64[][2]);

int main()
{
	int b, e;
	
	while(scanf("%d %d", &b, &e) != EOF && e != 0)
		printf("%d\n", (fib(e+1)-fib(b)+P)%P);
	
	return 0;
}

int fib(int n)
{
	int64 i, b, m[2][2] = { { 0, 1 }, { 1, 1 } }, unit[2][2] = { { 0, 1 }, { 1, 1 } };
	for(b = 31; (n&(1<<b)) == 0; b--);
	for(i = b-1; i >= 0; i--) {
		mul(m, m);
		if(n & (1<<i)) mul(m, unit);
	}
	return (m[1][0]+m[1][1])%P;
}
void mul(int64 a[][2], int64 b[][2])
{
	int64 a1 = a[0][0]*b[0][0]+a[0][1]*b[1][0], a2 = a[0][0]*b[0][1]+a[0][1]*b[1][1];
	int64 b1 = a[1][0]*b[0][0]+a[1][1]*b[1][0], b2 = a[1][0]*b[0][1]+a[1][1]*b[1][1];
	a[0][0] = a1%P; a[0][1] = a2%P; a[1][0] = b1%P; a[1][1] = b2%P;
}