人见人爱A^B——HDU

人见人爱A^B
Problem Description
求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

二分幂：13 = 1 1 0 1
所以a^13 = a^8 * a^4 * a^1
认真分析一下弄懂了就不难，我也是看了很久才稍微明白点。其实很早就知道快速幂模，但是只是记住了模板没有记住算法的推导，过一段时间忘记了模板又不会做了。这个故事说明一个道理：编程没有捷径。

#include <cstdio>
typedef long long ll;
ll binaryPow(ll a,ll b,ll m){
    ll ans = 1;//ans用来表示之前计算出的结果，最开始相当于a的0次方，赋值为1 
    while(b > 0){
        if(b & 1){
            ans = ans * a % m; //a的1,2,4,8,16等次方，当前a的权值等于前一项的平方，因为平方已经算过了所以直接乘以a 
        }
        a = a * a % m; //a始终在前面结果的基础上平方，所以a的权值实际上是1,2,4,8等等次方 
        b=b >> 1; //b每次都右移一位，相当于除以2主要是转变为b的二进制形式 
    }               //为什么是右移除到0，而不是左移，因为a的1次方刚好跟b的二进制形式的最低位对应，然后a的2次方 与b的次低位对应 
    return ans; 
}
int main(){
    ll a,b;
    while(scanf("%lld%lld",&a,&b) != EOF){
        if(a == 0 && b == 0) break;
        printf("%lld\n",binaryPow(a,b,1000));
    }
    return 0;
}