二分求幂

a^b问题中
在求得b 的二进制数后，各个二进制位为 1 的数位所代表的权重即是分解的结果。以 2 的 31 次方为例，我们首先求得 31 的二进制数 11111，在二进制表达式中 31 即被表达成 (11111) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4，这就是我们所需的分解结果。即拆2 的 31 次为 2 的 0 次、1 次、2 次、3 次、4 次的乘积，即得到前文中所讲的结果。所以，二分求幂对要求的次数并没有特殊的要求，而是对任何要求的次数都可以采用二分求幂来大大减少其乘法运算的次数。我们通过下面这个例题，来了解其编码方式。
例 4.10 人见人爱 A ^ B (九度教程第 57 题)
时间限制： 1 秒 内存限制： 128 兆 特殊判题：否
题目描述：
求 A^B 的最后三位数表示的整数。说明： A^B 的含义是 ―A的 B 次方‖
输入：
输入数据包含多个测试实例，每个实例占一行，由两个正整数 A 和 B 组成
（1<=A,B<=10000），如果 A=0, B=0，则表示输入数据的结束，不做处理。
输出：
对于每个测试实例，请输出 A^B 的最后三位表示的整数，每个输出占一行。
样例输入：
23
12 6
6789 10000
00
样例输出：
8
984
1
相信经过本章前几节内容的学习以及相应的练习，读者对求一个数的后三位
数已经没有什么问题了。那么在本例中，我们先求得 A^B 的具体数字再求其后
三位数么？这毫无疑问是不可行的，按照题面给明的输入规模， A^B 的次至多
可以达到 10000 的 10000 次，这么庞大的数字是非常不容易保存的，但是我们应
该注意到 A^B 的后三位数只与 A 的后三位数和 B 有关。这样，由于要求的仅是
最后结果的后三位数，那么我们在保存为计算该最终值的中间值时也只需保存其
后三位数即可。即，计算过程中的所有中间结果我们仅保存和使用其后三位数。
那么，我们再利用二分求幂来求得 A^B 次，同时在计算中间结果时我们都仅保
存后三位数。这样 ,我们就不用担心数字不能被保存的问题了 .
代码 4.10

#include <stdio.h> 
int main () { 
int a , b; 
while (scanf ("%d%d" ,& a,& b) != EOF ) { 
if (a == 0 && b == 0) break; 
int ans = 1; //保存最终结果变量 ,初始值为 1 
while(b != 0) { //若b不为 0，即对 b转换二进制过程未结束
if (b % 2 == 1) { //若当前二进制位为 1，则需要累乘 a的2^k次至变量 ans，
其中 2^k次为当前二进制位的权重
ans *= a; //最终结果累乘 a 
ans %= 1000; //求其后三位数
} 
b /= 2; //b除以 2 
a *= a; //求下一位二进制位的权重， a求其平方，即从 a的1次开始，依次求的 a 
的2次， a的4次... 
a %= 1000; //求a的后三位
} //一边计算 b的二进制值，一边计算 a的2^k次，并将需要的部分累乘到变量 ans上
printf( "%d\n" ,ans); //输出
} 
return 0; 
}