16 二分求幂_牛客博客

理论说明

该问题解决的是如何快速的求得a的b次方。一般做***是使用了一个循环次数为b的for循环，并在每次循环时都累乘a,这样在b次循环结束时就能获得a的b次方。但是显然这种方法并不是最优的。按照这个策略，当我们循环到第i次时，此时的累乘的结果即为2的i次。那么当我们完成了前16次循环时，我们就得到了a的16次的数字，思考要获得a的32次我们还需要继续完成后续的16次循环吗？答案是否定的，当我们已经获得了a的16次时，我们只需将a的16次对应的数字求平方，我们即可计算出a的32次方，这样后16次乘法运算我们只用了一次平方就就完成了。既然a的32次可以由a的16次求平方取到，那么a的16次呢？你还确定我们需要使用16次循环来获得该值么？答案也是否定的，a的16次只需要对a的8次求平方即可，同理要求a的8次求平方即可，同理要求a的8次我们只需对a的4次求平方....这样依次往复。这样，原本需要使用32次乘法才能完成的工作，现在只需要6次乘法便能完成，效率提高了将近6倍，这种求某个数的指定次幂即为二分求幂。

题目描述

求A^B的最后三位数表示的整数。

输入说明

输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成，如果A=0，B=0，则表示输入数据的结束，不做处理。

输出说明

对于每个测试用例，请输出A^B的最后三位表示的整数，每个输出占一行。

样例展示

样本输入：
2 3
12 6
6789 10000
0 0
样本输出：
8
984
1

C++代码

#include<iostream>
using namespace std;

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
                ans=ans*a; //如果为1
                ans%=1000;
            }
            b/=2;
            a*=a; //a都平方一下
            a%=1000; //求a的后三位
        }
        printf("%d\n",ans);
    }
    return 0;   
}