循環算法：
long long normalPower(long long base,long long power){
long long result=1;
for(int i=1;i<=power;i++){
result=result*base;
}
return result%1000;
}
但是仔細思考後會發現，當a和b很大的時候，這有很大的缺點，指數關係很容易爆炸。這道題其實出的很有意思，題目要求你輸出結果的後三位，為什麼不讓你直接輸出結果呢？難道僅僅只是為了增大題目的難度嗎？
我們可以看一下關於取模的規律
對於取模來說
(a + b) % p =(a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p ) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
其中我們只要關注第「3」條法則即可：(a * b) % p = (a % p * b % p) % p ，我們仔細研究一下這個運算法則，會發現多個因子連續的乘積取模的結果等於每個因子取模後的乘積再取模的結果。也就是說，我們如果要求：
(a*b*c)%d=(a%d*b%d*c%d)%d;
因此，我們可以藉助這個法則，只需要在循環乘積的每一步都提前進行「取模」運算，而不是等到最後直接對結果「取模」，也能達到同樣的效果。
所以，我們的代碼可以變成這個樣子：
long long normalPower(long long base,long long power){
long long result=1;
for(int i=1;i<=power;i++){
result=result*base;
result=result%1000;
}
return result%1000;
}
但是時間複雜度依然是O(N)，有什麼方法可以更快一點呢？（看標題）
快速冪：
快速冪算法能幫我們算出指數非常大的冪，傳統的求冪算法之所以時間複雜度非常高（為O(指數n)），就是因為當指數n非常大的時候，需要執行的循環操作次數也非常大。所以我們快速冪算法的核心思想就是每一步都把指數分成兩半，而相應的底數做平方運算。這樣不僅能把非常大的指數給不斷變小，所需要執行的循環次數也變小，而最後表示的結果卻一直不會變。讓我們先來看一個簡單的例子：
3^10=3*3*3*3*3*3*3*3*3*3
儘量想辦法把指數變小來，這裡的指數為10
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
3^10=(3*3)^5
3^10=9^5
此時指數由10縮減一半變成了5，而底數變成了原來的平方，求3^10原本需要執行10次循環操作，求9^5卻只需要執行5次循環操作，但是3^10卻等於9^5,我們用一次（底數做平方操作）的操作減少了原本一半的循環量，特別是在冪特別大的時候效果非常好，例如2^10000=4^5000,底數只是做了一個小小的平方操作，而指數就從10000變成了5000，減少了5000次的循環操作。
現在我們的問題是如何把指數5變成原來的一半，5是一個奇數，5的一半是2.5，但是我們知道，指數不能為小數，因此我們不能這麼簡單粗暴的直接執行5/2，然而，這裡還有另一種方法能表示9^5
9^5=（9^4）*（9^1）
此時我們抽出了一個底數的一次方，這裡即為9^1，這個9^1我們先單獨移出來,剩下的9^4又能夠在執行「縮指數」操作了，把指數縮小一半，底數執行平方操作
9^5=（81^2）*(9^1)
把指數縮小一半，底數執行平方操作
9^5=（6561^1）*(9^1)
此時，我們發現指數又變成了一個奇數1，按照上面對指數為奇數的操作方法，應該抽出了一個底數的一次方，這裡即為6561^1，這個6561^1我們先單獨移出來，但是此時指數卻變成了0，也就意味著我們無法再進行「縮指數」操作了。
9^5=（6561^0）*(9^1)*(6561^1)=1*(9^1)*(6561^1)=(9^1)*(6561^1)=9*6561=59049
我們能夠發現，最後的結果是9*6561，而9是怎麼產生的？是不是當指數為奇數5時，此時底數為9。那6561又是怎麼產生的呢？是不是當指數為奇數1時，此時的底數為6561。所以我們能發現一個規律：最後求出的冪結果實際上就是在變化過程中所有當指數為奇數時底數的乘積。
代碼
```
long long fastPower(long long base, long long power) {
long long result = 1;
while (power > 0) {
if (power % 2 == 0) {
//如果指數為偶數
power = power / 2;//把指數縮小為一半
base = base * base % 1000;//底數變大成原來的平方
} else {
//如果指數為奇數
power = power - 1;//把指數減去1，使其變成一個偶數
result = result * base % 1000;//此時記得要把指數為奇數時分離出來的底數的一次方收集好
power = power / 2;//此時指數為偶數，可以繼續執行操作
base = base * base % 1000;
}
}
return result;
}
```
優化：
```
long long fastPower(long long base, long long power) {
long long result = 1;
while (power > 0) {
if (power % 2 == 1) {
result = result * base % 1000;
}
power = power / 2;
base = (base * base) % 1000;
}
return result;
}
按位運算：
在C語言中，power%2==1可以用更快的「位運算」來代替，例如：power&1。因為如果power為偶數，則其二進位表示的最後一位一定是0；如果power是奇數，則其二進位表示的最後一位一定是1。將他們分別與1的二進位做「與」運算，得到的就是power二進位最後一位的數字了，是0則為偶數，是1則為奇數。例如5是奇數，則5&1=1；而6是偶數，則6&1=0；因此奇偶數的判斷就可以用「位運算」來替換了。
而且，對於power=power/2來說，也可以用更快的「位運算」進行替代，我們只要把power的二進位表示向右移動1位就能變成原來的一半了。
代碼：
```
long long fastPower(long long base, long long power) {
long long result = 1;
while (power > 0) {
if (power & 1) {//此處等價於if(power%2==1)
result = result * base % 1000;
}
power >>= 1;//此處等價於power=power/2
base = (base * base) % 1000;
}
return result;
}