[POJ]3040 Fibonacci

In the Fibonacci integer sequence, F₀ = 0, F₁ = 1, and F_n = F_{n − 1} + F_{n − 2} for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

An alternative formula for the Fibonacci sequence is

.

Given an integer n, your goal is to compute the last 4 digits of F_n.

题目已经告诉我们了求[[1, 1], [1, 0]]的n次方可以求得斐波那契的第n项，那么我们用快速幂就可以在O(log n)的时间内求得答案，快速幂的文章可以参考这篇。代码如下：

	//POJ 3070
	/*
	In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
	Given an integer n, your goal is to compute the last 4 digits of Fn.
	Input
	The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.
	Output
	For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).
	*/
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	const int MOD = 10000;
	struct Matrix {
	int m[2][2];
	Matrix operator * (const Matrix& rhs)
	{
	Matrix matrix = {0, 0, 0, 0};
	for(int i = 0; i < 2; ++i)
	for(int j = 0; j < 2; ++j)
	for(int k = 0; k < 2; ++k)
	matrix.m[i][j] = (matrix.m[i][j] + (m[i][k] * rhs.m[k][j]) % MOD) % MOD;
	return matrix;
	}
	}f;
	Matrix base = {1, 1, 1, 0};
	int pow(Matrix& matrix, int n)
	{
	Matrix res = {1, 0, 0, 1};
	while(n)
	{
	if(n & 1)
	res = res * matrix;
	matrix = matrix * matrix;
	n >>= 1;
	}
	return res.m[0][1];
	}
	int main() {
	int n;
	while(~scanf("%d",&n))
	{
	if(n == -1)break;
	base.m[0][0] = 1;
	base.m[0][1] = 1;
	base.m[1][0] = 1;
	base.m[1][1] = 0;
	printf("%d\n", pow(base, n));
	}
	return 0;
	}

view raw POJ_3070_ Fibonacci.cpp hosted with ❤ by GitHub