`
hellojyj
  • 浏览: 58411 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

HDU 2035 人见人爱A^B

    博客分类:
  • ACM
阅读更多

原题传送门: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

 

 

 

 

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)
 
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics