【快速幂】a的n次幂的算法

    public static int QuickRow(int a, int n){
        int ans = 1;
        if (n == 0){
            return 1;
        }
        while (n>0){
            if (n%2 == 0){ // n为偶数
                ans *= a;
                n/=2;
            }else {    // n为奇数
                n--;
                ans *= a;
            }
        }
        return ans;
    }

时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

算法思路

1. 当n为偶数时，  = （）
2. 当n为奇数时，让n - 1 变成偶数，加上 a ，再用偶数方法算 

---

比如算 3的100次幂