首页 > 试题广场 >

阶乘末尾非零数字

[编程题]阶乘末尾非零数字

热度指数：10138 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个正整数 $n$ ，记其阶乘为：

$n! = 1 \times 2 \times 3 \times \dots \times n$ 。

$\hspace{15pt}$ 请你输出 $n!$ 的十进制表示中，从右往左数第一个非零数字的数值。

输入描述:

在一行上输入一个整数 。

输出描述:

输出一个整数，代表  末尾第一个非零数字。

示例1

输入

输出

说明

当  时，，末尾第一个非零数字为 。

示例2

输入

输出

说明

当  时，，末尾第一个非零数字为 。

算法知识视频讲解

Python 3

Oliver1234

python死活超时9/10.。。。思路类似情况下别的语言就能AC，佛了

n = int(input())
cnt, tmp = 0, n # cnt 记录n!末尾0的数量(也是含有因子5的数量)
res = 1
while tmp > 0:
    tmp //= 5
    cnt += tmp
for i in range(2,n+1):
    while i % 5 == 0: # 每次相乘，除去所有因子5
        i //= 5
    if cnt > 0 and i % 2 == 0: # 在累计除去cnt个因子2
        i //=2
        cnt -= 1
    res = (i*res) % 10
print(res)

发表于 2022-02-21 13:39:02 回复(0)