原题传送门: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次方”
说明: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
解法一:暴力求解,每步取模。(但是只用于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)
相关推荐
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
acm hdu as easy as a+b
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU1059的代码
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu_2102_passed_sorce
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类
Hdu 1237 解题代码