按常理的算法是复杂度为O（n）如果再降低便是O（nlgn）

O(n)

    static int pow(int a, int n) {
        int res = 1;
        for (int i = 0; i < n; i++) {
            res *= a;
        }
        return res;
    }

O(nlgn)

  /**
     * 以最快速度求a的n次方
     * O(lgn)
     */
    public static int ex(int a, int n) {
        if (n == 0) return 1;
        if (n == 1) return a;
        int temp = a; //a 的 1 次方
        int res = 1;
        int exponent = 1;
        while ((exponent << 1) < n) {
            temp = temp * temp;
            exponent = exponent << 1;
        }

        res *= ex(a, n - exponent);
        return res * temp;
    }

二进制巧算

    /**
     * m=1010
     */
    public static long ex2(long n, long m) {
        if (n == 0) return 1;
        long pingFangShu = n; //n 的 1 次方
        long result = 1;
        while (m != 0) {
            //遇1累乘现在的幂
            if ((m & 1) == 1)
                result *= pingFangShu;
            //每移位一次，幂累乘方一次
            pingFangShu = pingFangShu * pingFangShu;
            //右移一位
            m >>= 1;
        }
        return result;
    }

GitHub
斐波那契与矩阵的快速幂的结合