??說實話，自己是第一次接觸到快速冪這種東西，覺得有必要記錄下來。

題意：

計算a^n % b，其中a，b和n都是32位的整數(shù)。

樣例：

例如 2^31 % 3 = 2

例如 100^1000 % 1000 = 0

挑戰(zhàn)：

O(logn)

1.解題思路

??在介紹這個題的解題思路之前，我先來簡單的介紹一下，什么是快速冪？

(1).快速冪

??快速冪，顧名思義就是快速的求次冪，例如:a^b，普通的算法就是累乘，這樣的計算方法的時間復(fù)雜度就是O(n),而快速冪的方法使得次冪的計算方法的時間復(fù)雜度降低到O(logn).
??假設(shè)我們要求a^b的結(jié)果，這里我們可以將b轉(zhuǎn)換為二進制來求。例如：

                    a^11 = a(2  ^ 0 + 2 ^ 1 + 2 ^ 3) = a ^(1011);

??所以，我們得出結(jié)果：a^11 = (a ^ (2 ^ 3)) *( a ^(2 ^ 1)) *( a^(2 ^ 0));
也就是說，我們只要把次冪化成二進制數(shù)，那么我們操作起來就非常的簡單了。怎么化成二進制呢？在位運算符中，>>符號表示將一個數(shù)字右移一位，也就是說，我們這里可以通過這個符號來一位一位的計算(這里講的是二進制數(shù)，當十進制數(shù)使用這個符號來操作的話，我們可以將十進制數(shù)當成二進制數(shù)右移)。同時我們還可以使用&符號來看看我們二進制數(shù)的最后一位數(shù)是不是0，比如 a & 1 == 0,表示的是a的二進制數(shù)的最后一位是0，反之就是不為0.這里清楚了這一點的話，下面的代碼就非常的容易理解。
??這里我來舉一個例子，例如，我們想要求a ^ b的結(jié)果，按照快速冪的求法，代碼如下：

public int fastPower(int a, int b) {
        int ans = 1;
        int base = a;
        while (b != 0) {
            if ((b & 1) != 0) { //如果當前的次冪數(shù)最后一位(二進制數(shù))不為0的話，那么我們將當前權(quán)值加入到最后答案里面去
                ans = ans * base;
            }
            //權(quán)值增加
            base = base * base;
            b >>= 1;
        }
        return ans;
    }

(2).取模

??但是這個題不是簡單的快速冪，而是需要求余數(shù)，理解到了上面的快速冪的求法，那么這里就非常的簡單，就是在計算的時候在取一次模就行了。

public int fastPower(int a, int b, int n) {
        if (n == 0) {
            return 1 % b;
        }
        long ans = 1l;
        long base = a % b;
        while (n != 0) {
            if ((n & 1) == 1) {
                ans = (ans * base) % b;
            }
            //為了避免超出long的范圍，所以取三次模
            base = (base % b) * (base % b) % b;
            n >>= 1;
        }
        return (int) ans;
    }