二分求幂
计算A^B可以使用最直接的方法，即累乘，但是还有更简单的方式，例如计算2的32次方，假设计算到了2的16次方，我们还要继续重复这个乘2的过程么？更简单的方式是平方，这样就可以直接的到结果了，按照这种方式计算2的32次方，我们总共要计算6次，从2到2的平方，再到2的4次方，再到2的8次方，再到2的16次方，再到2的32次方，这样看来，其实二次求幂的方式就是将A^B转化为一系列A^N的乘积，其实这些乘积是有规律的，我们可以使用B的二进制序列来表示，例如：
求解2^31, 我们先将31用二进制表示 11111 = 2^0 + 2^1+2^2+2^3+2^4 其实结果本身就对应着2的0次，1次，2次，3次，4次的乘积。使用代码来表示（非递归）：
int power(int a, int b){
int ans = 1;
while(b!=0){
if(b%2)
ans *= a;
a *= a;
b /= 2;
}
return ans;
}例题
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
代码 & 分析
只是一个小小的变形，因为题目的输入数据在经过次方运算之后会很大，所以但是只是取最后三位数字的话，我们只可以在计算过程中不停的对1000取模，这样一直保持在规模较小的计算上。主要还是二分求幂的方法。
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
int a, b;
int ans = 1;
int main(){
while(cin>>a>>b && a &&b){
ans = 1;
while(b!=0){
if(b%2){
ans *= a;
ans %= 1000;
}
a *= a;
a %= 1000;
b /= 2;
}
cout<<ans<<endl;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116803.html
