last no zero digit of N!

---

结论：

求$n!$的最后一位非零数字，最高效的计算方法是这样的：首先把$n$转化为$5$进制数$(a_ma_{m-1}a_{m-2}\cdots a_{1}a_{0})_5$,若$f(n!)$表示$n!$的最后一位非零数字，则：

$$f(n!)\equiv 2^{\sum\limits_{i=0}^{m}ia_{i}} \times \prod\limits_{i=0}^{m}a_{i}! \pmod{10}$$

注意：2的幂的最后一位会出现循环节，且这个式子中没有含5的倍数的数出现，因此可以很方便的求出最后一位数字。

思路和简要的证明：

初看结论会感觉到有点神奇，怎么会出现一个$5$进制呢？公式又看起来好复杂的样子，，最开始分析的时候如果能联想到求$n!$结尾$0$的个数问题，你就会意识到$n!$之所以会产生结尾的0，那是因为里面有一些数是5的倍数，如果除去5的倍数的数，那么我们要找的数字就是乘积最后一个数了，最后一位数字的最多取值0~9，那么这么乘下去必然是会出现循环节的。

思路就是这样，然后形式化一点就可以得出下面的式子：

$$(5i+1)(5i+2)(5i+3)(5i+4) \equiv 4 \pmod{10} \quad \quad i \in\mathbb{Z}$$ 因此，如果把$n$表示为5进制为$(a_ma_{m-1}a_{m-2}\cdots a_{1}a_{0})_5$，则有$n=5j+a_0$，
$$\prod_{1 \leq k \leq n, 5 \nmid k}{k}\equiv 4^j(a_0 !) \pmod{10}$$ 若$f(n!)$表示$n!$的最后一位非零数字，则：
$$\begin{align} f(n!) \equiv f(6^jn!) & \equiv f(6^j\prod_{1 \leq k \leq n, 5 \nmid k}{k}\prod_{1 \leq k \leq j}{5k}) \pmod{10} \\ & \equiv f\left(30^j\left(\prod_{1 \leq k \leq n, 5 \nmid k}{k}\right)j!\right) \pmod{10} \\ & \equiv f(3^j[4^j(a_0!)]j!) \pmod{10} \\ & \equiv 2^ja_0!f(j!) \pmod{10} \end{align}$$ 接着对$f(j!)$进行相同的推导，这个过程就是把n转化为5进制的过程，而推导的结果恰好就是上面结论中的公式。

附上我的渣代码：

#include <string.h>
#include <stdio.h>
int fact[10]={1,1,2,6,4,6,2,4,8};
char str[1010];
int str10[1500];
int main()
{
    while(~scanf("%s",str))
    {
        if (strcmp(str,"1")>0){
            int i,j,prod=1,r=-1,sum=0,mod=0,tem;
            int len=strlen(str);
            for (i = 0; i < len; ++i)   str10[i]=str[i]-'0';
            for (i=0; i<len; i+=(!str10[i])){
                for (j = i,mod=0; j < len; ++j){
                    tem=str10[j];
                    str10[j]=(mod<<1)+(str10[j]>4);
                    mod=tem%5;
                }
                sum+=(++r)*mod;
                prod=prod*fact[mod]%10;
            }
            printf("%d\n", fact[sum%4+5]*prod%10);
            continue;
        }
        printf("%d\n",1);
    }
}