hdu 2035--人見人愛A^B(高速べき乗関数)

B-人に好かれるA^B
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit
 
Status
 
Practice
 
HDU 2035
 
Description
A^Bの最後の3桁の表す整数を求めます.
 
説明:A^Bの意味は「AのB次方」
 
 
Input
入力データは複数のテストインスタンスを含み、各インスタンスは1行を占め、2つの正の整数AとBからなる(1<=A、B<=10000)、A=0、B=0の場合は入力データの終了を示し、処理しない.
 
Output
各テストインスタンスについて、A^Bの最後の3桁で表される整数を出力し、各出力が1行を占めます.
 
 
Sample Input

      
      
      
      

       
       
       
        2 3
12 6
6789 10000
0 0 
      
      
      
      

 
Sample Output

      
      
      
      

       
       
       
        8
984
1 
      
      
      
      

 
二分を用いて高速べき乗を解く

int pow_mod(int a,int b,int n)
{
    int ans ;
    if(b == 0)
        return 1 ;
    ans = pow_mod(a,b/2,n);
    ans = ans * ans % n ;
    if( b%2 )
        ans = ans*a % n ;
    return ans ;
}

 
 
 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int pow_mod(int a,int b,int n)
{
    int ans ;
    if(b == 0)
        return 1 ;
    ans = pow_mod(a,b/2,n);
    ans = ans * ans % n ;
    if( b%2 )
        ans = ans*a % n ;
    return ans ;
}
int main()
{
    int a , b ;
    while(scanf("%d %d", &a, &b)!=EOF)
    {
        if(a == 0 && b == 0)
            break;
        printf("%d
", pow_mod(a,b,1000) );
    }
    return 0;
}