您的位置: 首页  >  IT文章  >  HDU 2035 人见人爱A^B（二分求幂，快速求幂）

HDU 2035 人见人爱A^B（二分求幂，快速求幂）

分类: IT文章 • 2023-11-25 12:28:19

题意：求A的B次方的后三位数字

思路1：常规求幂，直接取余求解

代码：

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    int a,b;
    int ans;
    while(~scanf("%d%d",&a,&b)){
        if(a==0&&b==0) break;
        a=a%1000;//底数取余
        ans=1;
        while(b--){
            ans=(ans*a)%1000;//结果取余
        }
        printf("%d
",ans);
    }
    return 0;
}
View Code

思路2：二分求幂（一般）

代码：

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    int a,b;
    int ans;
    while(~scanf("%d%d",&a,&b)){
        if(a==0&&b==0) break;
        a=a%1000;//底数取余
        ans=1;
        while(b>0){//b==0时，所有的因子都已经相乘，循环结束。
            if(b%2==1)//1.奇数时，多出来的一项提前放到ans里  2.b==1时，完成结果和底数的最后一次相乘
                ans=(ans*a)%1000;//结果取余
            a=(a*a)%1000;//二分操作
            b=b/2;//1.二分  2.b==1时，b/2=0,作为结束循环的条件
        }
        printf("%d
",ans);
    }
    return 0;
}
View Code

思路3：快速求幂（位操作）

Hint：  这不就是二分求幂么！  只不过改动了两个位操作。。。

  b&1 可以判断是否为奇数，相当于 b%2==1

  b=b>>1 表示b的二进制数向右移一位，相当于 b=b/2;

代码：

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    int a,b;
    int ans;
    while(~scanf("%d%d",&a,&b)){
        if(a==0&&b==0) break;
        a=a%1000;
        ans=1;
        while(b>0){
            if(b&1)//判断是否为奇数，相当于 if(b%2==1)
                ans=(ans*a)%1000;
            a=(a*a)%1000;
            b=b>>1;//二进制向右移一位，相当于 b=b/2;
        }
        printf("%d
",ans);
    }
    return 0;
}
View Code

相关推荐