二分求幂： 求a^b时，对a的幂次不再是一个一个的加，而是利用之前的计算结果快速求解。 如求2^32: 2^1=2 2^2=2*2=4 2^4=2^2*2^2=64 2^8=2^4*2^4=256 2^16=2^8*2^8=65536 2^32=2^16*216=4294967296 再2^1之后的每一次结果都利用之前的结果进行计算，从而较少了计算次数。 如何确定哪些2的次幂是需要的呢？ 即是对b进行二进制表示，若改为二进制为1，则为需要的。
题目1441：人见人爱 A ^ B 时间限制：1 秒内存限制：128 兆特殊判题：否提交：2690解决：2088 题目描述： 求A^B的最后三位数表示的整数。说明：A^B的含义是“A的B次方” 输入： 输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。 输出： 对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。 样例输入： 2 3 12 6 6789 10000 0 0 样例输出： 8 984 1
#include <iostream> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int a,b; //利用二分法快速求a^b int main(int argc, char *argv[]) { cin>>a>>b; while(a != 0 && b != 0){ int ans=1; while(b != 0){ //求b的二进制 各位 if(b%2 == 1){ //这一位上二进制位1 则对结果进行累乘 ans*=a; ans=ans%1000; //按题目要求只取后三位 } a*=a; //循环产生a^1 a^2 a^4 a^16 ... ... a=a%1000; //按题目要求只取后三位 b/=2; //求b二进制的下一位 } cout<<ans<<endl; cin>>a>>b; } return 0; }题目中要求输出A^B的后三位，因此在运算中的中间结果都只去后三位即可。
