首页

首先看一下快速幂的思想，假设现在要求 10^75 的结果，我们将指数的二进制求出来，75 的二进制：1001011，也就是 64+8+2+1，所以 10^75 就可以拆分为 10^64+10^8+10^2+10^1 ，那么我们可以从 10^1 发出，每次指数都两个增长，然后看最开始的指数和当前指数做 & 运算，如果不为 0，说明该指数可以加到结果集中：

public int fastPower(int p, int n) {
    //p 为幂，n 为指数
    int s = p, idx = 1, res = 1; // 一开始从 p^1 开始
    while(idx <= n) {
        if((idx & n) != 0) {
            res = res * s;
        }
        s *= s;
        idx = idx << 1;
    }
    return res;
}

通过斐波那契数列来实战一下快速幂，斐波那契数列：1,1,2,3,5,8,...

除了前两项以外，f (n) = f (n-1)+f (n-2)，通过快速幂算法实现 O (logN) 的时间复杂度。

迭代式是一个二阶递推数列，可以用矩阵乘法来表示：为了方便解释，我假设矩阵

1 1

1 0

为矩阵 A

f(n) = 1*f(n-1) + 1*f(n-2)
f(n-1) = 1*f(n-1) + 0*f(n-2)
# 联合两个方程可知
(f(n), f(n-1)) = (f(n-1),f(n-2)) * A
(f(n-1), f((n-2)) = (f(n-2),f(n-3)) * A
...
(f(3),f(2)) = (f(2),f(1)) * A
#递推可知
(f(n), f(n-1)) = (f(2),f(1)) * (A^(n-2))
所以本题就变成了如何快速求 A^(n-2)，快速幂的思想就可以用了
private int[][] fastPower(int[][] m, int n) {
    if(m == null) return null;
    int row = m.length, col = m[0].length, idx = 1;
    int[][] res = new int[row][col], tmp = m;
    // 初始化为单位矩阵
    for(int i = 0; i < row; i++) res[i][i] = 1;
    while(idx <= n) {
        if((idx & n) != 0) {
            res = muli(res, tmp);
        }
        tmp = muli(tmp,tmp);
        idx <<= 1;
    }
    return res;
}
// 两个矩阵相乘，这里就不判断这两个矩阵的合法性了
private int[][] muli(int[][] m1, int[][] m2) {
    if(m1 == null || m2 == null) return null;
    int row = m1.length, col = m2[0].length;
    int[][] res = new int[row][col];
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            for(int k = 0; k < col; k++) {
                res[i][j] += m1[i][k]*m2[k][j];
            }
        }
    }
    return res;
}
最后给出解决代码：
public int f(int n) {
    if(n <= 2) return 1;
    // (1,1) * A^(n-2)
	int[][] m = {
        {1,1},
        {1,0}
    }
    m = fastPower(m, n-2);
    
    // f(n) = 1*m[0][0] + 1*m[1][0], f(n-1) = m[1][0] + m[1][1]
    return m[0][0] + m[1][0]
}