斐波那契数列

矩阵乘法解决，保证时间复杂度为O(logN)

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = k - 2;
        if (n <= 2) {
            System.out.println(1);
            return;
        }

        int[][] matrix = new int[][]{{1, 1}, {1, 0}};
        matrix = matrixPower(matrix, n);
        int result = matrix[0][0] + matrix[1][0];
        System.out.println(result);
    }

    private static int[][] matrixPower(int[][] m, int n) {

        int[][] result = new int[m.length][m[0].length];
        for (int i = 0; i < m.length; i++) {
                result[i][i] = 1;
        }

        while (n != 0) {
            result = (n & 1) == 1 ? matrixMultiply(result, m) : result;
            m = matrixMultiply(m, m);
            n >>= 1;
        }

        return result;
    }

    private static int[][] matrixMultiply(int[][] a, int[][] b) {
        if (a[0].length != b.length)
            return null;

        int[][] result = new int[a.length][b[0].length];
        for (int row = 0; row < a.length; row++) {
            for (int column = 0; column < b[0].length; column++) {
                int temp = 0;
                for (int i = 0; i < a[row].length; i++) {
                    temp += a[row][i] * b[i][column];
                }
                result[row][column] = temp;
            }
        }

        return result;
    }
}