SP2124 FCTRL4 - Last Non-Zero Digit of Factorials 题解

题目链接：FCTRL4 - Last Non-Zero Digit of Factorials

题意：

多组数据，每次给出一个正整数 \(n(n \le 10^{100})\) ，求 \(n!\) 最后一位非零数字。

例如 \(5! = 1\times 2 \times 3 \times 4 \times 5 = 120\) ，它的最后一位非零数字是 \(2\) 。

好像我是这题代码最短的，只有 202B 。

记 \(a = \left\lfloor\frac{n}{5}\right\rfloor,~b = n - 5\times \left\lfloor\frac{n}{5}\right\rfloor\) ，并记 \(L(n)\) 为 \(n!\) 最后一位非 \(0\) 数字，则 \[ \begin{aligned} L(n) &= 5\times 10\times 15\times \cdots\times (1 \times 2 \times 3 \times 4)(6 \times 7 \times 8 \times 9)(11\times 12\times 13\times 14)\times \cdots \\[6pt]&=5^a\cdot a!\cdot (1 \times 2 \times 3 \times 4)(6 \times 7 \times 8 \times 9)(11\times 12\times 13\times 14)\cdots \\[6pt]&=5^a\cdot a!\cdot (1 \times 2 \times 3 \times 4)(6 \times 7 \times 8 \times 9)(1\times 2\times 3\times 4)\cdots(1\times 2\times\cdots\times b) \\[6pt]&=5^a\cdot a!(4\times 6)(4\times 6)\cdots (1\times 2\times \cdots \times b) \\[6pt]&=5^a\cdot a! \cdot 2^{2a} \cdot 6^a\cdot b! \\[6pt]&=2^{a} L(a)L(b)\cdot 6^a \end{aligned} \pmod{10} \] 由于 \(2^a\) 的个位数等于 \(2^{a \bmod 4}\) ，并且 \(6\) 乘以任何偶数 \(x\) 都不改变 \(x\) 的个位数，故 \[ L(n) = 2^{a \bmod 4}L(n/5)\cdot L(n \bmod 5) \pmod{10} \] 时间复杂度 \(\mathcal{O}(100\times \log_5 n)\)

代码：（懒得写高精度了）

import sys

p = lambda x: [1, 2, 4, 8][x % 4]

def L(n):
	if n < 5:
		return [1, 1, 2, 6, 4][n]
	return p(n // 5) * L(n // 5) * L(n % 5) % 10

for b in sys.stdin.readlines():
	print(L((int)(b.strip())))

---

参考文献：

[1] https://www.youtube.com/watch?v=RmENut3ZmnM

[2] https://www.luogu.com.cn/article/i75zelbh

---

题外话：

怎么 2020 年的时候交了这么多发暴力？

另外这道题应该是目前写过最短的 省选/NOI− 了吧。