家具信息发布江西站,偷吃禁果的小宫女,s.x.suoyi
time limit: 2000/1000 ms (java/others) memory limit: 65536/32768 k (java/others)total submission(s): 51690 accepted submission(s): 18916
problem description
lcy gives a hard puzzle to feng5166,lwg,jgshining and ignatius: gave a and b,how to know the a^b.everybody objects to this bt problem,so lcy makes the problem easier than begin.
this puzzle describes that: gave a and b,how to know the a^b's the last digit number.but everybody is too lazy to slove this problem,so they remit to you who is wise.
input
there are mutiple test cases. each test cases consists of two numbers a and b(0<a,b<=2^30)
output
for each test case, you should output the a^b's last digit number.
sample input
7 66 8 800
sample output
9 6
这道题给把我整的自闭了(´-ι_-｀)
一开始根本不知道快速幂的算法，总是会tle
（这是我之前写的暴力代码，直接起飞233333）
我要评论#include <stdio.h>
int main() {
int a,b,t;
while(scanf("%d%d",&a,&b) != eof) {
t=a;
if(b > 1)
for(int i=2; i <= b; i++) {
t=t*a;
t=t%10;
}
printf("%d\n",t);
}
return 0;
}
后来dalao给我讲了讲快速幂，在迷茫之中终于搞懂了（顺便来一句，快速幂真相）；
（以下为快速幂的大体解释）
int ksm(int a,int b)
{
int ans=1;
while(b)
{
if(b & 1)
ans=ans*a%10;
a=a*a%10;
b=b >> 1;
}
return ans;
}
/*
总体上来讲就是化成二进制后用二分法思想将一个大幂次分解为若干个小幂次：
'a^n=[(a)*（二进制最后一位）]*[(a^2)*（二进制倒数第二位）]*[(a^4)*（二进制倒数第三位）]*[(a^8)*（二进制倒数第四位）]*[(a^16)*（二进制倒数第四位）]*[(a^32)*······';
*/
//程序运行以'a^13'为例：
//'13'转化二进制'1101';
**//位运算（等价于'a%2'）取二进制最后一位;
//为'1',把二分开的项运算出来放入结果，否则只进行二分
//位移（比如第一步'1 1 0 1'位移就相当于去掉二进制最后一位）'1 1 0 1';
// ^ ^
//返回**步进行，直到'b == 0';
//据二分法，得'a^13=[(a^1)*1]*[(a^2)*0]*[(a^4)*1]*[a(a^8)*1]';
由快速幂可以得出题解（因为ans计算时要考虑溢出问题所以改用long long变量储存）
样例答案（刚刚接触点c++，有点乱。。。）
#include <bits/stdc++.h>
using namespace std;
long long ksm(long long a,long long b) //快速幂
{
long long ans=1;
while(b)
{
if(b & 1)
ans=ans*a%10;
a=a*a%10;
b=b >> 1;
}
return ans;
}
int main()
{
long long a,b;
while(scanf("%lld%lld",&a,&b) != eof)
printf("%lld\n",ksm(a,b));
return 0;
}
（ps：日后我会填补快速乘的坑 ~ ヾ(=･ω･=)o）
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论