Question

一个很简单的C语言程序

Given a positive integer N, you should output the most right digit of N^N. Input The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.Each test case contains a single positive integer N(1<=N<=1,000,000,000). Output For each test case, you should output the rightmost digit of N^N. Sample Input 2 3 4  Sample Output 7 6 Hint In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7. In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.  求各种答案，我老是超出时间限制，求救

Answer 1

不要先把总结果求出来再取最后一个数字
因为最后一个数字肯定有数字的个位数决定
比如13^13,就求3*13，但是每次记录最后一个数字
3×3=9 9
9×3=27 7
7×3=21 1
1×3=3 3
3×3 9
然后就可以看出是个最后结果处于每4次一个循环
因为13x13x13...x13总共有12个乘号，所以12%4=0所以结果是3

再举一个例子77^77，就求7^77
7×7=49 9
9×7=63 3
3×7=21 1
1×7=7 7
7×7=49 9
所以4次一循环
77x77x77..x77中有76个乘号，所以76%4=0，所以取循环的第四个数，答案是7

再举一个列子98×98，就求8^98
8×8=64 4
4×8=32 2
2×8=16 6
6×8=48 8
8×8=64 4
出现循环，4次一循环
98×98....×98中有97个乘号，97%4=1，取第1个数，所以结果为4

以下就是我自己编写的程序，程序中有详细的说明，你根据我举例好好想一下，如果再不懂，继续问

#include<stdio.h>
int main()
{
int n;//输入的正整数
long aresult;//每次相乘得到的个位数
printf("please input a positive integer:");
scanf("%d",&n);
int m=n%10;//取出正整数n的个位数，比如123，m就是3，274，m就是4
int a[10];//用于存储aresult的数组，记录aresult的不重复的值
int aflag=0;//数组a的标志，也用来记录a数组的元素个数
int i,j;//用于循环
int forflag=0;//用途是如果aresult值与a数组中的值重复，那么退出所有循环，详细用途请阅读所有程序
for(i=0;i<n;++i)//外循环，每次用于记录aresult的值
{
if(i==0)//第一次执行循环时，把第一次m×m的值的个位数保存在数组a中，然后跳出第一次循环
{
aresult=m*m%10;
a[aflag++]=aresult;
continue;
}
aresult=m*aresult%10;//记录m×aresult的值的个位数并保存在aresult中
for(j=0;j<10;j++)//内循环，检测数组aresult值是否与数组a中的值相等，如果相等，那么代表出现循环
{
if(aresult==a[j])
{
forflag=1;//设置标记，用于检测到出现循环后退出所有循环
break;
}
if(j==9)//如果没有相同元素，那么添加aresult到数组a中，aresult是每次相乘得到的个位数
a[aflag++]=aresult;
}//end j for
if(forflag)//如果符合条件，退出外循环
break;
}//end i for
if((n-1)%aflag==0)//如果n-1是aflag的倍数的话，那么结果就是a保存的最后一个数，也就是说，乘号的总数是循环的倍数
printf("%d\n",a[aflag-1]);
else//否则结果就是数组a中n-1对aflag求余的余数再减去1的位置，因为aflag记录的是数组a中元素的个数
printf("%d\n",a[(n-1)%aflag-1]);
return 0;
}

经过我仔细推敲后的认为更好的程序
#include<stdio.h>
int main()
{
int n;
long aresult;
printf("please input a positive integer:");
scanf("%d",&n);
int m=n%10;
int a[10];
int aflag=0;
int i;
for(i=0;i<n;++i)
{
if(i==0)
{
aresult=m*m%10;
a[aflag++]=aresult;
continue;
}
aresult=m*aresult%10;
if(aresult==a[0])
break;
a[aflag++]=aresult;
}//end i for
if((n-1)%aflag==0)
printf("%d\n",a[aflag-1]);
else
printf("%d\n",a[(n-1)%aflag-1]);
return 0;
}

Answer 2

首先，对于任意数N，其可以表示为m*10+N1，其中m及N1都为整数且0<=N1<=9，则有N^N=(m*10+N1)^N=求和(i=0, N)*C(i,N)*(m*10)^(N-i)*N1^N，对于i=1...N的项，其值模10均为0，故N^N的最后一位仅与N1有关，问题简化为N1^N%10。

又知对于0<=N1<=9，N1^m(m是正整数)其末位存在循环特征，如下：
0 : 0，循环长度为1
1 : 1，循环长度为1
2 : 2 4 8 6，循环长度为4
3 : 3 9 7 1，循环长度为4
4 : 4 6，循环长度为2
5 : 5，循环长度为1
6 : 6，循环长度为1
7 : 7 9 3 1，循环长度为4
8 : 8 4 2 6，循环长度为4
9 : 9 1，循环长度为2

然后由以上特征去解题，应该不会再超时了。

Answer 3

我觉得你不妨可以总结一下各位为0~9的数的k次方的各位数的规律.都是有章可循的.然后直接由这个规律根据输入的数字做一些简单的判断即可.时间有点晚了.不写程序了.不过这思路应该是可行的.
比如说个位为0的结果是0
个位为1的结果是1
各位为2的结果应该是2,4,8,6,2,4,8,6如此一直循环下去
以此类推