2204.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 45 行

/*  This Code is Submitted by wywcgs for Problem 2204 on 2006-04-10 at 21:12:06 */ 
#include <cstdio>
#include <cmath>

const int LMT = 100000000;
const int P = 10000;
const double SQRT_5 = sqrt(5.0);

void com(int);
void mul(int[][2], int[][2]);

int main()
{
	int f[40] = { 0, 1 }, fn, n;

	for(fn = 1; f[fn] < LMT; fn++) f[fn+1] = f[fn] + f[fn-1];
	while(scanf("%d", &n) != EOF)
		if(n < fn) printf("%d\n", f[n]);
		else {
			double x = log10((1+SQRT_5)/2)*n - log10(SQRT_5);
			x = pow(10, fmod(x, 1));
			printf("%04d...", (int)(x*1000));
			com(n-1);
		}
	
	return 0;
}

void com(int n)
{
	int 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);
	}
	printf("%04d\n", m[1][1]);
}
void mul(int a[][2], int b[][2])
{
	int 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];
	int 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;
}