二分求幂——人见人爱的A^B

image.png

解题思路：

• 分解a的b次为若干个a的2^k次的积。
• 本题要求的仅是最后结果的后三位数，那么我们在保存为计算该最终值的中间值时也只需保存其后三位数即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


int main(){

    int a,b;
    while(scanf("%d %d",&a,&b)){
        if(a==0&&b==0){
            break;
        }
        int ans=1;
        while(b!=0){
            if(b%2==1){
                ans=ans*a;
                ans%=1000;
            }
            b=b/2;
            a=a*a;
            a%=1000;
        }
        printf("%d\n",ans);


    }
    return 0;

}

如果觉得有帮助，点个赞再走吧^_^