小白詳細講解快速冪--杭電oj2035-A^B，杭電oj2035-a

小白詳細講解快速冪--杭電oj2035-A^B，杭電oj2035-a

Problem Description 求A^B的最後三位數表示的整數。
說明：A^B的含義是“A的B次方”  Input 輸入數據包含多個測試實例，每個實例占一行，由兩個正整數A和B組成（1<=A,B<=10000），如果A=0, B=0，則表示輸入數據的結束，不做處理。  Output 對於每個測試實例，請輸出A^B的最後三位表示的整數，每個輸出占一行。 　　簡單的說這題就是要求高次冪，有兩種方法可以實現。 　　第一總比較土鱉，每次乘完對1000取余也可以過。 　　我要講的是第二種聽起來很高大上的方法——快速冪。為什麼叫快速冪呢？因為用它求冪非常快，對於x^n,復雜度為O（logn），是不是很吊！快速冪的原理是把冪分解，把一個很大的冪分解成較小的幾部分。例如： 11的二進制是1011 11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1 因此，我們將a¹¹轉化為  即把n化為2進制數，每個為1的位都是較小的一部分。這樣可以用一個循環來解決。下面是快速冪的非遞歸代碼，暫時忽略max

int cal(int x, int n, int max){

　　int sum = 1;　　　　//最後輸出的結果
　　while (n > 0){　　　//當冪降為0是結束
　　if (n & 1)　　　　　　//位運算，&是按位與，當兩邊都為1，表達式為1，這個是用來判斷二進制數最後一位是否為1，這裡n是以二進制的形式比較的

　　　　sum = sum*x%max;//如果為1，sum就要乘x^i,i為該位在二進制數中的位置
　　n >>= 1;　　　　　　//>>為位運算符，右移一位，即去掉已經計算過的部分
　　x = x*x%max;　　　　//用來標記記錄x^2^i,循環i次即去掉了i位,當第i+1位為1時，sum就要乘x^2^i;
　　}
　　return sum;//循環結束返回結果。
}

　　現在來講max的作用，用來把數變小的，我們可以想象如果是很大的數的很高次方，乘幾次後數據非常大無法用任何一個基本數據類型表示，而且這也是不必要的，通常我們只需要知道最後若干位的值，這就可以用到取余了，余數的冪和原數的冪在余數的位數上是相同的，所以每次進行乘法運算後都要取余，當然如果數據很小也可以不用取余。

　　好了，感覺我已經講的很詳細了！！真的是盡力了。。。

下面貼上上面那題的代碼

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int cal(int x, int n, int max){
 5     int sum = 1;
 6     while (n > 0){
 7         if (n & 1)
 8             sum = sum*x%max;
 9         n >>= 1;
10         x = x*x%max;
11     }
12     return sum;
13 }
14 int main(){
15     int x, n;
16     while ((cin >> x >> n) && (x || n)){
17         cout << cal(x, n, 1000) << endl;
18     }
19     return 0;
20 }