嘘~ 正在从服务器偷取页面 . . .

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

发布日期: 2024-06-15

更新日期: 2024-07-05

文章字数: 444

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())))