各处看来的姿势

为什么要写这样一篇博文呢？

因为在知乎上看到了一个问题感觉思想有用？

2016 的阶乘（2016!）末尾第一个非零数字是几？

传送门：https://www.zhihu.com/question/47569759

不妨令2016!末尾有k个零， $n = \frac{2016!}{10^k}$

因为2016!因子里2肯定比5多，所以 $n \equiv 0 \pmod 2$

来数2016!因子5的个数

$\begin{array}{} 2016 &\div& 5 &=& 403 &...& 1 \\ 403 &\div& 5 &=& 80 &...& 3 \\ 80 &\div& 5 &=& 16 &...& 0 \\ 16 &\div& 5 &=& 3 &...& 1\\ 3 &\div& 5 &=& 0 &...& 3 \\ \end{array}$

Notes:

考虑以前做过的一道题，k的阶乘的末尾有几个0，我们知道因子里2肯定比5多，所以看因子5的数量，我们的做法是用k去除5，25，125…这里就是一样的道理啦。

因此 $2^k \cdot n \equiv (1 \cdot 2 \cdot 3 \cdot 4)^k \cdot 1^2 \cdot (1 \cdot 2 \cdot 3)^2 \pmod 5, k = 403+80+16+3$

Notes:

这是为什么呢？左边是2016!/5^k，右边是2016!除去所有5以后的余数，因为是mod 5的，所以只有4中因子的可能，比如1 mod 5=1，2 mod 5=2，3 mod 5=3，4 mod 5=4，6 mod 5=1，是一直循环的，所以这里求了一下周期（减去有5因子的数后），其实我觉得可以直接找周期不这样做。

有 $1 \cdot 2 \cdot 3 \equiv 1 \pmod 5$

所以， $n \equiv 2^{502} \pmod 5$

又有 $2^4 \equiv 1 \pmod 5$

于是 $n \equiv 2^2 \pmod 5$ （利用周期）

用中国剩余定理求出 $n \equiv 4 \pmod {10}$

Notes：

结合之前的n≡0(mod 2)，由中国剩余定理，k=(4×2×inv(2,5)+0×5×inv(5,2))%(2×5)=4。

还看到了一个让我有启发的回答：

小于2016的质数表
将2016！表示成质数表的指数积
消掉2，5
计算剩余质数指数积的尾数

提示：每个数都表示成质数字典