HDU 2035 人见人爱A^B

原题传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2035

 

 

人见人爱A^B

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 21919    Accepted Submission(s): 15276

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

 

 

Author

 

lcy

 

 

Source

 

ACM程序设计期末考试（2006/06/07）

 

 

 

Recommend

 

lcy   |   We have carefully selected several similar problems for you:  1021 2034 1008 2033 1108

 

解法一：暴力求解，每步取模。（但是只用于b比较小的时候，如果b>=10^8估计就不行了）

#include<cstdio>
#define MOD 1000;
int a,b,ret;
int main()
{
    while(scanf("%d%d",&a,&b))
    {
        if(a==0&&b==0)break;
        ret = 1;
        while(b--){
            ret  = ret * a%MOD;
        }
        printf("%d\n",ret);
    }
    return 0;
}

解法二：快速幂。对于任意的一个b都可以表示成二进制数，例如b= 45,的时候对应的二进制数（101101）,那么他可以表示成45=2^5+2^3+2^2+2^0 =32+8+4+1；也就是说x^45 = x^32 * x^8 * x^4 * x^1；就是b的二进制数中对应有1的那一位就要参与运算，而参与累乘运算的项为b对应为1所在它整个二进制数的第几位，如果在第5位，那么就是x^(2^4)，因此，我们要解决的问题是b对应的每个1，在第几位？我们这里用位运算，用n&1，表示二进制数最后一位是不是1，如果是1,n&1的结果是1，不是则为0.这样我们可以类比十进制整数取各位上的数字一样，而代替“/”的是“>>”运算符，表示二进制数向右移动x位,n>>1表示向右移动一位（101101>>1 = 10110）；这样我觉得你应该想得到怎么做了，代码如下。

#include<cstdio>
#define MOD 1000;
int a,b,ret;
int main()
{
    while(scanf("%d%d",&a,&b))
    {
        if(a==0&&b==0)break;
        ret = 1;
        while(b>0)
        {
            if(b&1)ret = ret * a % MOD;
            a = a*a%MOD;
            b>>=1;
        }
        printf("%d\n",ret);

    }
    return 0;
}

 

<!--[if !mso]> <style> v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} p\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} v\:textbox {display:none;} </style> <![endif]-->

=(101101)