//第一题：

public class Fibonacci {

/**
* /a b/
* /c d/
*/
private static class Matrix{
int a;
int b;
int c;
int d;

public Matrix(int a, int b, int c, int d) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
}
}

public static void main(String[] args) {
Arrays.asList(1,2,3,4,5,6,7,8,9,10).stream().forEach(n->System.out.println(fibonacci(n)));
}


public static int fibonacci(int n){
if(n==1)
return 0;
return Fib(n-1).b;
}

public static Matrix Fib(int n){
if(n==1)
return new Matrix(1,1,1,0);
return (n&1)==0?multi(Fib(n/2),Fib(n/2)):multi(Fib(n/2),Fib(n/2 + 1));
}

private static Matrix multi(Matrix m1,Matrix m2){
return new Matrix(
m1.a*m2.a+m1.b*m2.c,
m1.a*m2.b+m1.b*m2.d,
m1.c*m2.a+m1.d*m2.c,
m1.c*m2.b+m1.d*m2.d
);
}
}