王道机试指南 例题6.10 人见人爱A^B（快速幂应用）

题目：

快速幂原理：

mod 1000原理：

代码：

#include <iostream>
using namespace std;

int FastExp(int a,int b,int mod){//用快速幂求a^b % mod
    int ans=1;
    while(b!=0){ //不断求b的二进制数位
        if(b%2==1){
            ans=ans*a;
            ans=ans%mod;
        }
        b=b/2;
        a=a*a;
        a=a%mod;
    }
    return ans;
}

int main(){
    int a,b;
    while(cin>>a>>b && a!=0){
        cout<<FastExp(a,b,1000)<<endl;
    }
    return 0;
}

运行结果：