刷的一道水题，有点数学规律，思路挺有意思的，有些细节方面没有注意竟然还WA了一次，po上来。

 

题目：

A hard puzzle

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

 

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

 

 

Author

eddy

 

 

Recommend

JGShining   |   We have carefully selected several similar problems for you:  1076 1061 1096 1106 1003 

 

思路题解：

1. 看题，并不难，首先先考虑了下暴力求解，但是看下数的范围，emmm，算了吧。

2。所以开始考虑简便算法。 因为是考虑到最后一位的话，幂计算的话，结果的最后一位，也只跟原数的个位有关。

同时，0-9这十个数种，自己画了一下， 0，1，5，6四个数，多少次幂的结果个位都和原数相同，

而其他数，例如7：

7的1次方末尾数是7

7的2次方末尾数是9，

7的3次方末尾数是3，

7的4次方末尾数是1，

7的5次方末尾数是7，

……可以周期为4，如果你要说如果是1的几次方呢，周期不是1吗，怎么办，没关系，因为无论举哪一个数，最大的周期都为4，所以都可以看成周期为4的来算。

所以，规律 周期为四 找到了，就可以直接由幂次来考虑求解。

int c=b%4;
	if(c==0){
		printf("%d\n",a*a*a*a%10);
	}
	if(c==1){
		printf("%d\n",a%10);
	}
	if(c==2){
		printf("%d\n",a*a%10);
	}
	if(c==3){
		printf("%d\n",a*a*a%10);
	}

但是！！！！ 如果只考虑到这个，那就提交，那就想我第一次提交，成功WA掉了。

错误示范：

#include <stdio.h>
int main (){
long long int a,b;
while (scanf("%lld %lld",&a,&b)!=EOF){
	int c=b%4;
	if(c==0){
		printf("%d\n",a*a*a*a%10);
	}
	if(c==1){
		printf("%d\n",a%10);
	}
	if(c==2){
		printf("%d\n",a*a%10);
	}
	if(c==3){
		printf("%d\n",a*a*a%10);
	}

}
return 0;
}

需要注意：

如果当a非常大时，则在操作过程中，很容易就直接溢出。

所以，要对a进行下简化。因为只与个位有关，那就只提取出个位数。

 

正确答案：

#include <stdio.h>
int main (){
    long long int a,b;
    while (scanf("%lld %lld",&a,&b)!=EOF){
	a=a%10;
	int c=b%4;
	if(c==0){
		printf("%d\n",a*a*a*a%10);
	}
	if(c==1){
		printf("%d\n",a%10);
	}
	if(c==2){
		printf("%d\n",a*a%10);
	}
	if(c==3){
		printf("%d\n",a*a*a%10);
	}

}
    return 0;
}

PS：当然此类问题也可以用快速幂求解，但会比较麻烦，没有此法简单，回头更下快速幂解法。