快速幂和矩阵快速幂

快速幂

快速幂是数论中最简单的几种算法之一，顾名思义，就是快速计算某个数的多少次幂。相较于传统循环pow的计算方法，快速幂的复杂度为 O ( l o g 2 N ) O(log_2N) O(log2​N)，而传统的方法是O(N)级别。归纳一下，两种的方法优势如下：

快速幂：快

循环：不用动脑

快速幂的实现

我们都知道对于任何一个整数N，都能用二进制来表示。那么对于aⁿ， n一定可以用二进制表示。比如求2⁸ ,我们可以转化为计算2¹⁰⁰⁰ 。

接下来，以计算a¹⁵⁶为例，它可以转换为a^10011100，来讲解快速幂的实现。

按照传统的方法，我们需要计算156次，而如果只计算10011100（2），则运算次数 = 二进制的长度（8）* 二进制中1的个数（4）=24。这项计算公式不理解的同学，可以先看下面的图和代码。

以下给出代码实现（特别注意，这里运用了位运算符，没有这个基础的同学，需要自己补一下课）。

public int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

矩阵快速幂

矩阵快速幂与快速幂相比，仅仅是底数和乘数换成了矩阵形式。

所以，我们可以对上面的代码进行简单的修改，将源代码中整数乘法的地方，更换成矩阵的乘法。假设矩阵乘法的函数名为，multiply()，则得：

public int[][] qpow(int a, int n){
    int ans = {{1, 0}, {0, 1}};
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans = multiply(ans, a);  //ans乘上当前的a
        a = multiply(a, a);        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

该方法在求形如f(n) = f(n-1) + f(n-2)之类的递归表达式时非常有用。