Cod sursa(job #517654)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 29 decembrie 2010 14:01:20
Problema Al k-lea termen Fibonacci Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#define MOD	 666013

void mult(long A[2][2], long B[2][2]) {
	static long C[2][2];
	C[0][0] = A[0][0]*B[0][0] + A[0][1]*B[1][0];
	C[0][1] = A[0][0]*B[0][1] + A[0][1]*B[1][1];
	C[1][0] = A[1][0]*B[0][0] + A[1][1]*B[1][0];
	C[1][1] = A[1][0]*B[0][1] + A[1][1]*B[1][1];
	
	A[0][0] = C[0][0]; A[0][1] = C[0][1];
	A[1][0] = C[1][0]; A[1][1] = C[1][1];
}

int main() {
	long n;
	
	fscanf(fopen("kfib.in", "r"), "%ld", &n);
	long P[2][2] = {{1,1},{1,0}};
	long A[2][2] = {{1,0},{0,1}};
	
	int i;
	for (i=1; i<=n; i<<=1) {
		if ( n&i ) 
			mult(A,P);
		mult(P, P);
	}
	
	fprintf(fopen("kfib.out", "w"), "%ld\n", A[0][0]);
	return 0;
}