HDU-2035人見人愛A^B

HDU-2035人見人愛A^B

題目：

求A^B的最後三位數表示的整數。

說明：A^B的含義是“A的B次方”

Input

輸入資料包含多個測試執行個體，每個執行個體占一行，由兩個正整數A和B組成（1<=A,B<=10000），如果A=0, B=0，則表示輸入資料的結束，不做處理。

Output

對于每個測試執行個體，請輸出A^B的最後三位表示的整數，每個輸出占一行。

Sample Input

2 3

12 6

6789 10000

0 0

Sample Output

8

984

1

#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    int n,m,sum;
    while(scanf("%d %d",&n,&m) != EOF)
    {
        sum = 1;
        if(!n && !m) break;
        for(int i = 0;i < m;i++)
        {
            sum = sum * n;
            sum = sum % 1000;
        }
        cout << sum % 1000 << endl;
    }
    return 0;
}
           

一開始這道題想通過for循環來計算A^B，然後把計算出來的值對1000取餘就是最後三位了。但是，看到例子中的6789的10000次方，就打消了這樣的想法。因為題目中隻要求最後三位的數字，是以在for循環中每次累乘之後要不停的對算出來的值對1000取餘，那麼這樣就可以控住數的範圍了。

但是此時的複雜度還是o(n)，如何才能更快速呢？查閱資料之後發現有一種快速幂取模法，此時算法複雜度可縮減為o(logn)級别，例如：12^6 = 12^2* 12^4

代碼如下：

#include<stdio.h>
int mod_pow(int x, int n,int mod){      //快速幂
    int res = 1;
    while( n > 0 ){
        if( n % 2 ) res = res * x % mod;//判斷次方的奇偶
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
int main(){ 
    int m,n;
    while(scanf("%d%d",&m,&n),n||m)
        printf("%d\n",mod_pow(m,n,1000));
    return 0;
}

           

運作結果：