BISHI59　阶乘末尾非零数字¶

中等通过率 16.89%python3样例通过牛客 AC基础数学

牛客原题　源码

讲解章节：组合数学

一句话

求 n! 去掉末尾所有 0 后的最后一位，n <= 1e7。

解题思路¶

这题考什么¶

模意义下的「去 5 递归」+ 中国剩余定理拼回十进制位。

直接算 n! 是天方夜谭（1e7! 有约 6.5e7 位）。设

z = v5(n!) = ⌊n/5⌋ + ⌊n/25⌋ + ...     （末尾 0 的个数）
X = n! / 10^z                           （去掉末尾 0 后的整数）

要求的就是 X mod 10。用 CRT 拆成 mod 2 与 mod 5：

n >= 2 时 v2(n!) > v5(n!)，所以 X 仍是偶数 → X ≡ 0 (mod 2)；
只需再求 X mod 5，两者拼起来唯一确定 X mod 10。 X mod 5 ∈ {1,2,3,4}（不可能是 0，5 已被除干净），对应的偶数末位分别是 6, 2, 8, 4。

求 X mod 5：令 F(n) = 「n! 去掉全部因子 5 之后」mod 5。把 1..n 分成「5 的倍数」与其余两类：

非 5 倍数：每满 5 个一组，乘积 123*4 = 24 ≡ -1 (mod 5)，共 ⌊n/5⌋ 组，再乘上零头 (n mod 5)!；
5 的倍数：提出 5^⌊n/5⌋ 后剩下 ⌊n/5⌋!，递归。

即 F(n) = (-1)^⌊n/5⌋ * (n mod 5)! * F(⌊n/5⌋) (mod 5)。最后 X = F / 2^z，除以 2 就是乘 inv(2) = 3：X ≡ F * 3^z (mod 5)。

数据规模与复杂度¶

n <= 1e7。O(n) 的「逐个乘、随时去 2 去 5」在 Python 里要跑 1e7 次大整数取模，必然超时；本递归只有 O(log_5 n) ≈ 10 层，是 O(log n)。

坑在哪¶

n = 1（以及 0）必须特判：1! = 1 是奇数，上面「X 是偶数」的前提不成立，直接输出 1。从 n = 2 起公式才对；
递归里的 (-1)^k 在 mod 5 下要写成 4^(k mod 2) 或者最后统一 % 5 转正；
z 用 while 累加 n//5、n//25... 而不是 n//4（那是等比和的近似，错的）；
3^z mod 5 直接用内置 pow(3, z, 5)，2 在模 5 下的阶是 4，不必手动约减；
递归式写成了 while 循环（尾递归展开），n <= 1e7 时只有 10 层，写成真递归也不会爆栈，但循环省掉了函数调用开销。

样例复核¶

n = 6：z = 6//5 = 1；F(6) = 1! * (-1)^1 * F(1)， F(1) = 1! = 1，故 F(6) ≡ -1 ≡ 4 (mod 5)； X ≡ 4 * 3^1 = 12 ≡ 2 (mod 5)，查表得末位 2 —— 6! = 720 ✓。 n = 10：z = 2；F(10) = 0! * (-1)^2 * F(2)，F(2) = 2! = 2，故 F ≡ 2； X ≡ 2 * 3^2 = 18 ≡ 3 (mod 5)，查表得 8 —— 10! = 3628800 ✓。

中国剩余定理（CRT，把「模若干个互质的数」的结果拼回「模它们乘积」的结果）与阶乘性质见 85-基础数学与递推及 80-数论基础。

参考实现¶

solutions/BISHI59.py
import sys


def f_mod5(n: int) -> int:
    """n! 去掉所有因子 5 之后，模 5 的值。"""
    res = 1
    fact = (1, 1, 2, 6, 24)          # 0!..4!，用来处理不足 5 个的零头
    # 递推 F(n) = (-1)^⌊n/5⌋ * (n mod 5)! * F(⌊n/5⌋) 展开成循环，每轮除以 5
    while n:
        res = res * fact[n % 5] % 5  # 零头 (n mod 5)!
        if (n // 5) & 1:             # (-1)^⌊n/5⌋：⌊n/5⌋ 为奇数才翻号
            res = (5 - res) % 5      # 模 5 下取相反数，外层 % 5 兜住 res==0
        n //= 5                      # 进入下一层：5 的倍数提出 5 后剩 ⌊n/5⌋!
    return res


def main() -> None:
    n = int(sys.stdin.buffer.read().split()[0])
    if n < 2:                        # 0! = 1! = 1，末位就是 1
        sys.stdout.write("1\n")
        return
    # 勒让德公式：v5(n!) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...
    z = 0                            # 末尾 0 的个数 = v5(n!)
    p = 5
    while p <= n:                    # p 每轮乘 5，n <= 1e7 时最多 10 轮
        z += n // p
        p *= 5
    r = f_mod5(n) * pow(3, z, 5) % 5     # 3 = inv(2) mod 5，除掉多余的 2^z
    sys.stdout.write("%d\n" % (0, 6, 2, 8, 4)[r])   # 偶数 + 模 5 余 r -> 唯一末位


main()

BISHI59 阶乘末尾非零数字¶