UC知道ACM的一道题
来源：百度知道 编辑：UC知道 时间：2024/05/17 22:57:43
个位数字
Time Limit:1000MS Memory Limit:32768K
Description:
Ray 参加了数学兴趣小组，其中一道题目是求a^b(a的b次方)个位数字是多少，聪明的Ray 一下子就解决了，你是否也像Ray 一样聪明呢？
Input:
第一行是一个整数N，表示有N组数据1<=N<=10000。每组数据是两个整数a和b，a、b的位数都不超过100位且a、b>0。
Output:
输出a^b的个位数字，每组占一行。
Sample Input:
3
3 2
12 9
123456789 121
Sample Output:
9
2
9
Time Limit:1000MS Memory Limit:32768K
Description:
Ray 参加了数学兴趣小组，其中一道题目是求a^b(a的b次方)个位数字是多少，聪明的Ray 一下子就解决了，你是否也像Ray 一样聪明呢？
Input:
第一行是一个整数N，表示有N组数据1<=N<=10000。每组数据是两个整数a和b，a、b的位数都不超过100位且a、b>0。
Output:
输出a^b的个位数字，每组占一行。
Sample Input:
3
3 2
12 9
123456789 121
Sample Output:
9
2
9
文件io就不说了，仅说算法。有两个显然的事实：
1.a只需要知道个位数字即可。
2.一个数的n次方，个位数字对于n是循环的。
因此可以维护10个数组，第i个数组储存个位为i的数的各次幂的个位情况。
简单说来如下：a[i][0]保存i的循环节有多长。循环节从i[1]开始。
int[10] a;
a[0] = {1,0};
a[1] = {1,1};
a[2] = {4,2,4,8,6};
a[3] = {4,3,9,7,1};
a[4] = {2,4,6};
a[5] = {1,5};
a[6] = {1,6};
a[7] = {4,7,9,1,7};
a[8] = {4,8,4,2,6};
a[9] = {2,9,1};
这个数组可以作为预处理阶段由计算机计算出来，或者像这样事先算好手工编码。都不困难。
剩下的事情是，读入a的个位k，以及b，则a[k][b % a[k][0]]就是结果。