一种快速求N的N次方的个位数的算法
ACM题库有这么一道题：
求N的N次方的个位数。
很简单的题目，但是如果用普通算法就会超时，因为N可能很大很大。
本文介绍自己想出的一个快速求解办法。也许也有人跟我想的一样。
先看公式：

3*3*3=27，所以答案应该是7.
4*4*4*4=256，所以答案应该是6.
最容易想到的就是连续乘N，最后按10取余数。但是肯定会超时的。

其实不难发现，做连乘的时候，个位数变化是比较有规律的。
比如以6,1,0结尾的数，无论多大，自己本身的N次方的个位数还是6,1,0.
所以就想到计算一个pos指针，它可以指明个位数的变化是多大的一个循环。
对6,1,0来说，pos=1。
然后比如计算1236的1236次方，对1236取1的余数，为0.
说明只需要取得1236的个位数，就是1236的1236次方的个位数。
如果还不明白，下面以个位数为3的整数为例，说明pos指针的运作。
3*3=9
9*3=27
7*3=21
1*3=3
3*3=9
看，一个尾数为3的整数，它自己次方的尾数会在4次循环之后回到9.所以pos按此法计算。

下面是代码：

 继续加油发掘。    2 楼    zui4yi1    2011-12-07              单纯想求N^N的个位数的话，去学数论的同余，可化简成这样：
d= N%10,
k=d%4
d^k的个位数即N^N的个位数,即g=d^k%10。

d是个位数,k<=3，这个计算量你会求吧？

    3 楼    zui4yi1    2011-12-07              zui4yi1 写道单纯想求N^N的个位数的话，去学数论的同余，可化简成这样：
d= N%10,
k=d%4
d^k的个位数即N^N的个位数,即g=d^k%10。

d是个位数,k<=3，这个计算量你会求吧？


晕，打错了，k=N%4才对，事实上，求N^M的个位数的通式都是这样：
d = N % 10,
k = M % 4,
若k=0,则d=4
g = d^k % 10    4 楼    zui4yi1    2011-12-07              若k=0,则k=4    5 楼    zui4yi1    2011-12-07              N^M的个位数g:
d = N % 10,
k = M % 4,
若k=0,则k=4
g = d^k % 10