Question

c语言算n^n，1<=N<=1,000,000,000，输出个位数

#include <stdio.h>
int main(void)
{
int t,k,i,j,x;
__int64 n;
while(scanf("%d",&t)!=EOF)
{
for(i=0;i<t;i++)
{
k=1;
scanf("%I64d",&n);
x=(n-1)%4;
n=n%10;
for(j=0;j<=x;j++)
{
k=k*n;
}
printf("%d\n",k%10);
}
}
return 0;
}

为什么要x=(n-1)%4然后再循环

Answer 1

你这里求 n^n的个位数
我说说a^b的个位数算法吧（a=b时就是n^n）
首先：a^b的个位数 等于 a的个位数 的b次方 即等于(a%10)^b的个位数
现在的问题就是观察0到9的b次方的个位数规律了（a%10范围0到9）

0,1,5,6的b次方结果的个位还是0,1,5,6 （）
2的b次方结果的个位以 2,,4,8,6 循环 （b每增加4循环一次）
3的b次方结果的个位以3,9,7,1循环 （b每增加4循环一次）
4:以4,6循环 （b每增加2循环一次）
7: 7,9,3,1循环 （b每增加4循环一次）
8: 8,4,2,6循环 （b每增加4循环一次）
9: 9,1循环 （b每增加2循环一次）
所以，所有数字把b每增加4次看成一个回合，它是一个循环可以不管。
比如：
1的14次方，个位数 就是1^(14%4)=1^2=1的个位数1
3的9次方，个位数 就是 3^(9%4)=3^1=3的个位数3
4的11次方，个位数 就是4^(11%4)=4^3=64的个位数4
所以a^b的个位数与 (a%10)^(b%4)的个位是相同的
这里有个情况，当b%4=0时，其实他的个位数与 (a%10)^4的个位数相同而不是 (a%10)^0

这里x=(n-1)%4就是解决这种情况的
当n%4不等于0时
(n-1)%4 = n%4 -1
---------------------------------
x=(n-1)%4;
n=n%10;
for(j=0;j<=x;j++) //这里计算的就是 (a%10)^(b%4)的值了
{
k=k*n;
}
因为 j 从0开始，比如计算 4^6的值4096，这样就是
k=1;
for(j=0;j<=6-1;j++) //6要减1
{
k=k*4;
}
最后k=4096
所以上面用的x=(n-1)%4; 也就是x= n%4 -1，也就是 要减1
---------------------
当n%4等于0时
(n-1)%4=3
按上面说的，for循环计算的是 n%10 的4次方（j=0，1，2，3 乘了4次n%10）

结果也是对的