Description
In the Fibonacci integer sequence, F_0 = 0, F_1 = 1, and F_n = F_{n-1} + F_{n-2} for n geq 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, cdots
An alternative formula for the Fibonacci sequence is
Given an integer n, your goal is to compute the last 4 digits of F_n.
Input
The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 leq n leq 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 F_n. If the last four digits of F_n are all zeros, print 0; otherwise, omit any leading zeros (i.e., print F_n mod 10000).
Sample Input
0
9
999999999
1000000000
-1
Sample Output
0
34
626
6875
Hint
As a reminder, matrix multiplication is associative, and the product of two 2 imes 2 matrices is given by
Also, note that raising any 2 imes 2 matrix to the 0th power gives the identity matrix:
The data used in this problem is unofficial data prepared by 695375900. So any mistake here does not imply mistake in the offcial judge data.
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include<cmath> 6 #include<sstream> 7 #include<string> 8 using namespace std; 9 #define M 10000 10 struct matrix 11 { 12 int a[2][2]; 13 }; 14 matrix mul(matrix x,matrix y) 15 { 16 matrix temp; 17 memset(temp.a,0,sizeof(temp.a)); 18 for(int i=0;i<2;i++) 19 for(int j=0;j<2;j++) 20 for(int k=0;k<2;k++) 21 temp.a[i][j]=(temp.a[i][j]+x.a[i][k]*y.a[k][j])%M; 22 return temp; 23 } 24 matrix mpow(matrix A,int n) 25 { 26 matrix B; 27 memset(B.a,0,sizeof(B.a)); 28 for(int i=0;i<2;i++) 29 B.a[i][i]=1; 30 while(n>0) 31 { 32 if(n&1) 33 B=mul(B,A); 34 A=mul(A,A); 35 n>>=1; 36 } 37 return B; 38 } 39 int main() 40 { 41 matrix A; 42 int n; 43 while(~scanf("%d",&n)) 44 { 45 A.a[0][0]=1;A.a[0][1]=1; 46 A.a[1][0]=1;A.a[1][1]=0; 47 if(n==-1) 48 break; 49 if(n==0) 50 {printf("0 "); 51 continue;} 52 if(n==1) 53 {printf("1 "); 54 continue;} 55 56 A=mpow(A,n); 57 printf("%d ",A.a[1][0]);} 58 return 0; 59 }